On the robust assignment problem under a fixed number of cost scenarios

V.G. Deineko, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

24 Citations (Scopus)
2 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)175-179
JournalOperations Research Letters
Volume34
Issue number2
DOIs
Publication statusPublished - 2006

Fingerprint

Dive into the research topics of 'On the robust assignment problem under a fixed number of cost scenarios'. Together they form a unique fingerprint.

Cite this