Problemas de bilhetes de estacionamento e projeto de redes com arrendamento

Author(s)

Murilo Santos De Lima

• Document type: Doctoral Thesis
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2018-05-11

Examining board members

Orlando Lee; Aritanan Borges Garcia Gruber; Marco Serpa Molinaro; Eduardo Candido Xavier; Lehilton Lelis Chaves Pedrosa

• Advisor: Mário César San Felice; Orlando Lee

Abstract

In traditional optimization problems, we can think that a solution is built by acquiring resources that persist in time. In contrast, in the leasing optimization model, we assume that resources may be leased for different lengths of time and that, due to economies of scale, it is more cost-effective to lease a resource for longer periods. This model has received some attention recently, since it models problems such as cloud resource allocation. In this thesis, we study the parking permit problem, which is the seminal leasing problem, and we propose some generalizations. The first is the multi parking permit problem, which is a generalization with multiple identical resources. 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 asymptotically optimal deterministic and randomized online algorithms. The second variant we propose is the group parking permit problem, a rent-or-buy generalization for which we give an 8-approximation algorithm and a deterministic competitive online algorithm. The complexity of this problem is open, but we believe it is weakly NP-hard. Finally, we study the 2D parking permit problem, proposed by Hu, Ludwig, Richa and Schmid~(2015). They presented a constant approximation algorithm and a deterministic competitive online algorithm for the hierarchical version of the problem, but those algorithms have pseudo-polynomial running time. We show how to turn their algorithms into polynomial time. We also show that their original pseudo-polynomial offline algorithm works for the general version of the 2D parking permit problem, which we prove to be NP-hard. Those results yield approximation and competitive online algorithms for leasing variants of the Steiner network problem, the rent-or-buy problem, and the buy-at-bulk network design problem, by using the technique of approximating a finite metric by a tree metric. In particular, we improve the previous best approximation algorithm for the leasing version of the multi-commodity rent-or-buy-problem. We also review approximation algorithms for the facility location problem with penalties and the facility leasing problem, and we propose a 3-approximation algorithm for the facility leasing problem with penalties. Finally, we review approximation and competitive online algorithms for the connected facility location problem. Then we propose four leasing variants of this problem, and we give approximation and competitive online algorithms for each of them when the (smallest) scale factor is 1. We also discuss why some classical algorithms for the connected facility location problem and the available analysis techniques in the literature do not suffice to obtain good algorithms for the leasing variants when the (smallest) scale factor is not a constant (AU)

• FAPESP's process: 14/18781-1 - Dynamic network design
• Grantee: Murilo Santos de Lima
• Support Opportunities: Scholarships in Brazil - Doctorate