Fixed-Parameter Algorithms for Maximum-Profit Facility Location Under Matroid Constraints
| Autor: | René van Bevern, Philipp Zschoche, Oxana Yu. Tsidulko |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Computer Science::Computer Science and Game Theory
Mathematics::Combinatorics Rank (linear algebra) Computer science TheoryofComputation_GENERAL Parameterized complexity Matroid Facility location problem Set (abstract data type) Task (computing) Computer Science::Discrete Mathematics Independent set Computer Science::Data Structures and Algorithms Algorithm Complement (set theory) |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783030174019 CIAC |
| DOI: | 10.1007/978-3-030-17402-6_6 |
| Popis: | We consider an uncapacitated discrete facility location problem where the task is to decide which facilities to open and which clients to serve for maximum profit so that the facilities form an independent set in given facility-side matroids and the clients form an independent set in given client-side matroids. We show that the problem is fixed-parameter tractable parameterized by the number of matroids and the minimum rank among the client-side matroids. To this end, we derive fixed-parameter algorithms for computing representative families for matroid intersections and maximum-weight set packings with multiple matroid constraints. To illustrate the modeling capabilities of the new problem, we use it to obtain algorithms for a problem in social network analysis. We complement our tractability results by lower bounds. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|