Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Group parking permit problems

Texto completo
Autor(es):
de Lima, Murilo Santos [1] ; San Felice, Mario Cesar [2] ; Lee, Orlando [3]
Número total de Autores: 3
Afiliação do(s) autor(es):
[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
Número total de Afiliações: 3
Tipo de documento: Artigo Científico
Fonte: DISCRETE APPLIED MATHEMATICS; v. 281, n. SI, p. 172-194, JUL 15 2020.
Citações Web of Science: 0
Resumo

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)

Processo FAPESP: 14/18781-1 - Projeto de redes dinâmico
Beneficiário:Murilo Santos de Lima
Linha de fomento: Bolsas no Brasil - Doutorado
Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
Beneficiário:Flávio Keidi Miyazawa
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 17/11382-2 - Algoritmos Online e de Aproximação para Clusterização e Projeto de Redes
Beneficiário:Mário César San Felice
Linha de fomento: Bolsas no Brasil - Pós-Doutorado