Browsing by Author "Kong, Nan"

Now showing items 1-2 of 2

2004-02-19Buch

A factor 1/2 approximation algorithm for a class of two-stage stochastic mixed-integer programs

Kong, Nan; Schaefer, Andrew J.

Abstract We introduce the two-stage stochastic maximum-weight matching problem and demonstrate that this problem is NP-complete. We give a factor 1/2 approximation algorithm and prove its correctness. We also provide a ...
2004-10-02Buch

Two-stage integer programs with stochastic right-hand sides

Kong, Nan; Schaefer, Andrew J.; Hunsaker, Brady

We consider two-stage pure integer programs with discretely distributed stochastic right-hand sides. We present an equivalent superadditive dual formulation that uses the value functions in both stages. We give two algorithms ...