| Article ID: | iaor20102853 |
| Volume: | 36 |
| Issue: | 4 |
| Start Page Number: | 424 |
| End Page Number: | 429 |
| Publication Date: | Jul 2008 |
| Journal: | Operations Research Letters |
| Authors: | Monnot Jrme, Spanjaard Olivier, Escoffier Bruno |
| Keywords: | minimax problem |
In this paper, we provide polynomial and pseudopolynomial algorithms for classes of particular instances of interval data minmax regret graph problems. These classes are defined using a parameter that measures the distance from well-known solvable instances. Tractable cases occur when the parameter is bounded by a constant.