Group parking permit problems

In this paper we study some generalizations of the parking permit problem (Meyerson, FOCS’05), in which we are given a demand rt∈{0,1} for instant of time t=0,…,T−1, along with K permit types with lengths of time δ1,…,δK and sub-additive costs. A permit is a pair (k,tˆ)∈[K]×Z+, and it covers interval [tˆ,tˆ+δk). We wish to find a minimum-cost set of permits that covers every t with rt=1. Meyerson gave deterministic O(K)-competitive and randomized O(lgK)-competitive online algorithms for this problem, as well as matching lower bounds. The first variant we propose is the multi parking permit problem, in which an arbitrary demand is given at each instant (rt∈Z+) and we may buy multiple permits to serve it. We prove that the offline version of this problem can be solved in polynomial time, and we show how to reduce it to the parking permit problem, while losing a constant cost factor. This approximation-preserving reduction yields a deterministic O(K)-competitive online algorithm and a randomized O(lgK)-competitive online algorithm. For a leasing variant of the Steiner network problem, these results imply a O(lgn)-approximation algorithm and a O(lgKlg|V|)-competitive online algorithm, where n is the number of requests and |V| is the size of the input metric. The second variant we propose is the group parking permit problem, in which we also have an arbitrary demand for each instant, and each permit of type k can be either a single permit, costing γk and covering one demand per instant of time, or a group permit, which costs M⋅γk for some constant M≥1 and covers an arbitrary number of demands in the interval covered by this permit. (I.e., group permits have infinite capacity.) For this version of the problem, we give an 8-approximation algorithm and a deterministic O(K)-competitive online algorithm. The first result yields an improvement on the previous best approximation algorithm for the leasing version of the rent-or-buy problem. Finally, we study the 2D parking permit problem, proposed by Hu, Ludwig, Richa and Schmid (2015), in which a permit type is defined by a length of time and an integer capacity. They presented a constant approximation algorithm and a deterministic O(K)-competitive online algorithm for a hierarchical version of the problem, but those algorithms have pseudo-polynomial running time. We show how to turn their algorithms into polynomial time algorithms. Moreover, these results yield approximation and competitive online algorithms for a hierarchical leasing version of the buy-at-bulk network design problem. We also show that their original pseudo-polynomial offline algorithm works for a more general version of the 2D parking permit problem, which we prove to be NP-hard.