Optimal Cuts and Optimal Faces of Exact Max-Cut Semidefinite Relaxations
An exact Max-Cut semidefinite relaxation can have optima outside the convex hull of optimal cut matrices. We study when this hull equals the optimal face and how to recognize equality. For rational weights, the unique optimal dual slack is recoverable in polynomial time, but its kernel may contain directions no optimal matrix uses. Under strict complementarity, recognition and recovery of all optimal cuts on equality instances take deterministic polynomial time. At dual rank one, this hypothesis is unnecessary. Recognition is polynomial-time Turing equivalent to exact rational semidefinite…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.36827
curl -X POST /api/v1/records/arxiv/2609.36827/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.36827/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'