A 3-approximation algorithm for the facility location problem with uniform capacities

DOI10.1007/s10107-012-0565-4zbMath1274.90191OpenAlexW2025042641MaRDI QIDQ378101

Surabhi Jain, Neelima Gupta, Naveen Garg, Ankit Aggarwal, Anand Louis, Manisha Bansal, Shubham Gupta

Publication date: 11 November 2013

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

Full work available at URL: https://doi.org/10.1007/s10107-012-0565-4

zbMATH Keywords

local searchfacility locationapproximation algorithmsuniform capacities

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items

Approximation algorithms for hard capacitated \(k\)-facility location problems, Integrality gaps for strengthened linear relaxations of capacitated facility location, Approximation algorithms for two variants of correlation clustering problem, Bifactor approximation for location routing with vehicle and facility capacities, LP-based approximation for uniform capacitated facility location problem, A note on LP-based approximation algorithms for capacitated facility location problem, Approximation Algorithms for the Capacitated Min–Max Correlation Clustering Problem, Improved bounds for metric capacitated covering problems, Unnamed Item, Unnamed Item, A local search approximation algorithm for the uniform capacitated \(k\)-facility location problem, LP-Based Algorithms for Capacitated Facility Location, Respecting lower bounds in uniform lower and upper bounded facility location problem, On the cost of essentially fair clusterings, Easy capacitated facility location problems, with connections to lot-sizing, Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems, An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties, Constant factor approximation algorithm for uniform hard capacitated knapsack median problem, An approximation algorithm for the uniform capacitated \(k\)-means problem

Cites Work

• Improved approximation algorithms for capacitated facility location problems
• Analysis of a Local Search Heuristic for Facility Location Problems
• Local Search Heuristics for k-Median and Facility Location Problems
• A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
• Algorithms - ESA 2003
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques