Metraipolis › archive › dc_e6bd7c148376
Volumes of the strong and weak relaxations of the uncapacitated facility-location polytope — arXiv:2609.25981
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.25981
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T15:53:20.146Z
- SHA-256 of the archived text
cab9c8496b559b28291b251b29eeda3a2d96fa9e6df60ac3c81c4dfcb95ab845- Stable URL of this page
https://metraipolis.com/documento/dc_e6bd7c148376
How to cite
Volumes of the strong and weak relaxations of the uncapacitated facility-location polytope — arXiv:2609.25981 — arXiv (en), https://arxiv.org/abs/2609.25981 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e6bd7c148376 (Metraipolis archive dc_e6bd7c148376, sha256 cab9c8496b559b28291b251b29eeda3a2d96fa9e6df60ac3c81c4dfcb95ab845)
BibTeX
@misc{dce6bd7c148376,
title = {Volumes of the strong and weak relaxations of the uncapacitated facility-location polytope — arXiv:2609.25981},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.25981},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e6bd7c148376; sha256 cab9c8496b559b28291b251b29eeda3a2d96fa9e6df60ac3c81c4dfcb95ab845},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.25981. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Lee, Skipper, and Speakman (2018) asked for formulae or asymptotic expressions for the volumes of the strong and weak relaxations $\mathcal{P}_{m,n}\cap \mathcal{D}_{m,n}$ and $\mathcal{Q}_{m,n}\cap \mathcal{D}_{m,n}$ of the uncapacitated facility-location polytope with $m$ facilities and $n$ customers (their Problem~3, ``Texas Hot''). We give exact formulae for all $m$ and $n$, and we give asymptotics that hold uniformly as $m+n\to\infty$, whatever the relative growth of $m$ and $n$. The volume ratio satisfies $Vol(\mathcal{Q}_{m,n}\cap \mathcal{D}_{m,n})/Vol(\mathcal{P}_{m,n}\cap \mathcal{D}_{m,n})\sim \prod_{j=2}^{n}\mleft(1+\tfrac{1}{(m-1)j}\mright)^{m}$. From this, we read off the behavior in every growth regime of $m$, and we identify a sharp transition at $m\asymp\ln n$. Below it, in a uniformly random point of the strong relaxation, each facility variable is close to $1$ with high probability, and the ratio grows superlinearly in $n$. Above it, in a uniformly random point of either relaxation, each facility variable is asymptotically uniform on $[0,1]$, and the ratio grows linearly in $n$.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-23 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.25981 — 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-10-08T15:12:09.737Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-23?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).