Curvature batching for integer and mixed-integer quadratic programming
We give an explicit algorithm for integer quadratic programming with running time $(nL)^{O(n^2)} \mathrm{poly}(φ)$, where $n$ is the number of variables, $L$ bounds the absolute entries of the constraint and quadratic matrices, and $φ$ is the total input encoding length. The linear objective and constraint right-hand sides enter only through $φ$. The algorithm refines Lokshtanov's branching framework. Small integer kernel directions identify optima near constraint boundaries. When all chosen basis directions have nonnegative curvature, their gradient values can be imposed in one batch. The…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.04851
curl -X POST /api/v1/records/arxiv/2604.04851/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.04851/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'