A note on the complexity of the bilevel bottleneck assignment problem

Dennis Fischer (), Komal Muluk () and Gerhard J. Woeginger ()
Additional contact information
Dennis Fischer: RWTH Aachen
Komal Muluk: RWTH Aachen
Gerhard J. Woeginger: RWTH Aachen

4OR, 2022, vol. 20, issue 4, No 6, 713-718

Abstract: Abstract We establish the NP-completeness of the variant of the bilevel assignment problem, where the leader and the follower both have bottleneck objective functions and were the follower behaves according to the optimistic rule. This result settles a problem that has been left open by Klinz & Gassner [4OR 7:379–394, 2009].

Keywords: Bilevel programming; Combinatorial optimization; Computational complexity (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10288-021-00499-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:aqjoor:v:20:y:2022:i:4:d:10.1007_s10288-021-00499-6

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-021-00499-6

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().