Matroidal Approximations of Independence Systems

Abstract

Milgrom (2017) has proposed a heuristic for determining a maximum weight basis of an independence system $\mathcal{I}$ given that we want an approximation guarantee only for sets in a prescribed $\mathcal{O}\subseteq \mathcal{I}$. This $\mathcal{O}$ reflects prior knowledge of the designer about the location of the optimal basis. The heuristic is based on finding an `inner matroid', one contained in the independence system. We show that even in the case $\mathcal{O}=\mathcal{I}$ of zero additional knowledge the worst-case performance of this new heuristic can be better than that of the classical greedy algorithm.