Covariance-Rank Rounding and a Sharp Integrality Gap for a Matroid Edge-Coverage Moment Lift
Abstract
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⊤ 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≥1, the resulting basis has value at least (3/4+1/(4d))U. The procedure is deterministic and polynomial-time for a supplied exact rational point and an independence oracle. Weighting the covariance spectrum by the objective gives a stronger version of the bound. To show the rank factor is sharp, we construct a rank-2m rational linear matroid and m disjoint four-cycles with integral optimum 3m+1, relaxation optimum 4m, and an optimal covariance matrix of rank m. Thus the relaxation has limiting reciprocal integrality gap 4/3, despite its conditional constraints. One valid pair-exclusion inequality makes it exact on this family, as an explicit semidefinite certificate shows. The result concerns rounding and the strength of this relaxation; it does not supply a low-rank optimal point or a fixed universal approximation improvement.
Related
- Integrality-Gap Bounds for Weighted Matchoids and Matroid Intersection
- Matroid-Aware Spectral Certificates for Multiplicative Coverage Approximation
- Optimal detection of general moment changes: Simultaneous mean and covariance change detection and beyond
- Feasible closed form moment matching for scenario generation through covariance rotations
- Integrality of height-one formal groups
BibTeX
@misc{rezazadeh2026covariancerank,
title = {{Covariance-Rank Rounding and a Sharp Integrality Gap for a Matroid Edge-Coverage Moment Lift}},
author = {Navid Rezazadeh},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.17512},
eprint = {2610.17512},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.17512},
}
RIS
TY - UNPB
TI - Covariance-Rank Rounding and a Sharp Integrality Gap for a Matroid Edge-Coverage Moment Lift
AU - Navid Rezazadeh
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.17512
UR - https://arxiv.org/abs/2610.17512
AB - 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^⊤ 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≥1, the resulting basis has value at least (3/4+1/(4d))U. The procedure is deterministic and polynomial-time for a supplied exact rational point and an independence oracle. Weighting the covariance spectrum by the objective gives a stronger version of the bound. To show the rank factor is sharp, we construct a rank-2m rational linear matroid and m disjoint four-cycles with integral optimum 3m+1, relaxation optimum 4m, and an optimal covariance matrix of rank m. Thus the relaxation has limiting reciprocal integrality gap 4/3, despite its conditional constraints. One valid pair-exclusion inequality makes it exact on this family, as an explicit semidefinite certificate shows. The result concerns rounding and the strength of this relaxation; it does not supply a low-rank optimal point or a fixed universal approximation improvement.
ER -