Standard

Representative families for matroid intersections, with applications to location, packing, and covering problems. / van Bevern, René; Tsidulko, Oxana Yu; Zschoche, Philipp.

In: Discrete Applied Mathematics, Vol. 298, 31.07.2021, p. 110-128.

Research output: Contribution to journal › Article › peer-review

Harvard

van Bevern, R, Tsidulko, OY & Zschoche, P 2021, 'Representative families for matroid intersections, with applications to location, packing, and covering problems', Discrete Applied Mathematics, vol. 298, pp. 110-128. https://doi.org/10.1016/j.dam.2021.03.014

APA

van Bevern, R., Tsidulko, O. Y., & Zschoche, P. (2021). Representative families for matroid intersections, with applications to location, packing, and covering problems. Discrete Applied Mathematics, 298, 110-128. https://doi.org/10.1016/j.dam.2021.03.014

Vancouver

van Bevern R, Tsidulko OY, Zschoche P. Representative families for matroid intersections, with applications to location, packing, and covering problems. Discrete Applied Mathematics. 2021 Jul 31;298:110-128. doi: 10.1016/j.dam.2021.03.014

Author

van Bevern, René ; Tsidulko, Oxana Yu ; Zschoche, Philipp. / Representative families for matroid intersections, with applications to location, packing, and covering problems. In: Discrete Applied Mathematics. 2021 ; Vol. 298. pp. 110-128.

BibTeX

@article{046a3e6c8e9745fa94e808a8df509a95,
title = "Representative families for matroid intersections, with applications to location, packing, and covering problems",
abstract = "We show algorithms for computing representative families for matroid intersections and use them in fixed-parameter algorithms for set packing, set covering, and facility location problems with multiple matroid constraints. We complement our tractability results by hardness results.",
keywords = "Combinatorial optimization, Matroid median, Matroid parity, Matroid set packing",
author = "{van Bevern}, Ren{\'e} and Tsidulko, {Oxana Yu} and Philipp Zschoche",
note = "Funding Information: Ren{\'e} van Bevern was supported by Russian Foundation for Basic Research (RFBR) grant 18-501-12031 NNIO_a . Oxana Yu. Tsidulko was supported by RFBR grant 18-31-00470 mol_a . Publisher Copyright: {\textcopyright} 2021 Elsevier B.V. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.",
year = "2021",
month = jul,
day = "31",
doi = "10.1016/j.dam.2021.03.014",
language = "English",
volume = "298",
pages = "110--128",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Representative families for matroid intersections, with applications to location, packing, and covering problems

AU - van Bevern, René

AU - Tsidulko, Oxana Yu

AU - Zschoche, Philipp

N1 - Funding Information: René van Bevern was supported by Russian Foundation for Basic Research (RFBR) grant 18-501-12031 NNIO_a . Oxana Yu. Tsidulko was supported by RFBR grant 18-31-00470 mol_a . Publisher Copyright: © 2021 Elsevier B.V. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2021/7/31

Y1 - 2021/7/31

N2 - We show algorithms for computing representative families for matroid intersections and use them in fixed-parameter algorithms for set packing, set covering, and facility location problems with multiple matroid constraints. We complement our tractability results by hardness results.

AB - We show algorithms for computing representative families for matroid intersections and use them in fixed-parameter algorithms for set packing, set covering, and facility location problems with multiple matroid constraints. We complement our tractability results by hardness results.

KW - Combinatorial optimization

KW - Matroid median

KW - Matroid parity

KW - Matroid set packing

UR - http://www.scopus.com/inward/record.url?scp=85104394044&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2021.03.014

DO - 10.1016/j.dam.2021.03.014

M3 - Article

AN - SCOPUS:85104394044

VL - 298

SP - 110

EP - 128

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -

ID: 28397995