A note on the complexity of the bilevel bottleneck assignment problem

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].

MoreLess

Year of publication:	2021
Authors:	Fischer, Dennis ; Muluk, Komal ; Woeginger, Gerhard J.
Published in:	4OR. - Berlin, Heidelberg : Springer, ISSN 1614-2411. - Vol. 20.2021, 4, p. 713-718
Publisher:	Berlin, Heidelberg : Springer
Subject:	Bilevel programming \| Combinatorial optimization \| Computational complexity

More details

Type of publication:	Article
Type of publication (narrower categories):	Article
Language:	English
Other identifiers:	10.1007/s10288-021-00499-6 [DOI] hdl:10419/286750 [Handle]
Source:	EconStor

Persistent link: https://www.econbiz.de/10014497495