Pith. sign in

REVIEW 5 minor 52 references

Primal-Dual Online Algorithms for the Parking Permit Problem

T0 review · 0 major / 5 minor · reviewed 2026-07-10 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The parking permit problem has exact deterministic competitive ratio K and randomized ratio ln K + ln ln K up to an additive constant.

desk verdict Clean primal-dual treatment that pins the deterministic ratio at exactly K and shrinks the randomized gap to an additive constant of 2. read the letter →

arxiv 2607.08262 v1 pith:ISKSN5K3 submitted 2026-07-09 cs.DS

Christian Coester , Alex Turoczy This is my paper · ORCID
classification cs.DS
keywords onlinealgorithmscompetitiveanalysisprimal-dualparkingpermitproblemskirentalleasingcoveringLPs
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The parking permit problem asks how to buy time-limited parking permits of different lengths and costs when rainy days arrive one by one and you do not know future weather. Earlier algorithms first reduced the problem to a special laminar case and paid a constant-factor loss in competitive ratio. This paper works directly with the original non-laminar formulation via a primal-dual scheme. It proves that the deterministic competitive ratio is exactly K: a simple online algorithm matches a matching lower bound. For randomized algorithms the same framework yields an upper bound of ln K + ln ln K + O(1) and a nearly matching lower bound that differs only by an additive constant of 2. The key technical step is to update the sum of the relevant primal variables multiplicatively rather than each variable separately, so that the competitive ratio depends only on the number of permit types K even though the linear program has unbounded row sparsity.

What carries the argument

A primal-dual update that multiplies the sum of the covering variables for each permit type by an exponential of the dual variable; this produces a competitive ratio that is a function of K alone, bypassing the unbounded row-sparsity of the non-laminar covering LP.

What would settle it

Compute the exact competitive ratio of the fractional laminar PPP for successive small K (say K = 3,4,5) by solving the continuous optimal-control problem numerically and check whether the obtained values coincide with the recurrence S_K within the claimed o(1) error.

Watch

Extended reading notes

Core claim

The deterministic competitive ratio of the online parking permit problem is exactly K, and any randomized online algorithm has competitive ratio at least S_K = ln K + ln ln K + o(1) while a primal-dual algorithm achieves at most ln K + ln ln K + O(1).

Load-bearing premise

The continuous limit taken when the number of subintervals becomes infinite is assumed to preserve the exact competitive ratio of the discrete laminar instance, and the differential equation is solved under a greedy-saturation claim rather than a full optimality certificate.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper revisits the classic Parking Permit Problem (PPP) via the primal-dual framework, working directly with the non-laminar formulation rather than reducing to the laminar case. It gives a simple deterministic algorithm that is exactly K-competitive (matching a new lower bound of K) and a randomized primal-dual algorithm whose competitive ratio is at most ln K + ln ln K + O(1), together with a matching lower bound of S_K = ln K + ln ln K + o(1) obtained by a recursive ski-rental construction. An online rounding lemma converts the fractional solution into a randomized integral solution without loss.

Significance. If correct, the results close long-standing constant-factor gaps for a foundational leasing problem: the deterministic ratio is settled exactly, and the randomized ratio is pinned down to an additive constant. The direct (non-laminar) primal-dual analysis and the online rounding that preserves the fractional cost are clean technical contributions that improve on Meyerson’s original bounds and on subsequent laminar reductions. The work is self-contained, elementary, and immediately usable for related leasing problems.

minor comments (5)
  1. In the proof of Lemma 7 (Claim 2), the derivative comparison is written with a sum that equals 1 + 1/ln K only after the while-loop invariant is used; a one-sentence reminder that the covering mass is still strictly less than 1 would make the inequality immediate.
  2. Lemma 11 invokes a continuous limit M ≫ N ≫ 1. While the o(1) terms already absorb any vanishing discrepancy, a short remark that the discrete recurrence converges to the same differential equation (or a citation to a standard continuous-time ski-rental argument) would remove any residual doubt.
  3. Table 1 lists the new deterministic upper bound as K ln K + ln ln K + O(1); that expression belongs only to the randomized column. The deterministic entry should simply read “K”.
  4. Algorithm 2 uses the same symbol x_{k,t} for both the fractional variables being updated and the final solution; a brief clarification that the update is performed only while the covering sum is less than 1 would improve readability.
  5. The phrase “within an additive constant” appears in the abstract and introduction; stating the precise additive gap (at most 2 + o(1)) once would be more informative.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: competitive ratios follow from explicit primal-dual updates, weak duality, and independent adversarial constructions.

