Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Fixed-Parameter Algorithms for Maximum-Profit Facility Location Under Matroid Constraints. / van Bevern, René; Tsidulko, Oxana Yu; Zschoche, Philipp.
Algorithms and Complexity - 11th International Conference, CIAC 2019, Proceedings. ред. / Pinar Heggernes. Springer-Verlag GmbH and Co. KG, 2019. стр. 62-74 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11485 LNCS).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - Fixed-Parameter Algorithms for Maximum-Profit Facility Location Under Matroid Constraints
AU - van Bevern, René
AU - Tsidulko, Oxana Yu
AU - Zschoche, Philipp
PY - 2019/1/1
Y1 - 2019/1/1
N2 - 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.
AB - 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.
KW - Matroid median
KW - Matroid parity
KW - Matroid set packing
KW - Representative families
KW - Social network analysis
KW - Strong triadic closure
UR - http://www.scopus.com/inward/record.url?scp=85066909879&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-17402-6_6
DO - 10.1007/978-3-030-17402-6_6
M3 - Conference contribution
AN - SCOPUS:85066909879
SN - 9783030174019
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 62
EP - 74
BT - Algorithms and Complexity - 11th International Conference, CIAC 2019, Proceedings
A2 - Heggernes, Pinar
PB - Springer-Verlag GmbH and Co. KG
T2 - 11th International Conference on Algorithms and Complexity, CIAC 2019
Y2 - 27 May 2019 through 29 May 2019
ER -
ID: 20530120