Split Cuts in Fixed Integer Dimensions
We study how many split cuts, which include the Gomory mixed-integer cuts, are needed to reach the integer hull, and how large split closures can be. In every fixed dimension, a rational pure-integer polytope admits a polynomial-time constructible split proof of its integer hull with polynomial total encoding length; consequently, its full split rank is polynomial in the input length. This establishes the split-rank conjecture of Basu, Conforti, Di Summa, and Jiang for bounded pure-integer polyhedra in fixed dimension. Central to our approach is a preservation result: in arbitrary…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.02169
curl -X POST /api/v1/records/arxiv/2611.02169/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.02169/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'