Representative families for matroid intersections, with applications to location, packing, and covering problems

Abstract

We show algorithms for computing representative families for matroid intersections and use them in fixed-parameter algorithms for set packing, set covering, and facility location problems with multiple matroid constraints. We complement our tractability results by hardness results.

arXiv commentRestructuring (focus on representative families instead of facility location), slight running time improvements, algorithms factored out