A priori optimization for the probabilistic maximum independent set problem (Q5958320)
From MaRDI portal
scientific article; zbMATH DE number 1715321
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A priori optimization for the probabilistic maximum independent set problem |
scientific article; zbMATH DE number 1715321 |
Statements
A priori optimization for the probabilistic maximum independent set problem (English)
0 references
3 March 2002
0 references
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.
0 references
probabilistic optimization
0 references
NP-hard problem
0 references
independent set
0 references
polynomial approximation
0 references
0 references
