Hidden Convexity via Symmetric Displacement Covers: Mixed-Integer Quadratic Programming and Integer Cubic Programming in Fixed Dimension
We give exact polynomial-time algorithms in fixed dimension for mixed-integer quadratic programming over arbitrary rational polyhedra and for integer cubic programming over bounded rational polyhedra. The quadratic objective may be indefinite; the algorithm detects infeasibility, certifies unboundedness, or returns an exact minimizer. For an instance with N variables and m constraints, the running time is 2O(Nlog N) times (m+ 1)O(N) times a factor in which the binary encoding lengths of the coefficients are raised to a power O(N); for pure integer problems, and for mixed-integer problems…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.18266
curl -X POST /api/v1/records/arxiv/2609.18266/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.18266/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'