- Sell or Hold: a simple two-stage stochastic combinatorial optimization problem Qie He(qie.hegatech.edu) Shabbir Ahmed(sahmedisye.gatech.edu) George L. Nemhauser(gnemhausisye.gatech.edu) Abstract: There are $n$ individual assets and $k$ of them are to be sold over two stages. The first-stage prices are known and the second-stage prices have a known distribution. The sell or hold problem (SHP) is to determine which assets are to be sold at each stage to maximize the total expected revenue. We show that SHP is NP-hard when the second-stage prices are realized as a finite set of scenarios. We also identify a polynomially solvable case of SHP when the number of scenarios in the second stage is constant. A $\max\{\frac{1}{2},\frac{k}{n}\}$-approximation algorithm is presented for the scenario-based SHP. An example shows that the bound is tight. Keywords: stochastic programming; integer programming; submodular maximization; approximation algorithm Category 1: Stochastic Programming Category 2: Integer Programming Category 3: Combinatorial Optimization Citation: Download: [PDF]Entry Submitted: 08/12/2011Entry Accepted: 08/13/2011Entry Last Modified: 08/12/2011Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.