Thumbnail

Pseudo-polynomial algorithms for min-max and min-max regret problems

Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2005), Pseudo-polynomial algorithms for min-max and min-max regret problems, in Xian-Sun, Zhang, Operations Research and Its Applications. The Fifth International Symposium, ISORA’05 Tibet, China, August 8–13, 2005 Proceedings, World Publishing Corporation, p. 171-178

View/Open
Type
Communication / Conférence
Date
2005
Conference country
CHINA
Book title
Operations Research and Its Applications. The Fifth International Symposium, ISORA’05 Tibet, China, August 8–13, 2005 Proceedings
Book author
Xian-Sun, Zhang
Publisher
World Publishing Corporation
ISBN
7-5062-7277-6
Pages
171-178
Metadata
Show full item record
Author(s)
Aissi, Hassene

Bazgan, Cristina

Vanderpooten, Daniel
Abstract (EN)
We present in this paper general pseudo-polynomial time algorithms to solve min-maxand min-max regret versions of some polynomial or pseudo-polynomial problems undera constant number of scenarios. Using easily computable bounds, we can improve thesealgorithms. This way we provide pseudo-polynomial algorithms for the min-max and andmin-max regret versions of several classical problems including minimum spanning tree,shortest path, and knapsack.
Subjects / Keywords
min-max; pseudo-polynomial; computational complexity; min-max regret