Matroid-Aware Spectral Certificates for Multiplicative Coverage Approximation
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.17514
curl -X POST /api/v1/records/arxiv/2610.17514/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.17514/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'