arxiv: 2604.16030 · v3 · submitted 2026-04-17 · 💻 cs.DS

Recognition: unknown

Hardness, Tractability and Density Thresholds of finite Pinwheel Scheduling Variants

Sotiris Kanellopoulos , Giorgos Mitropoulos , Christos Pergaminelis , Thanos Tolias

Authors on Pith no claims yet

Pith reviewed 2026-05-10 07:38 UTC · model grok-4.3

classification 💻 cs.DS

keywords pinwheel schedulingNP-completenessdensity thresholdsfinite schedulingmultiplicityrandomized algorithmsk-visits problem

0 comments

The pith

2-Visits pinwheel scheduling is strongly NP-complete even when each deadline appears at most twice.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies finite versions of pinwheel scheduling in which each task must be executed a fixed number of times within a bounded window while respecting its deadline. It establishes that deciding the existence of such a schedule for exactly two executions per task remains hard even when no deadline value is shared by more than two tasks. This settles a prior open question and shows that earlier positive results for specially structured inputs do not extend to the general case with multiplicity two. The work also places the same problem in RP whenever the number of distinct deadlines is a fixed constant and supplies matching lower and asymptotic bounds on the highest input density that always admits a feasible schedule.

Core claim

We prove that 2-Visits is strongly NP-complete even when the maximum multiplicity of the input is equal to 2. We prove that 2-Visits is in RP when the number of distinct deadlines is constant. We generalize all existing positive results for 2-Visits to a mixed version in which some tasks are visited once and others twice. We establish a lower bound of √2−1/2≈0.9142 for the density threshold of 2-Visits and prove that the density threshold of k-Visits approaches 5/6 as k tends to infinity.

What carries the argument

The 2-Visits decision problem, which asks whether a sequence of length 2n exists that executes each of n tasks exactly twice without any deadline expiring between consecutive executions of the same task.

If this is right

2-Visits remains strongly NP-complete on all inputs whose deadlines take at most two identical values.
2-Visits admits a randomized polynomial-time algorithm whenever the number of distinct deadline values is bounded by a constant.
All previously known polynomial-time cases of 2-Visits extend directly to the mixed setting in which tasks may require either one or two visits.
The highest density guaranteeing a feasible 2-Visits schedule is at least √2−1/2.
The highest density guaranteeing a feasible k-Visits schedule converges to 5/6 in the limit of large k.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Scheduling software for systems with only a handful of distinct periods can safely use randomized methods even when exact deadlines repeat a few times.
Finite-horizon pinwheel variants may allow higher utilization than their infinite counterparts before becoming infeasible.
The gap between the proven 0.9142 lower bound for two visits and the 5/6 limit suggests that intermediate visit counts may admit still tighter density thresholds.
Exact solvers for these problems will likely need to combine branch-and-bound with randomization when the number of distinct deadlines grows.

Load-bearing premise

The reductions establishing NP-completeness assume that the input deadlines are positive integers and that the scheduling constraints can be encoded without additional side constraints such as release times or resource conflicts.

What would settle it

A deterministic polynomial-time algorithm that correctly decides every 2-Visits instance whose deadlines have multiplicity at most two would contradict the claimed strong NP-completeness.

Figures

Figures reproduced from arXiv: 2604.16030 by Christos Pergaminelis, Giorgos Mitropoulos, Sotiris Kanellopoulos, Thanos Tolias.

**Figure 1.** Figure 1: A map of the chain of reductions to 2-Visits in [29] compared to our multiplicitypreserving chain of reductions in Section 3 (bold arrows). The reduction marked with a (*) preserves the maximum multiplicity and is thus used as the final step for our result. In Section 3 we prove that 2-Visits remains strongly NP-hard even when the maximum multiplicity of the input is 2. Our result mostly relies on an alt… view at source ↗

