| Article ID: | iaor1989263 |
| Country: | Switzerland |
| Volume: | 18 |
| Start Page Number: | 17 |
| End Page Number: | 23 |
| Publication Date: | Feb 1989 |
| Journal: | Annals of Operations Research |
| Authors: | Rinnooy Kan Alexander H.G., Stougie Leen |
| Keywords: | complexity |
In practical problem situations data are usually inherently unreliable. A mathematical representation of uncertainty leads to stochastic optimization problems. In this paper the complexity of stochastic combinatorial optimization problems is discussed. Surprisingly, certain stochastic versions of NP-hard deterministic combinatorial problems appear to be solvable in polynomial time.