Metraipolis › archive › dc_97cc8a698ace

A Constant-Factor Approximation for Capacitated Facility Location with Outliers — arXiv:2611.04094

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.04094
License (as archived): CC0-1.0
Archived: 2026-11-04T19:06:57.566Z
SHA-256 of the archived text: 3f5b375dada85e2d548c6ee28851312c7d83487ff4c71e517f47e6b3f5589ddb
Stable URL of this page: https://metraipolis.com/documento/dc_97cc8a698ace

How to cite

A Constant-Factor Approximation for Capacitated Facility Location with Outliers — arXiv:2611.04094 — arXiv (en), https://arxiv.org/abs/2611.04094 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_97cc8a698ace (Metraipolis archive dc_97cc8a698ace, sha256 3f5b375dada85e2d548c6ee28851312c7d83487ff4c71e517f47e6b3f5589ddb)

BibTeX

@misc{dc97cc8a698ace,
  title = {A Constant-Factor Approximation for Capacitated Facility Location with Outliers — arXiv:2611.04094},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04094},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_97cc8a698ace; sha256 3f5b375dada85e2d548c6ee28851312c7d83487ff4c71e517f47e6b3f5589ddb},
  year = {2026}
}

Archived text

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

We give a deterministic polynomial-time $(60/11+\eps)$-approximation for metric capacitated facility location with outliers, with arbitrary opening costs and nonuniform hard capacities. The algorithm respects both capacities and the outlier budget. Its guarantee, approximately $5.455$, is close to the best known factor $5+\eps$ for capacitated facility location without outliers. The main ingredient is a local-search comparison for a common rejection penalty that retains the signed difference between the algorithm's and the comparator's rejection counts. Ordinary approximation guarantees for the penalty objective do not provide this comparison. We extend the exchange-forest accounting of Bansal, Garg, and Gupta \cite{BGG18} so that a nonnegative assignment remainder pays for rejection and cancels in the final bound. We then merge two penalty assignments whose served counts bracket the outlier quota. Grouping alternating paths by their terminal facility preserves capacities and shares opening costs. These ingredients give a $(20/3+\eps)$-approximation; starting each penalty run from the preceding solution improves the guarantee to $60/11+\eps$.

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/2611.04094 — 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-04T18:40:52.426Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).