| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1143414 | Operations Research Letters | 2006 | 5 Pages |
Abstract
We investigate the complexity of the min–max assignment problem under a fixed number of scenarios. We prove that this problem is polynomial-time equivalent to the exact perfect matching problem in bipartite graphs, an infamous combinatorial optimization problem of unknown computational complexity.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Vladimir G. Deı˘neko, Gerhard J. Woeginger,