Integrality-Gap Bounds for Weighted Matchoids and Matroid Intersection

Yu Cong; Yajie Zhao

In the authors' words

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 \leq 3$ , but for $k \geq 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\'ak; projective planes give explicit tight instances whenever one of order $p - 1$ exists.

Main resultLimitation the authors admit

Integrality-Gap Bounds for Weighted Matchoids and Matroid Intersection

In the authors' words

More on Optimization that day

Benign Nonconvex Landscape for Policy Optimization: Infinite-Horizon Discounted MDPs with General State and Action Spaces

Beyond Shadow Weights: Quantization-Aware Training as Quantized-Endpoint Descent

Energy minimization for eight points on the sphere

Near-Optimal Acceleration for Smooth ℓp​ / ℓq​ Nondual Convex First-Order Oracle Optimization

Interference-Driven Clustered Optimisation for FM Spectrum Coordination

Near-Optimal Acceleration for Smooth $ℓ_{p}$ / $ℓ_{q}$ Nondual Convex First-Order Oracle Optimization