Improved bounds on weighted matroid intersections and matchoids
Integrality-Gap Bounds for Weighted Matchoids and Matroid Intersection
Discrete Mathematics
Summary
The paper studies a math problem about picking the best combination of items that satisfy multiple rules at once, called matroids. The authors improved the best known mathematical guarantee for how close a certain relaxation method gets to the true best solution, especially when there are four or more rules. They also extended this to a more general setting called matchoids. Their results get closer to a long-standing prediction and can be matched by a deterministic algorithm.
What this means in practice
- •For network schedulers: Use improved approximation guarantees for resource allocation problems modeled by matroid intersections to design more efficient scheduling algorithms.
- •For database system builders: Optimize complex query evaluation plans that can be expressed through weighted matroid constraints with tighter LP-based approximations.
A theory result. No direct application yet.
Authors
Yu Cong, Yajie Zhao
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\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 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.