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


Abstract in English

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.

Download