Improved approximation algorithms for capacitated facility location problems

DOI10.1007/s10107-004-0524-9zbMath1079.90075OpenAlexW2149106399WikidataQ56519777 ScholiaQ56519777MaRDI QIDQ1771310

David P. Williamson, Fabián A. Chudak

Publication date: 19 April 2005

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-004-0524-9

zbMATH Keywords

location problempolynomial-time algorithm

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80)

Related Items (26)

Combinatorial approximation algorithms for the robust facility location problem with penalties ⋮ Approximation algorithms for hard capacitated \(k\)-facility location problems ⋮ Integrality gaps for strengthened linear relaxations of capacitated facility location ⋮ Finding a collective set of items: from proportional multirepresentation to group recommendation ⋮ Optimal Physician assignment and patient demand allocation in an outpatient care network ⋮ A note on LP-based approximation algorithms for capacitated facility location problem ⋮ A 3-approximation algorithm for the facility location problem with uniform capacities ⋮ Centrality of trees for capacitated \(k\)-center ⋮ Improved bounds for metric capacitated covering problems ⋮ The facility location problem with maximum distance constraint ⋮ Unnamed Item ⋮ A local search approximation algorithm for the uniform capacitated \(k\)-facility location problem ⋮ LP-Based Algorithms for Capacitated Facility Location ⋮ Capacitated Domination Problem ⋮ On the transportation problem with market choice ⋮ LP-based approximation algorithms for capacitated facility location ⋮ Towards flexible demands in online leasing problems ⋮ Local search algorithms for the red-blue median problem ⋮ Capacitated domination problem ⋮ Approximation algorithms for the transportation problem with market choice and related models ⋮ Heuristics for the dynamic facility location problem with modular capacities ⋮ Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems ⋮ 2-level station location for bike sharing ⋮ An approximation algorithm for the uniform capacitated \(k\)-means problem ⋮ Capacitated domination: problem complexity and approximation algorithms ⋮ The capacitated facility location problem with random input data

Cites Work

• Plant location with minimum inventory
• A threshold of ln n for approximating set cover
• Comments on the note of Frieze
• An analysis of approximations for maximizing submodular set functions—I
• Greedy Strikes Back: Improved Facility Location Algorithms
• On the hardness of approximating minimization problems
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Analysis of a Local Search Heuristic for Facility Location Problems
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Improved approximation algorithms for capacitated facility location problems