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

The sell or hold problem (SHP) is to sell $k$ out of $n$ 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\}$ ‐approximation algorithm is presented for the scenario‐based SHP.