@inproceedings{d2fe530ec83e4483a6f6599586db2268,
title = "Improved Approximation Algorithm for Capacitated Facility Location with Uniform Facility Cost",
abstract = "We consider the hard-capacitated facility location problem with uniform facility cost (CFL-UFC). This problem arises as an indicator variation between the general CFL problem and the uncapacitated facility location (UFL) problem, and is related to the profound capacitated k-median problem (CKM). In this work, we present a rounding-based 4-approximation algorithm for this problem, built on a two-staged rounding scheme that incorporates a set of novel ideas and also techniques developed in the past for both facility location and capacitated covering problems. Our result improves the decades-old LP-based ratio of 5 for this problem due to Levi et al. since 2004. We believe that the techniques developed in this work are of independent interests and may further lead to insights and implications for related problems.",
keywords = "Capacitated facility location, Hard capacities, Uniform facility cost",
author = "Kao, {Mong Jen}",
note = "Publisher Copyright: {\textcopyright} Mong-Jen Kao; licensed under Creative Commons License CC-BY 4.0.; 34th International Symposium on Algorithms and Computation, ISAAC 2023 ; Conference date: 03-12-2023 Through 06-12-2023",
year = "2023",
month = dec,
doi = "10.4230/LIPIcs.ISAAC.2023.45",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Satoru Iwata and Satoru Iwata and Naonori Kakimura",
booktitle = "34th International Symposium on Algorithms and Computation, ISAAC 2023",
address = "德國",
}