Facility Leasing with Penalties
Resumo
In this paper we study the facility leasing problem with penalties. We present a 3-approximation primal-dual algorithm, based on the algorithms by Nagarajan and Williamson for the facility leasing problem and by Charikar, Khuller, Mount and Narasimhan for the facility location problem with penalties.
Referências
Charikar, M., Khuller, S., Mount, D. M., and Narasimhan, G. (2001). Algorithms for facility location problems with outliers. In SODA’01: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 642–651.
Li, S. (2013). A 1.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222:45–58.
Li, Y., Du, D., Xiu, N., and Xu, D. (2015). Improved approximation algorithms for the facility location problems with linear/submodular penalties. Algorithmica, 73(2):460–482.
Nagarajan, C. and Williamson, D. P. (2013). Offline and online facility leasing. Discrete Optimization, 10(4):361–370.
Sviridenko, M. (2002). An improved approximation algorithm for the metric uncapacitated facility location problem. In Integer Programming and Combinatorial Optimization, volume 2337 of Lecture Notes in Computer Science, pages 240–257.
Li, S. (2013). A 1.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222:45–58.
Li, Y., Du, D., Xiu, N., and Xu, D. (2015). Improved approximation algorithms for the facility location problems with linear/submodular penalties. Algorithmica, 73(2):460–482.
Nagarajan, C. and Williamson, D. P. (2013). Offline and online facility leasing. Discrete Optimization, 10(4):361–370.
Sviridenko, M. (2002). An improved approximation algorithm for the metric uncapacitated facility location problem. In Integer Programming and Combinatorial Optimization, volume 2337 of Lecture Notes in Computer Science, pages 240–257.
Publicado
02/07/2017
Como Citar
DE LIMA, Murilo Santos; SAN FELICE, Mário César; LEE, Orlando.
Facility Leasing with Penalties. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 2. , 2017, São Paulo.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2017
.
p. 45-48.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2017.3188.
