Thumbnail

Some tractable instances of interval data minmax regret problems

Escoffier, Bruno; Monnot, Jérôme; Spanjaard, Olivier (2008), Some tractable instances of interval data minmax regret problems, Operations Research Letters, 36, 4, p. 424-429. http://dx.doi.org/10.1016/j.orl.2007.12.004

View/Open
Type
Article accepté pour publication ou publié
Date
2008
Journal name
Operations Research Letters
Volume
36
Number
4
Publisher
Elsevier
Pages
424-429
Publication identifier
Metadata
Show full item record
Author(s)
Escoffier, Bruno
Monnot, Jérôme cc
Spanjaard, Olivier
Abstract (EN)
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.
Subjects / Keywords
Bipartite perfect matching; Spanning tree; Shortest path; Interval data; Robust optimization