Browsing by Author "Schaefer, Andrew J."

Now showing items 1-3 of 3

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 ...
2002-04-23Buch

A stochastic intra-ring synchronous optimal network design problem

Cole, J.; Schaefer, Andrew J.; Yen, Joyce W.

We develop a stochastic programming approach to solving an intra-ring Synchronous Optical Network (SONET) design problem. This research differs from pioneering SONET design studies in two fundamental ways. First, while ...
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 ...