Metraipolis › archive › dc_16fd537dbf6a
Boxing Problem — arXiv:2610.38085
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.38085
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-01T02:32:00.293Z
- SHA-256 of the archived text
f701346ca246d404981b74376ee56b5e5ab742bc0ccbeee62d9a4c7537749a3e- Stable URL of this page
https://metraipolis.com/documento/dc_16fd537dbf6a
How to cite
Boxing Problem — arXiv:2610.38085 — arXiv (en), https://arxiv.org/abs/2610.38085 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_16fd537dbf6a (Metraipolis archive dc_16fd537dbf6a, sha256 f701346ca246d404981b74376ee56b5e5ab742bc0ccbeee62d9a4c7537749a3e)
BibTeX
@misc{dc16fd537dbf6a,
title = {Boxing Problem — arXiv:2610.38085},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.38085},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_16fd537dbf6a; sha256 f701346ca246d404981b74376ee56b5e5ab742bc0ccbeee62d9a4c7537749a3e},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.38085. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the \textit{Boxing Problem}, which seeks a subset of points in \(\mathbb{R}^d\) maximizing the total reward of a selection of points minus the width of its axis-aligned bounding box. We also investigate the associated \textit{Boxing Set}, defined by the epigraph of the width function over binary selection variables. Although the width function is not submodular in general, we restore submodularity by fixing an anchor point. After anchoring, we establish a connection to the intersection of mixing sets with a linking constraint, which yields a polynomial-time optimization algorithm and a polynomial-size extended formulation. We then study the polyhedral structure of the Boxing Set and show that its facets admit laminar families of tight sets and can be obtained by sequential lifting. For the one-dimensional case, we provide a complete description of facet-defining inequalities together with a strongly polynomial-time separation algorithm.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2610.38085 — 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-01T02:14:28.295Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).