A Primal Approach to Facial Reduction for SDP Relaxations of Combinatorial Optimization Problems
We propose a novel facial reduction algorithm tailored to semidefinite programming relaxations of combinatorial optimization problems with quadratic objective functions. Our method leverages the specific structure of these relaxations, particularly the availability of feasible solutions that can often be generated efficiently in practice. By incorporating such solutions into the facial reduction process, we substantially simplify the reduction steps. On average, our facial reduction algorithm is four times faster than the standard implementation on the considered benchmark sets, providing…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.26514
curl -X POST /api/v1/records/arxiv/2607.26514/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.26514/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'