Approximation algorithms for Capacitated Facility Location Problem with Penalties
Authors:
Preprint
Abstract
In this paper, we address the problem of capacitated facility location problem with penalties (CapFLPP) paid per unit of unserved demand. In case of uncapacitated FLP with penalties demands of a client are either entirely met or are entirely rejected and penalty is paid. In the uncapacitated case, there is no reason to serve a client partially. Whereas, in case of CapFLPP, it may be beneficial to serve a client partially instead of not serving at all and, pay the penalty for the unmet demand. Charikar et. al.~\cite{charikar2001algorithms}, Jain et. al.~\cite{jain2003greedy} and Xu- Xu~\cite{xu2009improved} gave $3$, $2$ and $1.8526$ approximation, respectively, for the uncapacitated case . We present $(5.83 + \epsilon)$ factor for the case of uniform capacities and $(8.532 + \epsilon)$ factor for non-uniform capacities.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- A 5-Approximation for Capacitated Facility Location2012
- An improved approximation algorithm for uncapacitated facility location problem with penaltiesJournal of Combinatorial Optimization, 2008
- A Unified Approach to Approximating Partial Covering ProblemsLecture Notes in Computer Science, 2006
- Local Search Heuristics for k-Median and Facility Location ProblemsSIAM Journal on Computing, 2004
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LPJournal of the ACM, 2003
- Analysis of a Local Search Heuristic for Facility Location ProblemsJournal of Algorithms, 2000
- Improved Approximation Algorithms for Capacitated Facility Location Problems1999
- A General Approximation Technique for Constrained Forest ProblemsSIAM Journal on Computing, 1995