Boxing Problem
math.OC
Submitted: 2026-10-27
Updated: 2026-10-27
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study the Boxing Problem, which seeks a subset of points in R d maximizing the total reward of a selection of points minus the width of its axis-aligned bounding box.
Abstract
We study the Boxing Problem, which seeks a subset of points in 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 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 papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise