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

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.

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-02
Main Authors: René van Bevern, Oxana Yu Tsidulko, Zschoche, Philipp
Format: Article
Language:English
Subjects:
Algorithms
Clients
Constraint modelling
Intersections
Lower bounds
Network analysis
Operations research
Parameters
Site selection
Social networks
Weight
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422
DOI:10.48550/arxiv.1806.11527