Affiliation:  ^{[1]} Reykjavik Univ, Sch Comp Sci, Menntavegi 1, IS101 Reykjavik  Iceland
^{[2]} Fed Univ Sao Carlos UFSCar, Dept Comp, Rod Washington Luis, Km 235, Caixa Postal 676, BR13565905 Sao Carlos, SP  Brazil
^{[3]} Univ Estadual Campinas, UNICAMP, Inst Comp, Av Albert Einstein 1251, Cidade Univ, BR13083852 Campinas, SP  Brazil
Total Affiliations: 3

In this paper we study some generalizations of the parking permit problem (Meyerson, FOCS'05), in which we are given a demand r(t) [0, 1] for instant of time t = 0 ,..., T1, along with K permit types with lengths of time delta(1),...,delta(K) and subadditive costs. A permit is a pair (k, t). {[}K] x Z(+), and it covers interval {[}t, t + delta(k)). We wish to find a minimumcost set of permits that covers every t with r(t) = 1. Meyerson gave deterministic O(K)competitive and randomized O(lg K)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 (r(t) is an element of 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 approximationpreserving reduction yields a deterministic O(K)competitive online algorithm and a randomized O(lg K)competitive online algorithm. For a leasing variant of the Steiner network problem, these results imply a O(lg n)approximation algorithm and a O(lg K lg vertical bar V vertical bar)competitive online algorithm, where n is the number of requests and vertical bar V vertical bar 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 gamma(k) and covering one demand per instant of time, or a group permit, which costs M . gamma(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 8approximation 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 rentorbuy 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 pseudopolynomial 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 buyatbulk network design problem. We also show that their original pseudopolynomial offline algorithm works for a more general version of the 2D parking permit problem, which we prove to be NPhard. (c) 2019 Elsevier B.V. All rights reserved. (AU) 