Thumbnail

Some tractable instances of interval data minmax regret problems: bounded distance from triviality

Escoffier, Bruno; Monnot, Jérôme; Spanjaard, Olivier (2008), Some tractable instances of interval data minmax regret problems: bounded distance from triviality, in Geffert, Viliam; Karhumäki, Juhani; Bertoni, Alberto; Preneel, Bart; Navrat, Pavol; Bielikova, Maria, SOFSEM 2008: Theory and Practice of Computer Science 34th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 19-25, 2008, Proceedings, Springer : Berlin, p. 280-291. http://dx.doi.org/10.1007/978-3-540-77566-9_24

View/Open
Type
Communication / Conférence
Date
2008
Conference title
34th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'08)
Conference date
2008-01
Conference city
Nový Smokovec
Conference country
Slovaquie
Book title
SOFSEM 2008: Theory and Practice of Computer Science 34th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 19-25, 2008, Proceedings
Book author
Geffert, Viliam; Karhumäki, Juhani; Bertoni, Alberto; Preneel, Bart; Navrat, Pavol; Bielikova, Maria
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
4910
Published in
Berlin
ISBN
978-3-540-77565-2
Number of pages
792
Pages
280-291
Publication identifier
Metadata
Show full item record
Author(s)
Escoffier, Bruno
Monnot, Jérôme cc
Spanjaard, Olivier
Abstract (EN)
This paper focuses on tractable instances of interval data minmax regret graph problems. More precisely, we provide polynomial and pseudopolynomial algorithms for sets of particular instances of the interval data minmax regret versions of the shortest path, minimum spanning tree and weighted (bipartite) perfect matching problems. These sets 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. Two kinds of parameters are investigated, measuring either the distance from special weight structures or the distance from special graph structures.
Subjects / Keywords
Robust optimization; Interval data; Shortest path; Spanning tree; Bipartite perfect matching