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

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
Pages (from-to)110-128
Number of pages19
JournalDiscrete Applied Mathematics
Volume298
DOIs
Publication statusPublished - 31 Jul 2021

Keywords

  • Combinatorial optimization
  • Matroid median
  • Matroid parity
  • Matroid set packing

Fingerprint Dive into the research topics of 'Representative families for matroid intersections, with applications to location, packing, and covering problems'. Together they form a unique fingerprint.

Cite this