Reference : Robust maximum weighted independent-set problems on interval graphs
Reports : Internal report
Business & economic sciences : Quantitative methods in economics & management
Robust maximum weighted independent-set problems on interval graphs
Talla Nobibon, Fabrice [Université de Liège - ULiège > HEC-Ecole de gestion : UER > UER Opérations : Supply Chain Management >]
Leus, Roel mailto [ > > ]
[en] computational complexity ; interval graphs ; independent set ; dynamic programming
[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.
Researchers ; Professionals ; Students ; General public

File(s) associated to this reference

Fulltext file(s):

Open access
robust_MW1C - modif Roel.pdfAuthor preprint299.46 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.