full rationale

The paper derives its claims from first principles without definitional loops or fitted parameters. Deterministic upper bound (Lemma 4 / Algorithm 1) charges each purchase of type k to a dual mass of C_k that is forced by the continuous increase of y_t until a dual constraint saturates; weak duality then yields the factor K. The matching lower bound (Lemma 5) is an explicit inductive adversarial sequence on carefully chosen costs and durations, with no reference to the algorithm's analysis. Randomized upper bound (Lemma 7 / Algorithm 2) multiplies the sum of relevant primal variables by an exponential of the dual; the resulting differential inequality and dual-violation factor ln(1+K ln K) are computed directly and combined with weak duality. Online rounding (Lemma 8) preserves expectation by a straightforward induction on the mass of expiring permits. The lower-bound recurrence S_K (Lemma 11) is obtained by recursively embedding ski-rental lower bounds inside a laminar instance and solving the continuous relaxation of the resulting differential equation; Lemma 10 then shows the asymptotic form of that recurrence by elementary integral comparison, independently of the upper-bound algorithm. No quantity is defined in terms of a later-claimed prediction, no uniqueness theorem is imported from the authors' prior work, and all self-citations are ordinary bibliographic references to classical results (ski rental, Buchbinder-Naor framework). The continuous-limit step M ≫ N ≫ 1 is an approximation argument whose error is absorbed into the already-stated o(1) term; it does not create a circular dependence.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

Pure theoretical paper. All claims rest on standard linear-programming duality, the definition of competitive ratio, and elementary analysis (induction, differential equations). No free parameters are fitted; no new physical or combinatorial entities are postulated beyond the problem statement itself.

assumptions (3)
  • standard math Weak duality of linear programs: any feasible dual is a lower bound on the optimal primal value.
    Invoked repeatedly to convert dual feasibility (or bounded violation) into competitive-ratio statements (e.g., end of Lemma 4, end of Lemma 7).
  • domain assumption Definition of competitive ratio: alg(I) ≤ ρ · opt(I) for every input sequence I.
    Standard online-algorithms framework used throughout Sections 2-3.
  • domain assumption Any randomized integral algorithm induces a fractional solution of equal expected cost by setting x_{k,t} to the purchase probability.
    Used to transfer the fractional lower bound of Lemma 11 to randomized algorithms (paragraph preceding Lemma 9).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Primal-Dual Online Algorithms for the Parking Permit Problem." pith.science (2026). https://pith.science/paper/ISKSN5K3

@misc{pith2026260708262,
  author       = {Pith},
  title        = {Pith review of: Primal-Dual Online Algorithms for the Parking Permit Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ISKSN5K3}},
  note         = {Machine review of arXiv:2607.08262}
}
read the original abstract

The Parking Permit Problem (PPP), first studied by Meyerson, is a classic online problem generalizing the ski rental problem. We re-examine the PPP using the primal-dual scheme, obtaining simple algorithms with superior performance guarantees. Unlike previous work, which relied on reductions that degraded competitive ratios, we work with the problem's structure directly. We also provide near-matching lower bounds. Using the primal-dual framework, we find the PPP's deterministic competitive ratio exactly, and the randomized competitive ratio within an additive constant.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

52 extracted references · 52 canonical work pages

  1. [1]

    46th Annual

    Adam Meyerson , title =. 46th Annual. 2005 , url =

    work page 2005

  2. [2]

    2017 , note =

    On Generalizations of the Parking Permit Problem and Network Leasing Problems , journal =. 2017 , note =. doi:https://doi.org/10.1016/j.endm.2017.10.039 , author =

    work page doi:10.1016/j.endm.2017.10.039 2017

  3. [3]

    2015 , pages =

    Hu, Xinhui and Ludwig, Arne and Richa, Andrea and Schmid, Stefan , booktitle =. 2015 , pages =

    work page 2015

  4. [4]

    Combinatorial Optimization and Applications: 8th International Conference, COCOA , pages =

    Abshoff, Sebastian and Markarian, Christine and Meyer auf der Heide, Friedhelm , title =. Combinatorial Optimization and Applications: 8th International Conference, COCOA , pages =. 2014 , doi =

    work page 2014

  5. [5]

    Proceedings of the 8th International Conference on Operations Research and Enterprise Systems,

    Christine Markarian and Friedhelm Meyer auf der Heide , title =. Proceedings of the 8th International Conference on Operations Research and Enterprise Systems,. 2019 , doi =

    work page 2019

  6. [6]

    Karlin and Mark S

    Anna R. Karlin and Mark S. Manasse and Lyle A. McGeoch and Susan S. Owicki , title =. Algorithmica , volume =. 1994 , doi =

    work page 1994

  7. [7]

    Mathematical Optimization Theory and Operations Research: 23rd International Conference, MOTOR , pages =

    Yaroslav, Kharchenko and Alexander, Kononov , title =. Mathematical Optimization Theory and Operations Research: 23rd International Conference, MOTOR , pages =. 2024 , url =. doi:10.1007/978-3-031-62792-7_8 , abstract =

    work page doi:10.1007/978-3-031-62792-7_8 2024

  8. [8]

    2025 , eprint=

    Learning-Augmented Online Covering Problems , author=. 2025 , eprint=

    work page 2025

