A note on the complexity of the bilevel bottleneck assignment problem
Dennis Fischer, Komal Muluk, Gerhard J. Woeginger · 4OR · 2021
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].