Matroid-Aware Spectral Certificates for Multiplicative Coverage Approximation
Abstract
We maximize the weight of edges covered by selected vertices, together with nonnegative individual rewards, under an arbitrary matroid constraint. The continuous coverage objective is quadratic and need not be concave. Our method searches projections onto a small set of directions and solves a concave subproblem for each projection center. A coverage-specific inequality converts the subproblem bounds into a multiplicative guarantee, while matroid rounding restores an integral solution. Let A be the weighted adjacency matrix and D the diagonal matrix of singleton values, restricted to positive-value elements after objective-preserving preprocessing. Set ϱ=λmax(D−1/2AD−1/2). For an integer budget q≥0, let τq be the smallest nonnegative threshold for which A+τqD has at most q negative eigenvalues on the span of differences of matroid bases. We obtain the factor 1−ϱτq/[2(ϱ+τq)]−ε in time (2+q/ε)O(q+1)NO(1), where N is the binary input length and a zero-over-zero loss is zero. The algorithm returns a rational upper bound on the integral optimum. A separate exact-algebraic construction produces polynomial-bit low-rank rational corrections with positive threshold slack; its proof isolates eigenvalues, keeps eigenspace bases unnormalized, and approximates scalar factors only at the final step. The numerical proposal prototype is not used to justify this complexity statement. Supplied certificates also yield robustness to locally bounded edge additions. These are threshold-dependent coverage guarantees, not a new general spectral-search principle or a universal approximation improvement.
Related
- On minimum-size matroid counterexamples to the multiplicative Merino--Welsh inequality
- Covariance-Rank Rounding and a Sharp Integrality Gap for a Matroid Edge-Coverage Moment Lift
- An Analytic 0.48-Approximation for Non-Monotone k-Submodular Maximization under a Matroid Constraint
- A Deterministic $0.401$-Approximation for Non-monotone Submodular Maximization under Matroid Constraints
- Smallest String Attractors and Minimal Coverage Certificates of Thue--Morse Words
BibTeX
@misc{rezazadeh2026matroidaware,
title = {{Matroid-Aware Spectral Certificates for Multiplicative Coverage Approximation}},
author = {Navid Rezazadeh},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.17514},
eprint = {2610.17514},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.17514},
}
RIS
TY - UNPB
TI - Matroid-Aware Spectral Certificates for Multiplicative Coverage Approximation
AU - Navid Rezazadeh
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.17514
UR - https://arxiv.org/abs/2610.17514
AB - We maximize the weight of edges covered by selected vertices, together with nonnegative individual rewards, under an arbitrary matroid constraint. The continuous coverage objective is quadratic and need not be concave. Our method searches projections onto a small set of directions and solves a concave subproblem for each projection center. A coverage-specific inequality converts the subproblem bounds into a multiplicative guarantee, while matroid rounding restores an integral solution. Let A be the weighted adjacency matrix and D the diagonal matrix of singleton values, restricted to positive-value elements after objective-preserving preprocessing. Set ϱ=λ_max(D^−1/2AD^−1/2). For an integer budget q≥0, let τ_q be the smallest nonnegative threshold for which A+τ_qD has at most q negative eigenvalues on the span of differences of matroid bases. We obtain the factor 1−ϱτ_q/[2(ϱ+τ_q)]−ε in time (2+q/ε)^O(q+1)N^O(1), where N is the binary input length and a zero-over-zero loss is zero. The algorithm returns a rational upper bound on the integral optimum. A separate exact-algebraic construction produces polynomial-bit low-rank rational corrections with positive threshold slack; its proof isolates eigenvalues, keeps eigenspace bases unnormalized, and approximates scalar factors only at the final step. The numerical proposal prototype is not used to justify this complexity statement. Supplied certificates also yield robustness to locally bounded edge additions. These are threshold-dependent coverage guarantees, not a new general spectral-search principle or a universal approximation improvement.
ER -