Name
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. |
Year | Venue | Field |
|---|---|---|
2014 | CoRR | Approximation algorithm,Discrete mathematics,Combinatorics,Facility location problem,Mathematics |
DocType | Volume | Citations |
Journal | abs/1408.4944 | 3 |
PageRank | References | Authors |
0.42 | 6 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Neelima Gupta | 1 | 159 | 19.69 |
| Shubham Gupta | 2 | 3 | 2.11 |