A note on the complexity of the bilevel bottleneck assignment problem

4OR, vol. 20, pp. 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].

Authors 3

1. Dennis Fischer corresponding Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen, Aachen, Germany

2. Komal Muluk Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen, Aachen, Germany

3. Gerhard J. Woeginger Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen, Aachen, Germany