A note on LP-based approximation algorithms for capacitated facility location problem

DOI10.1016/J.TCS.2022.08.002MaRDI QIDQ2172603zbMATH OpenOpenAlexWikidataFDO

Authors Runjie Miao, Jinjiang Yuan

Publication date 16 September 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2022.08.002

zbMATH Keywords

approximation algorithmcapacitated facility location problemlinear program

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Integer Programming and Combinatorial Optimization
• LP-based approximation algorithms for capacitated facility location
• LP-based approximation for uniform capacitated facility location problem
• An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties
• LP-based algorithms for capacitated facility location

Cites work

• A 3-approximation algorithm for the facility location problem with uniform capacities
• A 5-approximation for capacitated facility location
• Algorithms - ESA 2003
• Analysis of a Local Search Heuristic for Facility Location Problems
• Improved approximation algorithm for universal facility location problem with linear penalties
• Improved approximation algorithms for capacitated facility location problems
• Improved approximation algorithms for the facility location problems with linear/submodular penalties
• Improved local search for universal facility location
• LP-based algorithms for capacitated facility location
• LP-based approximation algorithms for capacitated facility location

Cited in

(4)

• An LP-rounding based algorithm for a uniform capacitated facility location problem with penalties
• An approximate cost recovery scheme for the k-product facility location game with penalties
• Approximation algorithms for the airport and railway problem
• Approximation algorithms for the airport and railway problem

This page was built for publication: A note on LP-based approximation algorithms for capacitated facility location problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2172603)