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

The sell or hold problem (SHP) is to sell kk out of nn indivisible assets over two stages, with known first-stage prices and random second-stage prices, 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 show that SHP is polynomially solvable when the number of scenarios in the second stage is constant. A max{1/2,k/n}max{1/2,k/n}-approximation algorithm is presented for the scenario-based SHP.