Internal report (Reports)
Robust maximum weighted independent-set problems on interval graphs
Talla Nobibon, Fabrice; Leus, Roel
2011
 

Files


Full Text
robust_MW1C - modif Roel.pdf
Author preprint (306.65 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
computational complexity; interval graphs; independent set; dynamic programming
Abstract :
[en] We study the maximum weighted independent-set problem on interval graphs with uncertainty on the vertex weights. We use the absolute robustness criterion and the min-max regret criterion to evaluate solutions. For a discrete scenario set, we nd that the problem is NP-hard for each of the robustness criteria; we also provide pseudo-polynomial time algorithms when there is a constant number of scenarios and show that the problem is strongly NP-hard when the set of scenarios is unbounded. When the scenario set is a Cartesian product, we prove that the problem is equivalent to a maximum weighted independent-set problem on the same interval graph but without uncertainty for the rst objective function and that the scenario set can be reduced for the second objective function.
Disciplines :
Quantitative methods in economics & management
Author, co-author :
Talla Nobibon, Fabrice ;  Université de Liège - ULiège > HEC-Ecole de gestion : UER > UER Opérations : Supply Chain Management
Leus, Roel
Language :
English
Title :
Robust maximum weighted independent-set problems on interval graphs
Publication date :
2011
Available on ORBi :
since 12 September 2011

Statistics


Number of views
91 (1 by ULiège)
Number of downloads
287 (0 by ULiège)

Bibliography


Similar publications



Contact ORBi