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

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

5 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииAlgorithms and Complexity - 11th International Conference, CIAC 2019, Proceedings
РедакторыPinar Heggernes
ИздательSpringer-Verlag GmbH and Co. KG
Страницы62-74
Число страниц13
ISBN (печатное издание)9783030174019
DOI
СостояниеОпубликовано - 1 янв 2019
Событие11th International Conference on Algorithms and Complexity, CIAC 2019 - Rome, Италия
Продолжительность: 27 мая 201929 мая 2019

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том11485 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция11th International Conference on Algorithms and Complexity, CIAC 2019
СтранаИталия
ГородRome
Период27.05.201929.05.2019

Fingerprint Подробные сведения о темах исследования «Fixed-Parameter Algorithms for Maximum-Profit Facility Location Under Matroid Constraints». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать