etc2016-published.pdf (193.49 kB)
Download fileOn a Leasing Variant of the Online Connected Facility Location Problem
conference contribution
posted on 2020-05-21, 12:14 authored by Murilo Santos De Lima, Mário César San Felice, Orlando LeeIn 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.
Funding
In author order: Supported by FAPESP Proc. 2014/18781-1, and CNPq Proc. 142161/2014-4.†Supported by CAPES PNPD scholarship 1522390.‡Supported by CNPq Proc. 311373/2015-1, and CNPq Proc. 477692/2012-5.
History
Citation
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 do I Encontro de Teoria da Computação. Porto Alegre: Sociedade Brasileira de Computação, aug. 2018 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2016.9837.Source
2016: ANAIS DO I ENCONTRO DE TEORIA DA COMPUTAÇÃOVersion
- VoR (Version of Record)