Reference : Robust maximum weighted independent-set problems on interval graphs

	Document type :	Reports : Internal report
	Discipline(s) :	Business & economic sciences : Quantitative methods in economics & management
	To cite this reference:	http://hdl.handle.net/2268/98608

Title :	Robust maximum weighted independent-set problems on interval graphs
Language :	English
Author, co-author :	Talla Nobibon, Fabrice [Université de Liège - ULg > HEC-Ecole de gestion de l'ULg : UER > UER Opérations : Supply Chain Management >]
	Leus, Roel [ > > ]
Publication date :	2011
Keywords :	[en] 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.
Target :	Researchers ; Professionals ; Students ; General public
Permalink :	http://hdl.handle.net/2268/98608

	File(s) associated to this reference
	Fulltext file(s): File Commentary Version Size Access Open access robust_MW1C - modif Roel.pdf Author preprint 299.46 kB View/Open

All documents in ORBi are protected by a user license.

 

© ULg Library Network |  Feedback |  ORBi legal notices

Dspace v1.5