Sharp Logarithmic Thresholds for Cut Schedules in an Abstract Branch-and-Cut Model
Branch-and-cut interleaves branching with cutting-plane generation. How the two operations share the work of proving a bound is a basic theoretical question. We study an abstract model in which a tree certifies a target bound $Z$. Each branch node improves the bound by $\ell$ on one child and by $r$ on the other, where $0 0$ defined by $e^{-λ^{\star}\ell}+e^{-λ^{\star}r}=1$. We establish uniform two-sided bounds of order $e^{λ^{\star}Z}$ on the minimal leaf count of pure branching trees. We then identify $\log k$ as the sharp threshold scale for the power of cutting. For cut schedules with…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.06343
curl -X POST /api/v1/records/arxiv/2607.06343/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.06343/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'