Show all 52 references
  1. [9]

    , title =

    Guo, Chuan and Pleiss, Geoff and Sun, Yu and Weinberger, Kilian Q. , title =. Proceedings of the 34th International Conference on Machine Learning - Volume 70 , pages =. 2017 , publisher =

    2017

  2. [10]

    2016 , booktitle =

    Gal, Yarin and Ghahramani, Zoubin , title =. 2016 , booktitle =

    2016

  3. [11]

    2017 , booktitle =

    Lakshminarayanan, Balaji and Pritzel, Alexander and Blundell, Charles , title =. 2017 , booktitle =

    2017

  4. [12]

    1998 , isbn =

    Borodin, Allan and El-Yaniv, Ran , title =. 1998 , isbn =

    1998

  5. [13]

    2021 , booktitle =

    Dinitz, Michael and Im, Sungjin and Lavastida, Thomas and Moseley, Benjamin and Vassilvitskii, Sergei , title =. 2021 , booktitle =

    2021

  6. [14]

    and Magnanti, Thomas L

    Ahuja, Ravindra K. and Magnanti, Thomas L. and Orlin, James B. , title =. 1993 , publisher =

    1993

  7. [15]

    Lipnet: End-to-End Lipreading , journal =

    S, Jishnu and Antony, Anju , year =. Lipnet: End-to-End Lipreading , journal =

  8. [16]

    , title =

    Silver, David and Huang, Aja and Maddison, Chris et al. , title =. Nature , year =

  9. [17]

    Online metric algorithms with untrusted predictions , booktitle =

    Antonios Antoniadis and Christian Coester and Marek Eli. Online metric algorithms with untrusted predictions , booktitle =. 2020 , url =

    2020

  10. [18]

    1997 , url =

    Blum, Avrim and Burch, Carl , title =. 1997 , url =. doi:10.1145/267460.267475 , booktitle =

    1997 doi

  11. [19]

    Competitive k-server algorithms , journal =

    Amos Fiat and Yuval Rabani and Yiftach Ravid , abstract =. Competitive k-server algorithms , journal =. 1994 , issn =. doi:https://doi.org/10.1016/S0022-0000(05)80060-1 , url =

    1994 doi

  12. [20]

    Niv Buchbinder and Joseph Naor , title =. Found. Trends Theor. Comput. Sci. , volume =. 2009 , url =

    2009

  13. [21]

    Proceedings of the 35th International Conference on Machine Learning,

    Thodoris Lykouris and Sergei Vassilvitskii , title =. Proceedings of the 35th International Conference on Machine Learning,. 2018 , url =

    2018

  14. [22]

    CoRR , volume =

    Michael Mitzenmacher and Sergei Vassilvitskii , title =. CoRR , volume =. 2020 , url =. 2006.09123 , timestamp =

    2020 arXiv

  15. [23]

    Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montr

    Manish Purohit and Zoya Svitkina and Ravi Kumar , title =. Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montr. 2018 , url =

    2018

  16. [24]

    Proceedings of the 2020

    Dhruv Rohatgi , title =. Proceedings of the 2020. 2020 , url =

    2020

  17. [25]

    Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS , year =

    Antonios Antoniadis and Themis Gouleakis and Pieter Kleer and Pavel Kolev , title =. Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS , year =

    2020

  18. [26]

    Proceedings of the 2020

    Silvio Lattanzi and Thomas Lavastida and Benjamin Moseley and Sergei Vassilvitskii , title =. Proceedings of the 2020. 2020 , url =

    2020

  19. [27]

    11th Innovations in Theoretical Computer Science Conference,

    Michael Mitzenmacher , title =. 11th Innovations in Theoretical Computer Science Conference,. 2020 , url =

    2020

  20. [28]

    Feller, William , publisher =

  21. [29]

    Prophet Inequalities via the Expected Competitive Ratio , journal =

    Tomer Ezra and Stefano Leonardi and Rebecca Reiffenh. Prophet Inequalities via the Expected Competitive Ratio , journal =. 2025 , url =

    2025

  22. [30]

    1997 , isbn =

    Bertsimas, Dimitris and Tsitsiklis, John , title =. 1997 , isbn =

    1997

  23. [31]

    , title =

    Anthony, Martin and Bartlett, Peter L. , title =. 2009 , publisher =

    2009

  24. [32]

    Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems , pages =

    Jamie Morgenstern and Tim Roughgarden , title =. Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems , pages =. 2015 , url =

    2015

  25. [33]

    2012 , publisher=

    Convergence of Stochastic Processes , author=. 2012 , publisher=

    2012

  26. [34]

    Li and Benjamin Moseley and Gabriel Visotsky , title =

    Lin An and Andrew A. Li and Benjamin Moseley and Gabriel Visotsky , title =. CoRR , volume =. 2024 , url =. doi:10.48550/ARXIV.2402.13530 , eprinttype =. 2402.13530 , timestamp =

    2024 doi arXiv

  27. [35]

    , biburl =

    Abramowitz, Milton and Stegun, Irene A. , biburl =

  28. [36]

    Ford, L. R. and Fulkerson, D. R. , year=. Maximal Flow Through a Network , volume=. doi:10.4153/CJM-1956-045-5 , journal=

    1956 doi

  29. [37]

    Paths, Trees, and Flowers , volume=

    Edmonds, Jack , year=. Paths, Trees, and Flowers , volume=. doi:10.4153/CJM-1965-045-4 , journal=

    1965 doi

  30. [38]

    , title =

    Edmonds, Jack and Karp, Richard M. , title =. 1972 , publisher =. doi:10.1145/321694.321699 , journal =

    1972 doi

  31. [39]

    Journal of Research of the National Bureau of Standards B , volume=

    Maximum matching and a polyhedron with 0,1-vertices , author=. Journal of Research of the National Bureau of Standards B , volume=

  32. [40]

    Combinatorica , volume=

    On submodular function minimization , author=. Combinatorica , volume=. 1985 , publisher=

    1985

  33. [41]

    , title =

    Hochbaum, Dorit S. , title =. SIAM Journal on Computing , volume =

  34. [42]

    On the ratio of optimal integral and fractional covers , year =

    Lov\'. On the ratio of optimal integral and fractional covers , year =. Discrete Math. , month = jan, pages =. doi:10.1016/0012-365X(75)90058-8 , abstract =

    doi

  35. [43]

    and Williamson, David P

    Goemans, Michel X. and Williamson, David P. , title =. SIAM Journal on Computing , volume =. 1995 , doi =

    1995

  36. [44]

    , title =

    Agrawal, Ajit and Klein, Philip and Ravi, R. , title =. 1991 , url =. doi:10.1145/103418.103437 , booktitle =

    1991 doi

  37. [45]

    Algorithms -

    Niv Buchbinder and Joseph Naor , title =. Algorithms -. 2005 , url =

    2005

  38. [46]

    47th Annual

    Niv Buchbinder and Joseph Naor , title =. 47th Annual. 2006 , url =

    2006

  39. [47]

    Karp and Umesh V

    Richard M. Karp and Umesh V. Vazirani and Vijay V. Vazirani , title =. Proceedings of the 22nd Annual. 1990 , url =

    1990

  40. [48]

    Daniel Dominic Sleator and Robert Endre Tarjan , title =. Commun. 1985 , url =. doi:10.1145/2786.2793 , timestamp =

    1985 doi

  41. [49]

    Devanur and Kamal Jain and Robert D

    Nikhil R. Devanur and Kamal Jain and Robert D. Kleinberg , title =. Proceedings of the Twenty-Fourth Annual. 2013 , url =

    2013

  42. [50]

    Online Algorithms for Covering and Packing Problems with Convex Objectives , booktitle =

    Yossi Azar and Niv Buchbinder and T. Online Algorithms for Covering and Packing Problems with Convex Objectives , booktitle =. 2016 , url =

    2016

  43. [51]

    Nikhil Bansal and Niv Buchbinder and Joseph Naor , title =. J. 2012 , url =. doi:10.1145/2339123.2339126 , timestamp =

    2012 doi

  44. [52]

    Forty-third International Conference on Machine Learning,

    Christian Coester and Alexa Tudose and Alexander Turoczy , title =. Forty-third International Conference on Machine Learning,

Pith tools

Reviewed July 10, 2026 · model on record in the stance chip above.