Tight Approximation Results for Matroid Optimization with a Linear Constraint

Ilan Doron-Arad, Hadas Shachnai, Gilad Shmerler

We study the following class of matroid optimization problems with a linear constraint (P-MOL). Given a matroid M=(E,I), two weight functions $v,w:E\to R_{\ge 0}$, and a threshold…