Complexity of the min–max and min–max regret assignment problems

Complexity of the min–max and min–max regret assignment problems

0.00 Avg rating0 Votes
Article ID: iaor2006921
Country: Netherlands
Volume: 33
Issue: 6
Start Page Number: 634
End Page Number: 640
Publication Date: Nov 2005
Journal: Operations Research Letters
Authors: , ,
Keywords: optimization, programming: assignment
Abstract:

This paper investigates the complexity of the min–max and min–max regret assignment problems both in the discrete scenario and interval data cases. We show that these problems are strongly NP-hard for an unbounded number of scenarios. We also show that the interval data min–max regret assignment problem is strongly NP-hard.

Reviews

Required fields are marked *. Your email address will not be published.