**Figure 2.** Figure 2: A map of our reductions in Section 4, transforming 2 [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** Figure 3: An example of a Position Matching instance, corresponding to the 2-Visits instance D = {1, 4, 5, 6, 6, 7, 15, 16, 18, 18, 18}, and its solution. A is the discretized sequence of D and T = [2n] \ A (see Lemma 1). Observe that none of the black lines dictating the solution cross the dotted lines (the borders of clusters), due to the d ≥ a restriction of Position Matching. 2.2.3 Pinwheel variants and the conc… view at source ↗

**Figure 4.** Figure 4: The reduction of Lemma 6, from EWPM in multigraphs to EWPM in simple graphs. Unlabeled edges have weight 0. The perfect matchings of both graphs denoted by red edges have total weight 10. Lemma 6. There is a linear-time reduction from EWPM in multigraphs to EWPM in simple graphs, preserving weights and multiplying the amount of edges by 3. Proof. Let G be a multigraph. We construct a simple graph G′ by rep… view at source ↗

**Figure 5.** Figure 5: The density function from the proof of Lemma 9: [PITH_FULL_IMAGE:figures/full_fig_p020_5.png] view at source ↗

read the original abstract

The k-Visits problem is a recently introduced finite version of Pinwheel Scheduling [Kanellopoulos et al., SODA 2026]. Given the deadlines of n tasks, the problem asks whether there exists a schedule of length kn executing each task exactly k times, with no deadline expiring between consecutive visits (executions) of each task. In this work we prove that 2-Visits is strongly NP-complete even when the maximum multiplicity of the input is equal to 2, settling an open question from [Kanellopoulos et al., SODA 2026] and contrasting the tractability of 2-Visits for simple sets. On the other hand, we prove that 2-Visits is in RP when the number of distinct deadlines is constant, thus making progress on another open question regarding the parameterization of 2-Visits by the number of numbers. We then generalize all existing positive results for 2-Visits to a version of the problem where some tasks must be visited once and some other tasks twice, while providing evidence that some of these results are unlikely to transfer to 3-Visits. Lastly, we establish bounds for the density thresholds of k-Visits, analogous to the $(5/6)$-threshold of Pinwheel Scheduling [Kawamura, STOC 2024]; in particular, we show a $\sqrt{2}-1/2\approx 0.9142$ lower bound for the density threshold of 2-Visits and prove that the density threshold of k-Visits approaches $5/6\approx 0.8333$ for $k \to \infty$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper settles the open NP-completeness question for 2-Visits at multiplicity 2 and supplies concrete density lower bounds that approach the classic 5/6 threshold.

read the letter

The paper settles the open question on the complexity of 2-Visits by proving it is strongly NP-complete even when the maximum multiplicity of the input is 2. This is the central result and it contrasts directly with the tractability for simple sets mentioned in the abstract. They also establish that 2-Visits is in RP when the number of distinct deadlines is constant, generalize positive results to mixed 1-visit and 2-visit instances, and derive density lower bounds for k-Visits that approach the 5/6 threshold of classic pinwheel scheduling as k goes to infinity, with a specific bound of about 0.914 for the 2-Visits case. The new hardness result stands out because it resolves a question left open in the SODA 2026 paper without relying on higher multiplicities. The RP membership advances the parameterization by the number of distinct values. Extending the tractability to the mixed case is a reasonable next step, and the evidence against easy transfer to 3-Visits is a helpful boundary. The density work is analogous to existing thresholds and gives explicit numbers that can be used in further analysis. The reductions appear to use the standard setup of positive integer deadlines without additional constraints such as release times. This is common in scheduling hardness proofs and does not introduce obvious problems. The abstract does not show any internal contradictions or circular reasoning, and the results build independently on the prior work. This paper is for people working specifically on pinwheel scheduling and finite variants in real-time systems. Readers interested in complexity of periodic tasks will get direct value from the settled open question and the new membership and bound results. It is too specialized for most general algorithms papers. The thinking is clear and it engages honestly with the open questions in the literature. It deserves a serious referee because it provides concrete progress on complexity classification and density thresholds. I would recommend sending this to peer review.

Referee Report

0 major / 3 minor

Summary. The paper studies the k-Visits problem, a finite variant of Pinwheel Scheduling. It proves strong NP-completeness of 2-Visits even under maximum multiplicity 2 (resolving an open question), shows membership in RP when the number of distinct deadlines is constant, generalizes existing tractability results to a mixed 1-visit/2-visit setting while providing evidence that some results fail to extend to 3-Visits, and derives density-threshold bounds including a √2−1/2≈0.9142 lower bound for 2-Visits and convergence to the classical 5/6 threshold as k→∞.

Significance. If the reductions and randomized algorithm are correct, the work resolves two open questions from the SODA 2026 predecessor, supplies the first parameterized tractability result for 2-Visits, and gives the first explicit finite-pinwheel density bounds that parallel the known infinite-pinwheel threshold. These contributions are load-bearing for the complexity landscape of the problem and would be of clear interest to the scheduling and parameterized-complexity communities.

minor comments (3)

The abstract states that positive results for 2-Visits are generalized to the mixed-visit variant but does not name the specific prior results being extended; a one-sentence pointer in the introduction would improve traceability.
The density-threshold section presents the √2−1/2 lower bound numerically; adding a short derivation sketch or reference to the construction used would help readers verify the constant without consulting external material.
The RP-membership proof for constant distinct deadlines is mentioned only in the abstract; a brief high-level outline of the randomized algorithm (e.g., sampling method or witness size) in the main text would clarify the parameterization.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of our manuscript and for recommending minor revision. The referee summary correctly reflects our main results: the strong NP-completeness of 2-Visits even at multiplicity 2, membership in RP for constant distinct deadlines, the generalization of tractability results to the mixed 1-visit/2-visit setting, and the density-threshold bounds (including the 0.9142 lower bound for 2-Visits and the limit of 5/6 as k grows).

Circularity Check

0 steps flagged

Minor self-citation to prior work; new proofs and bounds are independent

full rationale

The paper defines the k-Visits problem by reference to the SODA 2026 work and settles an open question from that paper via a new strong NP-completeness proof for 2-Visits at multiplicity 2, an RP membership result for constant distinct deadlines, and new density threshold bounds. These results are established through explicit reductions, randomized algorithms, and threshold arguments that do not reduce any claimed theorem to a fitted parameter, self-definition, or unverified self-citation chain. The self-citation is limited to problem introduction and open-question context and is not load-bearing for the new theorems.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard definitions from complexity theory (NP-completeness, RP) and the prior formalization of k-Visits; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (2)

standard math Standard definitions of strong NP-completeness and randomized polynomial time (RP)
Invoked when classifying 2-Visits as strongly NP-complete and in RP.
domain assumption The k-Visits problem is correctly formalized as a finite schedule of length kn with exactly k executions per task
Basis for all stated results; taken from the cited SODA 2026 paper.

pith-pipeline@v0.9.0 · 5613 in / 1449 out tokens · 27355 ms · 2026-05-10T07:38:33.848051+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

43 extracted references · 39 canonical work pages · 1 internal anchor

[1]

Networks75(2), 113–123 (2020)

Baller, A.C., van Ee, M., Hoogeboom, M., Stougie, L.: Complexity of in- ventory routing problems when routing is easy. Networks75(2), 113–123 (2020). https://doi.org/10.1002/NET.21908,https://doi.org/10.1002/net.21908

work page doi:10.1002/net.21908 2020
[2]

ACM Trans

Bar-Noy, A., Ladner, R.E., Tamir, T.: Windows scheduling as a restricted version of bin packing. ACM Trans. Algorithms3(3), 28 (2007). https://doi.org/10.1145/1273340.1273344, https://doi.org/10.1145/1273340.1273344

work page doi:10.1145/1273340.1273344 2007
[3]

In: Bercea, I.O., Pagh, R

Biktairov, Y., Gasieniec, L., Jiamjitrak, W.P., Namrata, Smith, B., Wild, S.: Simple approximation algorithms for polyamorous scheduling. In: Bercea, I.O., Pagh, R. (eds.) 2025 Symposium on Simplicity in Algorithms, SOSA 2025, New Orleans, LA, USA, Jan- uary 13-15, 2025. pp. 290–314. SIAM (2025). https://doi.org/10.1137/1.9781611978315.23, https://doi.org...

work page doi:10.1137/1.9781611978315.23 2025
[4]

In: Distributed Computing, 24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13-15, 2010

Blin, L., Milani, A., Potop-Butucaru, M., Tixeuil, S.: Exclusive perpetual ring ex- ploration without chirality. In: Distributed Computing, 24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13-15, 2010. Proceedings. pp. 312–327 (2010). https://doi.org/10.1007/978-3-642-15763-9 29,https://doi.org/10.1007/978-3- 642-15763-9_29

work page doi:10.1007/978-3-642-15763-9 2010
[5]

Algorithmica84(9), 28 2597–2621 (2022)

Bosman, T., van Ee, M., Jiao, Y., Marchetti-Spaccamela, A., Ravi, R., Stougie, L.: Approxi- mation algorithms for replenishment problems with fixed turnover times. Algorithmica84(9), 28 2597–2621 (2022). https://doi.org/10.1007/S00453-022-00974-4,https://doi.org/10.1007/ s00453-022-00974-4

work page doi:10.1007/s00453-022-00974-4 2022
[6]

IEEE Trans

Chan, M.Y., Chin, F.Y.L.: General schedulers for the pinwheel problem based on double-integer reduction. IEEE Trans. Computers41(6), 755–768 (1992). https://doi.org/10.1109/12.144627,https://doi.org/10.1109/12.144627

work page doi:10.1109/12.144627 1992
[7]

Algo- rithmica9(5), 425–462 (1993)

Chan, M.Y., Chin, F.Y.L.: Schedulers for larger classes of pinwheel instances. Algo- rithmica9(5), 425–462 (1993). https://doi.org/10.1007/BF01187034,https://doi.org/10. 1007/BF01187034

work page doi:10.1007/bf01187034 1993
[8]

Chuangpishit, H., Czyzowicz, J., Gasieniec, L., Georgiou, K., Jurdzinski, T., Kranakis, E.: Patrolling a path connecting a set of points with unbalanced frequencies of visits. In: SOFSEM 2018: Theory and Practice of Computer Science - 44th International Conference on Current Trends in Theory and Practice of Computer Science, Krems, Austria, January 29 - F...

work page doi:10.1007/978-3-319-73117-9 2018
[9]

In: Flocchini, P., Prencipe, G., Santoro, N

Czyzowicz, J., Georgiou, K., Kranakis, E.: Patrolling. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities, Current Research in Moving and Computing, Lecture Notes in Computer Science, vol. 11340, pp. 371–400. Springer (2019). https://doi.org/10.1007/978-3-030-11072-7 15,https://doi.org/10.1007/ 978-3-030-11072-7_15

work page doi:10.1007/978-3-030-11072-7 2019
[10]

In: Combinatorial Algorithms - 31st International Workshop, IWOCA 2020, Bordeaux, France, June 8-10, 2020, Proceedings

Damaschke, P.: Two robots patrolling on a line: Integer version and approximability. In: Combinatorial Algorithms - 31st International Workshop, IWOCA 2020, Bordeaux, France, June 8-10, 2020, Proceedings. pp. 211–223 (2020). https://doi.org/10.1007/978-3-030-48966- 3 16,https://doi.org/10.1007/978-3-030-48966-3_16

work page doi:10.1007/978-3-030-48966- 2020
[11]

Algorithms12(4), 74 (2019)

D’Emidio, M., Stefano, G.D., Navarra, A.: Bamboo garden trimming problem: Prior- ity schedulings. Algorithms12(4), 74 (2019). https://doi.org/10.3390/A12040074,https: //doi.org/10.3390/a12040074

work page doi:10.3390/a12040074 2019
[12]

van Ee, M.: A 12/7-approximation algorithm for the discrete bamboo garden trimming problem. Oper. Res. Lett.49(5), 645–649 (2021). https://doi.org/10.1016/J.ORL.2021.07.001, https://doi.org/10.1016/j.orl.2021.07.001

work page doi:10.1016/j.orl.2021.07.001 2021
[13]

In: Berenbrink, P., Bouyer, P., Dawar, A., Kant´ e, M.M

El Maalouly, N.: Exact Matching: Algorithms and Related Problems. In: Berenbrink, P., Bouyer, P., Dawar, A., Kant´ e, M.M. (eds.) 40th International Symposium on Theoreti- cal Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in In- formatics (LIPIcs), vol. 254, pp. 29:1–29:17. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Infor- mati...

work page doi:10.4230/lipics.stacs.2023.29 2023
[14]

In: Benoit, A., Kaplan, H., Wild, S., Herman, G

El Maalouly, N., Haslebacher, S., Taubner, A., Wulf, L.: On Finding l-Th Smallest Per- fect Matchings. In: Benoit, A., Kaplan, H., Wild, S., Herman, G. (eds.) 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in In- formatics (LIPIcs), vol. 351, pp. 19:1–19:15. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur In- formatik,...

work page doi:10.4230/lipics.esa.2025.19 2025
[15]

Theory Comput

Fellows, M.R., Gaspers, S., Rosamond, F.A.: Parameterizing by the number of numbers. Theory Comput. Syst.50(4), 675–693 (2012). https://doi.org/10.1007/S00224-011-9367-Y, https://doi.org/10.1007/s00224-011-9367-y

work page doi:10.1007/s00224-011-9367-y 2012
[16]

Algorith- mica34(1), 14–38 (2002)

Fishburn, P.C., Lagarias, J.C.: Pinwheel scheduling: Achievable densities. Algorith- mica34(1), 14–38 (2002). https://doi.org/10.1007/S00453-002-0938-9,https://doi.org/10. 1007/s00453-002-0938-9

work page doi:10.1007/s00453-002-0938-9 2002
[17]

Gasieniec, L., Jurdzinski, T., Klasing, R., Levcopoulos, C., Lingas, A., Min, J., Radzik, T.: Perpetual maintenance of machines with different urgency requirements. J. Comput. Syst. Sci.139, 103476 (2024). https://doi.org/10.1016/J.JCSS.2023.103476,https://doi.org/10. 1016/j.jcss.2023.103476

work page doi:10.1016/j.jcss.2023.103476 2024
[18]

In: Steffen, B., Baier, C., van den Brand, M., Eder, J., Hinchey, M., Mar- garia, T

Gasieniec, L., Klasing, R., Levcopoulos, C., Lingas, A., Min, J., Radzik, T.: Bamboo gar- den trimming problem (perpetual maintenance of machines with different attendance ur- gency factors). In: Steffen, B., Baier, C., van den Brand, M., Eder, J., Hinchey, M., Mar- garia, T. (eds.) SOFSEM 2017: Theory and Practice of Computer Science - 43rd Interna- tion...

work page doi:10.1007/978-3-319-51963-0 2017
[19]

In: Phillips, C.A., Speckmann, B

Gasieniec, L., Smith, B., Wild, S.: Towards the 5/6-density conjecture of pinwheel schedul- ing. In: Phillips, C.A., Speckmann, B. (eds.) Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2022, Alexandria, VA, USA, January 9-10, 2022. pp. 91–103. SIAM (2022). https://doi.org/10.1137/1.9781611977042.8,https://doi.org/10. 1137/1....

work page doi:10.1137/1.9781611977042.8 2022
[20]

2016 , issue_date =

Gurjar, R., Korwar, A., Messner, J., Straub, S., Thierauf, T.: Planarizing gadgets for perfect matching do not exist. ACM Trans. Comput. Theory8(4), 14:1–14:15 (2016). https://doi.org/10.1145/2934310,https://doi.org/10.1145/2934310

work page doi:10.1145/2934310 2016
[21]

ACM Trans

Gurjar, R., Korwar, A., Messner, J., Thierauf, T.: Exact perfect matching in complete graphs. ACM Trans. Comput. Theory9(2), 8:1–8:20 (2017). https://doi.org/10.1145/3041402,https: //doi.org/10.1145/3041402

work page doi:10.1145/3041402 2017
[22]

Vassilev, P.A

Ho, H., Ouaknine, J.: The cyclic-routing UAV problem is pspace-complete. In: Pitts, A.M. (ed.) Foundations of Software Science and Computation Structures - 18th International Con- ference, FoSSaCS 2015, Held as Part of the European Joint Conferences on Theory and Prac- tice of Software, ETAPS 2015, London, UK, April 11-18, 2015. Proceedings. Lecture Notes...

work page doi:10.1007/978-3- 2015
[23]

In: Megow, N., Smith, A.D

H¨ ohne, F., van Stee, R.: A 10/7-approximation for discrete bamboo garden trim- ming and continuous trimming on star graphs. In: Megow, N., Smith, A.D. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Tech- niques, APPROX/RANDOM 2023, September 11-13, 2023, Atlanta, Georgia, USA. LIPIcs, vol. 275, pp. 16:1–16:19. Schlos...

work page doi:10.4230/lipics.approx/random.2023.16 2023
[24]

InProceedings of the 22nd Hawaii International Conference of System Science

Holte, R., Mok, A., Rosier, L., Tulchinsky, I., Varvel, D.: The pinwheel: a real-time schedul- ing problem. In: [1989] Proceedings of the Twenty-Second Annual Hawaii International Con- ference on System Sciences. Volume II: Software Track. vol. 2, pp. 693–702 vol.2 (1989). https://doi.org/10.1109/HICSS.1989.48075

work page doi:10.1109/hicss.1989.48075 1989
[25]

Holte, R., Rosier, L.E., Tulchinsky, I., Varvel, D.A.: Pinwheel scheduling with two dis- tinct numbers. Theor. Comput. Sci.100(1), 105–135 (1992). https://doi.org/10.1016/0304- 3975(92)90365-M,https://doi.org/10.1016/0304-3975(92)90365-M

work page doi:10.1016/0304- 1992
[26]

Hulett, H., Will, T.G., Woeginger, G.J.: Multigraph realizations of degree se- quences: Maximization is easy, minimization is hard. Oper. Res. Lett.36(5), 594– 596 (2008). https://doi.org/10.1016/J.ORL.2008.05.004,https://doi.org/10.1016/j.orl. 2008.05.004

work page doi:10.1016/j.orl.2008.05.004 2008
[27]

CoRR abs/1410.7237(2014),http://arxiv.org/abs/1410.7237

Jacobs, T., Longo, S.: A new perspective on the windows scheduling problem. CoRR abs/1410.7237(2014),http://arxiv.org/abs/1410.7237

work page arXiv 2014
[28]

CoRRabs/2507.11681(2025)

Kanellopoulos, S., Pergaminelis, C., Kokkou, M., Markou, E., Pagourtzis, A.: Fi- nite pinwheel scheduling: the k-visits problem. CoRRabs/2507.11681(2025). https://doi.org/10.48550/ARXIV.2507.11681,https://doi.org/10.48550/arXiv.2507. 11681

work page doi:10.48550/arxiv.2507.11681 2025
[29]

In: Larsen, K.G., Saha, B

Kanellopoulos, S., Pergaminelis, C., Kokkou, M., Markou, E., Pagourtzis, A.: Finite pinwheel scheduling: the k-visits problem. In: Larsen, K.G., Saha, B. (eds.) Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026. pp. 355–371. SIAM (2026). https://doi.org/10.1137/1.9781611978971.1...

work page doi:10.1137/1.9781611978971.16 2026
[30]

In: Mohar, B., Shinkar, I., O’Donnell, R

Kawamura, A.: Proof of the density threshold conjecture for pinwheel scheduling. In: Mohar, B., Shinkar, I., O’Donnell, R. (eds.) Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024. pp. 1816–

2024
[31]

https://doi.org/10.1145/3618260.3649757,https://doi.org/10.1145/ 3618260.3649757

ACM (2024). https://doi.org/10.1145/3618260.3649757,https://doi.org/10.1145/ 3618260.3649757

work page doi:10.1145/3618260.3649757 2024
[32]

In: Finocchi, I., Georgiadis, L

Kawamura, A., Kobayashi, Y., Kusano, Y.: Pinwheel covering. In: Finocchi, I., Georgiadis, L. (eds.) Algorithms and Complexity - 14th International Conference, CIAC 2025, Rome, Italy, June 10-12, 2025, Proceedings, Part II. Lecture Notes in Computer Science, vol. 15680, pp. 185–199. Springer (2025). https://doi.org/10.1007/978-3-031-92935-9 12,https://doi....

work page doi:10.1007/978-3-031-92935-9 2025
[33]

Kleinberg, R., Mishra, A.: NP-hardness and a PTAS for the pinwheel problem (2026),https: //arxiv.org/abs/2604.13974

work page internal anchor Pith review Pith/arXiv arXiv 2026
[34]

In: Chen, H., Hon, W., Tsai, M

Kobayashi, Y., Lin, B.: Hardness and fixed parameter tractability for pinwheel schedul- ing problems. In: Chen, H., Hon, W., Tsai, M. (eds.) 36th International Sympo- sium on Algorithms and Computation, ISAAC 2025, Tainan, Taiwan, December 7-10,

2025
[35]

LIPIcs, vol. 359, pp. 47:1–47:15. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Infor- matik (2025). https://doi.org/10.4230/LIPICS.ISAAC.2025.47,https://doi.org/10.4230/ LIPIcs.ISAAC.2025.47 31

work page doi:10.4230/lipics.isaac.2025.47 2025
[36]

Algorithmica19(4), 411–426 (1997)

Lin, S., Lin, K.: A pinwheel scheduler for three distinct numbers with a tight schedulability bound. Algorithmica19(4), 411–426 (1997). https://doi.org/10.1007/PL00009181,https:// doi.org/10.1007/PL00009181

work page doi:10.1007/pl00009181 1997
[37]

In: Proceedings of the 13th Annual IEEE Conference on Computational Complexity, Buffalo, New York, USA, June 15-18, 1998

Marathe, M.V., III, H.B.H., Rosenkrantz, D.J., Stearns, R.E.: Theory of periodically speci- fied problems: Complexity and approximability. In: Proceedings of the 13th Annual IEEE Conference on Computational Complexity, Buffalo, New York, USA, June 15-18, 1998. p. 106. IEEE Computer Society (1998). https://doi.org/10.1109/CCC.1998.694596,https: //doi.org/1...

work page doi:10.1109/ccc.1998.694596 1998
[38]

In: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

Mishra, A.: An optimal density bound for discretized point patrolling. In: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 2846–2875. SIAM (2026),https://epubs.siam.org/doi/abs/10.1137/1.9781611978971.105

work page doi:10.1137/1.9781611978971.105 2026
[39]

In: Aho, A.V

Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. In: Aho, A.V. (ed.) Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA. pp. 345–354. ACM (1987). https://doi.org/10.1145/28395.383347, https://doi.org/10.1145/28395.383347

work page doi:10.1145/28395.383347 1987
[40]

Addison-Wesley (1994)

Papadimitriou, C.H.: Computational complexity. Addison-Wesley (1994)

1994
[41]

Papadimitriou, C.H., Yannakakis, M.: The complexity of restricted spanning tree problems. J. ACM29(2), 285–309 (1982). https://doi.org/10.1145/322307.322309,https://doi.org/10. 1145/322307.322309

work page doi:10.1145/322307.322309 1982
[42]

Yu, W., Hoogeveen, H., Lenstra, J.K.: Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard. J. Sched.7(5), 333–348 (2004). https://doi.org/10.1023/B:JOSH.0000036858.59787.C2,https://doi.org/10.1023/B:JOSH. 0000036858.59787.c2 32 A Minimizing the function for the density threshold of2-Visits We seek to find the min...

work page doi:10.1023/b:josh.0000036858.59787.c2 2004
[43]

Case 4:y→∞

Hence, in this case, the infimum is achieved when x→∞, y= √ 2−1 2 ·x+1 2 and is equal to limx→∞ ( f ( x, √ 2−1 2 ·x+1 2 )) = limx→∞ (√ 2−1 2 + 1 2x + 1√ 2 ) = √ 2−1 2. Case 4:y→∞. Sincex≥2y−1, it must also bex→∞in this case. Since we have already computed the infimum forx→∞in the previous case, this case can be skipped. The smallest value out of the four ...