Primal-Dual Online Algorithms for the Parking Permit Problem
For researchers in online algorithms, this provides a simpler and tighter analysis of a classic problem, improving upon previous reduction-based approaches.
The authors solve the Parking Permit Problem (PPP) using primal-dual methods, achieving exact deterministic and near-optimal randomized competitive ratios, with near-matching lower bounds.
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.