On the complexity of the bilevel minimum spanning tree problem

Simple item page
dc.contributor.authorBuchheim, Christoph
dc.contributor.authorHenke, Dorothee
dc.contributor.authorHommelsheim, Felix
dc.date.accessioned2024-02-12T12:43:02Z
dc.date.available2024-02-12T12:43:02Z
dc.date.issued2022-06-08
dc.description.abstractWe consider the bilevel minimum spanning tree (BMST) problem where the leader and the follower choose a spanning tree together, according to different objective functions. We show that this problem is NP-hard, even in the special case where the follower only controls a matching. Moreover, we give some evidence that BMST might even remain hard in case the follower controls only few edges. On the positive side, we present a (|V|-1)-approximation algorithm for BMST, where |V| is the number of vertices. Moreover, we show that 2-approximating BMST is fixed-parameter tractable and that, in case of uniform costs on leader's edges, even solving BMST exactly is fixed-parameter tractable. We finally consider bottleneck variants of BMST and settle the complexity landscape of all combinations of sum or bottleneck objective functions for the leader and follower, for the optimistic as well as the pessimistic setting.en
dc.identifier.urihttp://hdl.handle.net/2003/42324
dc.identifier.urihttp://dx.doi.org/10.17877/DE290R-24161
dc.language.isoende
dc.relation.ispartofseriesNetworks;80(3)
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/de
dc.subjectApproximation algorithmsen
dc.subjectBilevel optimizationen
dc.subjectCombinatorial optimizationen
dc.subjectComplexityen
dc.subjectSpanning tree problemen
dc.subjectSteiner treeen
dc.subject.ddc510
dc.titleOn the complexity of the bilevel minimum spanning tree problemen
dc.typeTextde
dc.type.publicationtypeResearchArticlede
dcterms.accessRightsopen access
eldorado.secondarypublicationtruede
eldorado.secondarypublication.primarycitationC. Buchheim, D. Henke, F. Hommelsheim, On the complexity of the bilevel minimum spanning tree problem, Networks. 80 (2022), 338–355. https://doi.org/10.1002/net.22111de
eldorado.secondarypublication.primaryidentifierhttps://doi.org/10.1002/net.22111de

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Networks - 2022 - Buchheim - On the complexity of the bilevel minimum spanning tree problem.pdf
Size:
1.36 MB
Format:
Adobe Portable Document Format
Description:
DNB
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
4.85 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Lehrstuhl V Diskrete Optimierung