A priori optimization for the probabilistic maximum independent set problem
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. (C) 2002 Elsevier Science B.V. All rights reserved.
independent set probabilistic optimization np-hard problem polynomial approximation