A priori optimization for the probabilistic maximum independent set problem
Murat, Cécile; Paschos, Vangelis (2002), A priori optimization for the probabilistic maximum independent set problem, Theoretical Computer Science, 270, 1-2, p. 561-590. http://dx.doi.org/10.1016/S0304-3975(01)00005-6
TypeArticle accepté pour publication ou publié
Journal nameTheoretical Computer Science
MetadataShow full item record
Abstract (EN)We first propose a formal definition for the concept of probabilistic combinatorial optimization problem (under the a priori method). Next, we study the complexity of optimally solving probabilistic maximum independent set problem under several a priori optimization strategies as well as the complexity of approximating optimal solutions. For the different strategies studied, we present results about the restriction of probabilistic independent set on bipartite graphs.
Subjects / KeywordsIndependent set; Polynomial approximation; NP-hard problem; Probabilistic optimization
Showing items related by title and author.