Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 19 min ago
PreprintCC BY 4.0arXiv

Boxing Problem

  • April Niu
  • Santanu Dey
  • Oktay Günlük
  • Jisun Lee
Open at sourcePDFDOICite

Abstract

We study the \textit{Boxing Problem}, which seeks a subset of points in ℝ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.

Related

  1. Technical-tactical indicators associated with winning in elite amateur boxing: A matched-pair analysis
    Xuguang Chen, Mohamad Nizam Mohamed Shapie, Wenyao Chen
    PLOS OnePeer-reviewedCC BY 4.0Full textProbabilityPLOS
  2. On the Hasse-Sugawara problem and its application to Hilbert's twelfth problem
    Ho Yun Jung, Ja Kyung Koo, Dong Hwa Shin
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  3. The recognition problem for 4-manifolds and the unknotting problem for 2-spheres in 4-manifolds
    Cameron Gordon
    arXivPreprintCC BY-NC-SA 4.0Full textGeometry & topologyarXiv
  4. Partial Derivatives of J and Hopf Problem
    Jun Ling
    HALPreprintLicence Ouverte 2.0Full textGeneral mathematicsHAL
  5. Nonzero Forms related to Hopf Problem of Six-Sphere
    Jun Ling
    HALPreprintLicence Ouverte 2.0Full textGeneral mathematicsHAL

Cite

BibTeXRIS
BibTeX
@misc{niu2026boxing,
  title = {{Boxing Problem}},
  author = {April Niu and Santanu Dey and Oktay Günlük and Jisun Lee},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.38085},
  eprint = {2610.38085},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.38085},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Boxing Problem
AU  - April Niu
AU  - Santanu Dey
AU  - Oktay Günlük
AU  - Jisun Lee
PY  - 2026
DA  - 2026/10/27
PB  - arXiv
DO  - 10.48550/arxiv.2610.38085
UR  - https://arxiv.org/abs/2610.38085
AB  - We study the \textit{Boxing Problem}, which seeks a subset of points in ℝ^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.
ER  -