  


Sell or Hold: a simple twostage stochastic combinatorial optimization problem
Qie He(qie.hegatech.edu) Abstract: There are $n$ individual assets and $k$ of them are to be sold over two stages. The firststage prices are known and the secondstage 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 NPhard when the secondstage 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 scenariobased 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/2011 Modify/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  