{"id":"arxiv/2609.21477","url":"https://arxiv.org/abs/2609.21477","tags":["math.CO","cs.DM"],"score":0,"title":"Integrality-Gap Bounds for Weighted Matchoids and Matroid Intersection","domain":"math.CO","source":"arxiv","authors":["Yu Cong","Yajie Zhao"],"reviews":0,"subject":"math.CO","summary":"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\\le3$, but for $k\\ge4$ 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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-18","reactions":{}}