A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems
DOI10.1007/s10107-014-0821-xzbMath1369.90143arXiv1111.1672OpenAlexW2016301092MaRDI QIDQ747779
Flávio K. Miyazawa, Lehilton L. C. Pedrosa, Luis A. A. Meira, Cristina G. Fernandes
Publication date: 19 October 2015
Published in: Mathematical Programming. Series A. Series B, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1111.1672
Quadratic programming (90C20) Linear programming (90C05) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Approximation algorithms (68W25)
Related Items (12)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A 1.488 approximation algorithm for the uncapacitated facility location problem
- A constant-factor approximation algorithm for the k -median problem (extended abstract)
- Approximation Algorithms for Metric Facility Location Problems
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- A new greedy approach for facility location problems
- Heuristics for the fixed cost median problem
- Greedy Strikes Back: Improved Facility Location Algorithms
- Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
- Online bipartite matching with random arrivals
- An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
This page was built for publication: A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems