Complexity of the robust weighted independent set problems on interval graphs

DOI10.1007/S11590-014-0773-3MaRDI QIDQ2018858zbMATH OpenOpenAlexWikidataFDO

Authors Adam Kasperski, Paweł Zieliński

Publication date 25 March 2015

Published in Optimization Letters (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1405.5376

zbMATH Keywords

computational complexityindependent setinterval graphrobust optimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Minimax problems in mathematical programming (90C47) Abstract computational complexity for mathematical programming problems (90C60)

Abstract: This paper deals with the max-min and min-max regret versions of the maximum weighted independent set problem on interval graphswith uncertain vertex weights. Both problems have been recently investigated by Nobibon and Leus (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 on 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(lo{g}^{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.

Recommendations

• Robust maximum weighted independent-set problems on interval graphs
• On the complexity of a class of combinatorial optimization problems with uncertainty
• The computational complexity of the relative robust shortest path problem with interval data
• Independent sets and vertex covers considered within the context of robust optimization
• Complexity of the min-max and min-max regret assignment problems

Cites work

• A sequential algorithm for finding a maximum weightK-independent set on interval graphs
• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• Discrete optimization with interval data. Minmax regret and fuzzy approach
• General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Robust discrete optimization and its applications
• Robust maximum weighted independent-set problems on interval graphs
• Selection of programme slots of television channels for giving advertisement: a graph theoretic approach
• Single machine scheduling with scenarios

Cited in

(4)

• Robust maximum weighted independent-set problems on interval graphs
• Independent sets and vertex covers considered within the context of robust optimization
• Computing the weighted neighbor isolated tenacity of interval graphs in polynomial time
• Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty

This page was built for publication: Complexity of the robust weighted independent set problems on interval graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2018858)