Metraipolis › archive › dc_a161f3bdc5be

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-02T08:06:43.209Z
SHA-256 of the archived text
8965a91670f662ca377349589e12251511eefb34248a4fe24fc1c6f3cd1da26e
Stable URL of this page
https://metraipolis.com/documento/dc_a161f3bdc5be

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_a161f3bdc5be (Metraipolis archive dc_a161f3bdc5be, sha256 8965a91670f662ca377349589e12251511eefb34248a4fe24fc1c6f3cd1da26e)
BibTeX
@misc{dca161f3bdc5be,
  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_a161f3bdc5be; sha256 8965a91670f662ca377349589e12251511eefb34248a4fe24fc1c6f3cd1da26e},
  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-02T07:45:15.769Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).