On a Leasing Variant of the Online Connected Facility Location Problem
Resumo
In the leasing optimization model, resources are leased for K different time periods, instead of being acquired for unlimited duration. The goal is to use these temporary resources to maintain a dynamic infrastructure that serves n requests while minimizing the total cost. We propose and study a leasing variant of the online connected facility location problem, which we call the online connected facility leasing problem. In this problem each client that arrives must be connected to a temporary facility, which in turn must be connected to a root facility using permanent edges. We present an algorithm that is O(K · lg n)-competitive if the scaling factor is M = 1.
Referências
Abshoff, S., Kling, P., Markarian, C., auf der Heide, F. M., and Pietrzyk, P. (2015). Towards the price of leasing online. Journal of Combinatorial Optimization, pages 1–20.
Anthony, B. M. and Gupta, A. (2007). Infrastructure leasing problems. In Integer Programming and Combinatorial Optimization, pages 424–438. Springer.
Grandoni, F. and Rothvoß, T. (2011). Approximation algorithms for single and multi-commodity connected facility location. In G¨unl¨uk, O. and Woeginger, G. J., editors, Integer Programming and Combinatoral Optimization, volume 6655 of Lecture Notes in Computer Science, pages 248–260. Springer Berlin Heidelberg.
Imase, M. and Waxman, B. M. (1991). Dynamic Steiner tree problem. SIAM Journal on Discrete Mathematics, 4(3):369–384.
Meyerson, A. (2005). The parking permit problem. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pages 274–282.
Nagarajan, C. and Williamson, D. P. (2013). Offline and online facility leasing. Discrete Optimization, 10(4):361–370.
San Felice, M. C., Williamson, D. P., and Lee, O. (2016). A randomized O(log n)-competitive algorithm for the online connected facility location. Algorithmica, pages 1–19.
Umboh, S. (2015). Online network design algorithms via hierarchical decompositions. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1373–1387.
Anthony, B. M. and Gupta, A. (2007). Infrastructure leasing problems. In Integer Programming and Combinatorial Optimization, pages 424–438. Springer.
Grandoni, F. and Rothvoß, T. (2011). Approximation algorithms for single and multi-commodity connected facility location. In G¨unl¨uk, O. and Woeginger, G. J., editors, Integer Programming and Combinatoral Optimization, volume 6655 of Lecture Notes in Computer Science, pages 248–260. Springer Berlin Heidelberg.
Imase, M. and Waxman, B. M. (1991). Dynamic Steiner tree problem. SIAM Journal on Discrete Mathematics, 4(3):369–384.
Meyerson, A. (2005). The parking permit problem. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pages 274–282.
Nagarajan, C. and Williamson, D. P. (2013). Offline and online facility leasing. Discrete Optimization, 10(4):361–370.
San Felice, M. C., Williamson, D. P., and Lee, O. (2016). A randomized O(log n)-competitive algorithm for the online connected facility location. Algorithmica, pages 1–19.
Umboh, S. (2015). Online network design algorithms via hierarchical decompositions. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1373–1387.
Publicado
04/07/2016
Como Citar
DE LIMA, Murilo Santos; SAN FELICE, Mário César; LEE, Orlando.
On a Leasing Variant of the Online Connected Facility Location Problem. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 1. , 2016, Porto Alegre.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 836-839.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2016.9837.
