Paper Info
Title
Complexity of the robust weighted independent set problems on interval graphs.
Abstract
This paper deals with the max–min and min–max regret versions of the maximum weighted independent set problem on interval graphs with uncertain vertex weights. Both problems have been recently investigated by Talla Nobibon and Leus (Optim Lett 8:227–235, 2014), who showed that they are NP-hard for two scenarios and strongly NP-hard if the number of scenarios is a part of the input. In this paper, new complexity and approximation results for the problems under consideration are provided, which extend the ones previously obtained. Namely, for the discrete scenario uncertainty representation it is proven that if the number of scenarios \(K\) is a part of the input, then the max–min version of the problem is not at all approximable. On the other hand, its min–max regret version is approximable within \(K\) and not approximable within \(O(\log ^{1-\epsilon }K)\) for any \(\epsilon >0\) unless the problems in NP have quasi polynomial algorithms. Furthermore, for the interval uncertainty representation it is shown that the min–max regret version is NP-hard and approximable within 2.
Year
DOI
Venue
2014
10.1007/s11590-014-0773-3
Optimization Letters
Keywords
DocType
Volume
Robust optimization, Independent set, Interval graph, Computational complexity
Journal
9
Issue
ISSN
Citations 
3
1862-4480
0
PageRank 
References 
Authors
0.34
6
2
Name
Order
Citations
PageRank
Adam Kasperski135233.64
Paweł Zieliński222728.62