𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Hassene Aissi; Cristina Bazgan; Daniel Vanderpooten

Publisher
Elsevier Science
Year
2005
Tongue
English
Weight
179 KB
Volume
33
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

On max-min problems
On max-min problems
✍ Kailash C. Kapur 📂 Article 📅 1973 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB
Solving min-max problems and linear semi
Solving min-max problems and linear semi-infinite programs
✍ S.-C. Fang; Soon-Yi Wu 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 309 KB

For a min-max problem in the form of minxEx maxtET {A(X)}, the nondi\_fferentiability of the max function F(x) --maxtET {ft(x)} presents special difficulty in finding optimal solutions. We show that an entropic regularization procedure can provide a smooth approximation Fp(x) that uniformly converge