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

Content Provider	Springer Nature Link
Author	Gupta, Neelima Garg, Naveen Aggarwal, Ankit Jain, Surabhi Gupta, Shubham Bansal, Manisha Louis, Anand
Copyright Year	2012
Abstract	We consider the facility location problem where each facility can serve at most U clients. We analyze a local search algorithm for this problem which uses only the operations of add, delete and swap and prove that any locally optimum solution is no more than 3 times the global optimum. This improves on a result of Chudak and Williamson who proved an approximation ratio of $${3+2\sqrt{2}}$$ for the same algorithm. We also provide an example which shows that any local search algorithm which uses only these three operations cannot achieve an approximation guarantee better than 3.
Ending Page	547
Page Count	21
Starting Page	527
File Format	PDF
ISSN	00255610
e-ISSN	14364646
Journal	Mathematical Programming
Issue Number	1-2
Volume Number	141
Language	English
Publisher	Springer Berlin Heidelberg
Publisher Date	2012-06-09
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Local search Approximation methods and heuristics Theoretical, Mathematical and Computational Physics Uniform capacities Discrete location and assignment Facility location Analysis of algorithms and problem complexity Mathematical Methods in Physics Calculus of Variations and Optimal Control; Optimization Mathematics of Computing Numerical Analysis Approximation algorithms Analysis of algorithms Combinatorics
Content Type	Text
Resource Type	Article
Subject	Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Local Search Heuristics for k-Median and Facility Location Problems

An efficient polynomial time approximation scheme for load balancing on uniformly related machines

LP-based approximation algorithms for capacitated facility location

A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems

Integrality gaps for strengthened linear relaxations of capacitated facility location

Integrated market selection and production planning: complexity and solution approaches

Improved approximation algorithms for capacitated facility location problems

Transmission system repair and restoration

Approximation Algorithms for Metric Facility Location Problems

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

Similar Documents

Local Search Heuristics for k-Median and Facility Location Problems

An efficient polynomial time approximation scheme for load balancing on uniformly related machines

LP-based approximation algorithms for capacitated facility location

A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems

Integrality gaps for strengthened linear relaxations of capacitated facility location

Integrated market selection and production planning: complexity and solution approaches

Improved approximation algorithms for capacitated facility location problems

Transmission system repair and restoration

Approximation Algorithms for Metric Facility Location Problems

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