Standard

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. ed. / Pinar Heggernes. Springer-Verlag GmbH and Co. KG, 2019. p. 62-74 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11485 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

van Bevern, R, Tsidulko, OY & Zschoche, P 2019, Fixed-Parameter Algorithms for Maximum-Profit Facility Location Under Matroid Constraints. in P Heggernes (ed.), Algorithms and Complexity - 11th International Conference, CIAC 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11485 LNCS, Springer-Verlag GmbH and Co. KG, pp. 62-74, 11th International Conference on Algorithms and Complexity, CIAC 2019, Rome, Italy, 27.05.2019. https://doi.org/10.1007/978-3-030-17402-6_6

APA

van Bevern, R., Tsidulko, O. Y., & Zschoche, P. (2019). Fixed-Parameter Algorithms for Maximum-Profit Facility Location Under Matroid Constraints. In P. Heggernes (Ed.), Algorithms and Complexity - 11th International Conference, CIAC 2019, Proceedings (pp. 62-74). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11485 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-030-17402-6_6

Vancouver

van Bevern R, Tsidulko OY, Zschoche P. Fixed-Parameter Algorithms for Maximum-Profit Facility Location Under Matroid Constraints. In Heggernes P, editor, Algorithms and Complexity - 11th International Conference, CIAC 2019, Proceedings. Springer-Verlag GmbH and Co. KG. 2019. p. 62-74. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-17402-6_6

Author

van Bevern, René ; Tsidulko, Oxana Yu ; Zschoche, Philipp. / Fixed-Parameter Algorithms for Maximum-Profit Facility Location Under Matroid Constraints. Algorithms and Complexity - 11th International Conference, CIAC 2019, Proceedings. editor / Pinar Heggernes. Springer-Verlag GmbH and Co. KG, 2019. pp. 62-74 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{514b1dbb68f741ed91e6c54f761639cb,
title = "Fixed-Parameter Algorithms for Maximum-Profit Facility Location Under Matroid Constraints",
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.",
keywords = "Matroid median, Matroid parity, Matroid set packing, Representative families, Social network analysis, Strong triadic closure",
author = "{van Bevern}, Ren{\'e} and Tsidulko, {Oxana Yu} and Philipp Zschoche",
year = "2019",
month = jan,
day = "1",
doi = "10.1007/978-3-030-17402-6_6",
language = "English",
isbn = "9783030174019",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "62--74",
editor = "Pinar Heggernes",
booktitle = "Algorithms and Complexity - 11th International Conference, CIAC 2019, Proceedings",
address = "Germany",
note = "11th International Conference on Algorithms and Complexity, CIAC 2019 ; Conference date: 27-05-2019 Through 29-05-2019",

}

RIS

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