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

zbMATH Keywords

approximation algorithmfacility locationbound-factor revealing linear program

Mathematics Subject Classification ID

Quadratic programming (90C20) Linear programming (90C05) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items (12)

An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties ⋮ An improved approximation algorithm for squared metric \(k\)-facility location ⋮ Clustering through continuous facility location problems ⋮ Approximation algorithm for squared metric facility location problem with nonuniform capacities ⋮ Approximation algorithm for squared metric two-stage stochastic facility location problem ⋮ \(\mathrm{M}^p\)UFLP: universal facility location problem in the \(p\)-th power of metric space ⋮ Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties ⋮ Local search approximation algorithms for the sum of squares facility location problems ⋮ Approximating the \(\tau\)-relaxed soft capacitated facility location problem ⋮ A local search approximation algorithm for a squared metric \(k\)-facility location problem ⋮ Maximum stable matching with one-sided ties of bounded length ⋮ Improved approximation algorithms for solving the squared metric \(k\)-facility location problem

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