On Partial Optimality in QUBO via Quadratic Posiform Autarkies
Partially optimal assignments (also called persistencies) allow combinatorial optimization problems to be reduced by fixing a subset of variables to values consistent with at least one optimal solution. For the quadratic unconstrained binary optimization (QUBO) problem, such assignments can be computed efficiently via autarkies of quadratic posiforms. However, the largest autarky domain and thus the number of fixed variables can depend on the specific posiform representation. We show that every quadratic posiform with the greatest possible constant term (the roof-dual bound) yields the…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.20346
curl -X POST /api/v1/records/arxiv/2610.20346/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.20346/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'