On Generalizations of the Parking Permit Problem and Network Leasing Problems

We propose a variant of the parking permit problem, called multi parking permit problem, in which an arbitrary demand is given at each instant and one may buy multiple permits to serve it. We show how to reduce this problem to the parking permit problem, while losing a constant cost factor. We obtain a 4-approximation algorithm and, for the online setting, a deterministic O(K)-competitive algorithm and a randomized O(lg⁡K)-competitive algorithm, where K is the number of permit types. For a leasing variant of the Steiner network problem, these results imply O(lg n)-approximation and online O(lg⁡Klg⁡|V|)-competitive algorithms, where n is the number of requests and |V| is the size of the input metric. Also, our technique turns into polynomial-time the pseudo-polynomial algorithms by Hu, Ludwig, Richa and Schmid for the 2D parking permit problem. For a leasing variant of the buy-at-bulk network design problem, these results imply: (i) an algorithm which improves the best previous approximation, and (ii) the first competitive online algorithm.