Integrality-Gap Bounds for Weighted Matchoids and Matroid Intersection
Abstract
The weighted k-matroid intersection problem asks for a maximum-weight set that is independent in each of k matroids on a common ground set. The natural LP relaxation optimizes over the intersection of the k matroid independent set polytopes. It is conjectured that this LP has integrality gap at most k−1. The conjecture is known for k≤3, but for k≥4 the best general upper bound was k. We improve this bound to k−1+1/k. More generally, we prove that the natural LP of a p-matchoid has integrality gap at most p−1+1/p, with a deterministic LP-relative algorithm attaining the same factor. The matchoid extension resolves the p-matchoid part of a conjecture of Lee, Sviridenko, and Vondrák; projective planes give explicit tight instances whenever one of order p−1 exists.
Related
- Covariance-Rank Rounding and a Sharp Integrality Gap for a Matroid Edge-Coverage Moment Lift
- A weighted inequality for matroid flats and log-concavity of Whitney numbers
- Integrality, smoothness and normality bounds for cube-truncated Hadamard simplices
- Integrality Gap Bounds for the Goemans-Linial SDP on Finite Abelian Cayley Graphs
- Irrational families of Fano weighted complete intersection fourfolds
BibTeX
@misc{cong2026integralitygap,
title = {{Integrality-Gap Bounds for Weighted Matchoids and Matroid Intersection}},
author = {Yu Cong and Yajie Zhao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.21477},
eprint = {2609.21477},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21477},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Integrality-Gap Bounds for Weighted Matchoids and Matroid Intersection
AU - Yu Cong
AU - Yajie Zhao
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.21477
UR - https://arxiv.org/abs/2609.21477
AB - The weighted k-matroid intersection problem asks for a maximum-weight set that is independent in each of k matroids on a common ground set. The natural LP relaxation optimizes over the intersection of the k matroid independent set polytopes. It is conjectured that this LP has integrality gap at most k−1. The conjecture is known for k≤3, but for k≥4 the best general upper bound was k. We improve this bound to k−1+1/k. More generally, we prove that the natural LP of a p-matchoid has integrality gap at most p−1+1/p, with a deterministic LP-relative algorithm attaining the same factor. The matchoid extension resolves the p-matchoid part of a conjecture of Lee, Sviridenko, and Vondrák; projective planes give explicit tight instances whenever one of order p−1 exists.
ER -