Integrality-Gap Bounds for Weighted Matchoids and Matroid Intersection

Yu Cong, Yajie Zhao

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…