Covariance-Rank Rounding and a Sharp Integrality Gap for a Matroid Edge-Coverage Moment Lift
Selecting vertices covers their incident edges, but a matroid can prevent selecting the combinations that cover the most weight. We study whether pair-selection information improves rounding from a semidefinite relaxation of this problem. A feasible point $(x,Y)$ records individual and paired selection values. Its relaxation objective is $U$, and the matrix $Y-xx^\top$ has rank $d$. We compare the feasible marginal vectors obtained by fixing one element as selected or excluded, then round only the best vector. For $d\ge1$, the resulting basis has value at least $(3/4+1/(4d))U$. The procedure…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.17512
curl -X POST /api/v1/records/arxiv/2610.17512/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.17512/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'