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

Voir/Ouvrir
Type
Article accepté pour publication ou publié
Date
2008
Nom de la revue
Operations Research Letters
Volume
36
Numéro
4
Éditeur
Elsevier
Pages
424-429
Identifiant publication
Métadonnées
Afficher la notice complète
Auteur(s)
Escoffier, Bruno
Monnot, Jérôme cc
Spanjaard, Olivier
Résumé (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.
Mots-clés
Bipartite perfect matching; Spanning tree; Shortest path; Interval data; Robust optimization