Scaling Local Solvers with the Many-Body Expansion
We introduce a Many-Body Expansion framework for scaling black-box solvers for discrete optimization. The method decomposes a large problem into fragments, repeatedly improves each fragment with the rest of the assignment held fixed, and then applies targeted corrections on unions of fragments. The solver itself is unchanged: it only receives a restricted subproblem and returns a candidate assignment. The framework separates decomposition from solver design. Moebius inversion gives an exact fragment expansion of the objective, and for pairwise objectives such as graph coloring, MAX-CUT, and…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.30137
curl -X POST /api/v1/records/arxiv/2610.30137/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.30137/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'