Advanced search
Start date
Betweenand
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Group parking permit problems

Full text
Author(s):
de Lima, Murilo Santos [1] ; San Felice, Mario Cesar [2] ; Lee, Orlando [3]
Total Authors: 3
Affiliation:
[1] Reykjavik Univ, Sch Comp Sci, Menntavegi 1, IS-101 Reykjavik - Iceland
[2] Fed Univ Sao Carlos UFSCar, Dept Comp, Rod Washington Luis, Km 235, Caixa Postal 676, BR-13565905 Sao Carlos, SP - Brazil
[3] Univ Estadual Campinas, UNICAMP, Inst Comp, Av Albert Einstein 1251, Cidade Univ, BR-13083852 Campinas, SP - Brazil
Total Affiliations: 3
Document type: Journal article
Source: DISCRETE APPLIED MATHEMATICS; v. 281, n. SI, p. 172-194, JUL 15 2020.
Web of Science Citations: 0
Abstract

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 ,..., T-1, along with K permit types with lengths of time delta(1),...,delta(K) and sub-additive costs. A permit is a pair (k, t). {[}K] x Z(+), and it covers interval {[}t, t + delta(k)). We wish to find a minimum-cost 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 approximation-preserving 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 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. (c) 2019 Elsevier B.V. All rights reserved. (AU)

FAPESP's process: 14/18781-1 - Dynamic network design
Grantee:Murilo Santos de Lima
Support type: Scholarships in Brazil - Doctorate
FAPESP's process: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
Grantee:Flávio Keidi Miyazawa
Support type: Research Projects - Thematic Grants
FAPESP's process: 17/11382-2 - Online and Approximation Algorithms for Clustering and Network Design
Grantee:Mário César San Felice
Support type: Scholarships in Brazil - Post-Doctorate