Fixed-Parameter Algorithms for Maximum-Profit Facility Location Under Matroid Constraints

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

6 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationAlgorithms and Complexity - 11th International Conference, CIAC 2019, Proceedings
EditorsPinar Heggernes
PublisherSpringer-Verlag GmbH and Co. KG
Pages62-74
Number of pages13
ISBN (Print)9783030174019
DOIs
Publication statusPublished - 1 Jan 2019
Event11th International Conference on Algorithms and Complexity, CIAC 2019 - Rome, Italy
Duration: 27 May 201929 May 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11485 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th International Conference on Algorithms and Complexity, CIAC 2019
CountryItaly
CityRome
Period27.05.201929.05.2019

Keywords

  • Matroid median
  • Matroid parity
  • Matroid set packing
  • Representative families
  • Social network analysis
  • Strong triadic closure

Fingerprint Dive into the research topics of 'Fixed-Parameter Algorithms for Maximum-Profit Facility Location Under Matroid Constraints'. Together they form a unique fingerprint.

Cite this