Optimization Online


Sell or Hold: a simple two-stage stochastic combinatorial optimization problem

Qie He(qie.he***at***gatech.edu)
Shabbir Ahmed(sahmed***at***isye.gatech.edu)
George L. Nemhauser(gnemhaus***at***isye.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


Download: [PDF]

Entry Submitted: 08/12/2011
Entry Accepted: 08/13/2011
Entry Last Modified: 08/12/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society