2014/08/21 by Neelima Gupta, Shubham Gupta, Gupta, Neelima +1
Business, Management and Accounting · Computer Science · Engineering · #Advanced Manufacturing and Logistics Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Facility Location and Emergency Management #Vehicle Routing Optimization Methods #cs.DS
paper · pdf · doi:10.48550/arxiv.1408.4944
openalex publication_date 2014/08/21 · arxiv created 2014/09/12 · arxiv updated 2014/09/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. \citecharikar2001algorithms, Jain et. al. \citejain2003greedy and Xu- Xu \citexu2009improved gave 3, 2 and 1.8526 approximation, respectively, for the uncapacitated case . We present (5.83 + ε) factor for the case of uniform capacities and (8.532 + ε) factor for non-uniform capacities.