Metraipolis › archive › dc_dce93c0bbc9b

Multiple Swap Local Search Approximations for Uniform-Cost Capacitated Facility Location with Extensions to Outliers — arXiv:2610.41187

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.41187
License (as archived)
CC0-1.0
Archived
2026-11-03T05:49:19.880Z
SHA-256 of the archived text
49cab465cbd40eb9eb5fa9f6f383d2ff1387ea873c6a95c9b40510d359eb5235
Stable URL of this page
https://metraipolis.com/documento/dc_dce93c0bbc9b

How to cite

Multiple Swap Local Search Approximations for Uniform-Cost Capacitated Facility Location with Extensions to Outliers — arXiv:2610.41187 — arXiv (en), https://arxiv.org/abs/2610.41187 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dce93c0bbc9b (Metraipolis archive dc_dce93c0bbc9b, sha256 49cab465cbd40eb9eb5fa9f6f383d2ff1387ea873c6a95c9b40510d359eb5235)
BibTeX
@misc{dcdce93c0bbc9b,
  title = {Multiple Swap Local Search Approximations for Uniform-Cost Capacitated Facility Location with Extensions to Outliers — arXiv:2610.41187},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41187},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dce93c0bbc9b; sha256 49cab465cbd40eb9eb5fa9f6f383d2ff1387ea873c6a95c9b40510d359eb5235},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41187. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study metric facility location with customer incompatibilities, where the clients assigned to each facility must satisfy prescribed independence constraints. We first consider the setting of facility-opening costs and where there is a single matroid $\mathcal M$ over the clients and the set of clients assigned to an open facility must be an independent set in $\mathcal M$. We develop a polynomial-time \((1+\sqrt{2}+\epsilon)\)-approximation algorithm for this setting. We further obtain a polynomial-time \((15+\epsilon)\)-approximation algorithm for the case of non-uniform facility-opening costs when $\mathcal M$ is a partition matroid that only permits $b_g$ clients to be assigned to a facility for each group $g$ in the partition. Both settings are substantial generalizations of Capacitated Facility Location with uniform capacities. Our algorithms are based on local search using add, delete, and single-swap operations. As with CFL, bounding the connection cost is reasonably straightforward using supermodularity of the minimum connection-cost function. However, bounding the facility opening costs requires novel arguments in both cases. We use a ``compression'' argument based on matroid exchange principles to identify a subset of the locally opened facilities whose size is no larger than that of an optimal facility set. The opening costs of facilities outside this subset can be bounded using supermodularity, while bounding the costs of the remaining facilities requires different arguments. It is natural to consider a variant where each possible facility $i$ has its own matroid $\mathcal M_i$ defining the subsets of clients it can feasibly serve. We also show problem is at least as hard to approximate as Set Cover even if all $\mathcal M_i$ are partition matroids that have the same partition of clients, just different group bounds $b_g$.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.41187 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T05:34:47.017Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).