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

Qie He; Shabbir Ahmed; George L. Nemhauser

doi:10.1016/j.orl.2011.11.007

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

Qie He, Shabbir Ahmed, George L. Nemhauser

Industrial and Systems Engineering

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

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 max12,kn-approximation algorithm is presented for the scenario-based SHP.

Original language	English (US)
Pages (from-to)	69-73
Number of pages	5
Journal	Operations Research Letters
Volume	40
Issue number	2
DOIs	https://doi.org/10.1016/j.orl.2011.11.007
State	Published - Mar 2012

Bibliographical note

Funding Information:
This work is supported by NSF grant CMMI-0758234 awarded to the Georgia Institute of Technology.

Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.

Keywords

Approximation algorithm
Integer programming
Stochastic programming
Submodular maximization

Publisher link

10.1016/j.orl.2011.11.007

Find It

Find It at U of M Libraries

Cite this

@article{7e315a101d5241589c1b66a5f2f8d922,

title = "Sell or Hold: A simple two-stage stochastic combinatorial optimization problem",

abstract = "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 max12,kn-approximation algorithm is presented for the scenario-based SHP.",

keywords = "Approximation algorithm, Integer programming, Stochastic programming, Submodular maximization",

author = "Qie He and Shabbir Ahmed and Nemhauser, {George L.}",

year = "2012",

month = mar,

doi = "10.1016/j.orl.2011.11.007",

language = "English (US)",

volume = "40",

pages = "69--73",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Sell or Hold

T2 - A simple two-stage stochastic combinatorial optimization problem

AU - He, Qie

AU - Ahmed, Shabbir

AU - Nemhauser, George L.

PY - 2012/3

Y1 - 2012/3

N2 - 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 max12,kn-approximation algorithm is presented for the scenario-based SHP.

AB - 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 max12,kn-approximation algorithm is presented for the scenario-based SHP.

KW - Approximation algorithm

KW - Integer programming

KW - Stochastic programming

KW - Submodular maximization

UR - http://www.scopus.com/inward/record.url?scp=84856595737&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84856595737&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2011.11.007

DO - 10.1016/j.orl.2011.11.007

M3 - Article

AN - SCOPUS:84856595737

SN - 0167-6377

VL - 40

SP - 69

EP - 73

JO - Operations Research Letters

JF - Operations Research Letters

IS - 2

ER -

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

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this