Volumes of the strong and weak relaxations of the uncapacitated facility-location polytope
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.25981
curl -X POST /api/v1/records/arxiv/2609.25981/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.25981/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'