Note on a class of admission control policies for the stochastic knapsack problem

Adriana F. Gabor; Jan-Kees C.W. van Ommeren

doi:10.1007/11775096_20

Note on a class of admission control policies for the stochastic knapsack problem

Adriana F. Gabor, Jan-Kees C.W. van Ommeren

Stochastic Operations Research

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

9 Downloads (Pure)

Abstract

In this note we discuss a class of exponential penalty function policies recently proposed by Iyengar and Sigman for controlling a stochastic knapsack. These policies are based on the optimal solution of some related deterministic linear programs. By finding explicitly their optimal solution, we reinterpret the exponential penalty function policies and show that they belong to the class of threshold policies. This explains their good practical behavior, facilitates the comparison with the thinning policy, simplifies considerably their analysis and improves the bounds previously proposed.

Original language	English
Title of host publication	Algorithmic Aspects in Information and Management
Subtitle of host publication	Second International Conference, AAIM 2006, Hong Kong, China, June 20-22, 2006. Proceedings
Editors	Siu-Wing Cheng, Chung Keung Poon
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	207-219
Number of pages	13
ISBN (Electronic)	978-3-540-35158-0
ISBN (Print)	978-3-540-35157-3
DOIs	https://doi.org/10.1007/11775096_20
Publication status	Published - 2006
Event	2nd International Conference on Algorithmic Aspects in Information and Management, AAIM 2006 - Hong Kong, Hong Kong Duration: 20 Jun 2006 → 22 Jun 2006

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	4041
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	2nd International Conference on Algorithmic Aspects in Information and Management, AAIM 2006
Abbreviated title	AAIM
Country/Territory	Hong Kong
City	Hong Kong
Period	20/06/06 → 22/06/06

Keywords

IR-63811
METIS-238723
EWI-8533

Access to Document

10.1007/11775096_20

Cite this

Gabor, A. F., & van Ommeren, J.-K. C. W. (2006). Note on a class of admission control policies for the stochastic knapsack problem. In S.-W. Cheng, & C. K. Poon (Eds.), Algorithmic Aspects in Information and Management: Second International Conference, AAIM 2006, Hong Kong, China, June 20-22, 2006. Proceedings (pp. 207-219). (Lecture Notes in Computer Science; Vol. 4041). Springer. https://doi.org/10.1007/11775096_20

Gabor, Adriana F. ; van Ommeren, Jan-Kees C.W. / Note on a class of admission control policies for the stochastic knapsack problem. Algorithmic Aspects in Information and Management: Second International Conference, AAIM 2006, Hong Kong, China, June 20-22, 2006. Proceedings. editor / Siu-Wing Cheng ; Chung Keung Poon. Berlin, Heidelberg : Springer, 2006. pp. 207-219 (Lecture Notes in Computer Science).

@inproceedings{74b96ab3b0734709838567835744363a,

title = "Note on a class of admission control policies for the stochastic knapsack problem",

abstract = "In this note we discuss a class of exponential penalty function policies recently proposed by Iyengar and Sigman for controlling a stochastic knapsack. These policies are based on the optimal solution of some related deterministic linear programs. By finding explicitly their optimal solution, we reinterpret the exponential penalty function policies and show that they belong to the class of threshold policies. This explains their good practical behavior, facilitates the comparison with the thinning policy, simplifies considerably their analysis and improves the bounds previously proposed.",

keywords = "IR-63811, METIS-238723, EWI-8533",

author = "Gabor, {Adriana F.} and {van Ommeren}, {Jan-Kees C.W.}",

year = "2006",

doi = "10.1007/11775096_20",

language = "English",

isbn = "978-3-540-35157-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "207--219",

editor = "Siu-Wing Cheng and Poon, {Chung Keung}",

booktitle = "Algorithmic Aspects in Information and Management",

address = "Germany",

note = "2nd International Conference on Algorithmic Aspects in Information and Management, AAIM 2006, AAIM ; Conference date: 20-06-2006 Through 22-06-2006",

}

Gabor, AF & van Ommeren, J-KCW 2006, Note on a class of admission control policies for the stochastic knapsack problem. in S-W Cheng & CK Poon (eds), Algorithmic Aspects in Information and Management: Second International Conference, AAIM 2006, Hong Kong, China, June 20-22, 2006. Proceedings. Lecture Notes in Computer Science, vol. 4041, Springer, Berlin, Heidelberg, pp. 207-219, 2nd International Conference on Algorithmic Aspects in Information and Management, AAIM 2006, Hong Kong, Hong Kong, 20/06/06. https://doi.org/10.1007/11775096_20

Note on a class of admission control policies for the stochastic knapsack problem. / Gabor, Adriana F.; van Ommeren, Jan-Kees C.W.
Algorithmic Aspects in Information and Management: Second International Conference, AAIM 2006, Hong Kong, China, June 20-22, 2006. Proceedings. ed. / Siu-Wing Cheng; Chung Keung Poon. Berlin, Heidelberg: Springer, 2006. p. 207-219 (Lecture Notes in Computer Science; Vol. 4041).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Note on a class of admission control policies for the stochastic knapsack problem

AU - Gabor, Adriana F.

AU - van Ommeren, Jan-Kees C.W.

PY - 2006

Y1 - 2006

N2 - In this note we discuss a class of exponential penalty function policies recently proposed by Iyengar and Sigman for controlling a stochastic knapsack. These policies are based on the optimal solution of some related deterministic linear programs. By finding explicitly their optimal solution, we reinterpret the exponential penalty function policies and show that they belong to the class of threshold policies. This explains their good practical behavior, facilitates the comparison with the thinning policy, simplifies considerably their analysis and improves the bounds previously proposed.

AB - In this note we discuss a class of exponential penalty function policies recently proposed by Iyengar and Sigman for controlling a stochastic knapsack. These policies are based on the optimal solution of some related deterministic linear programs. By finding explicitly their optimal solution, we reinterpret the exponential penalty function policies and show that they belong to the class of threshold policies. This explains their good practical behavior, facilitates the comparison with the thinning policy, simplifies considerably their analysis and improves the bounds previously proposed.

KW - IR-63811

KW - METIS-238723

KW - EWI-8533

U2 - 10.1007/11775096_20

DO - 10.1007/11775096_20

M3 - Conference contribution

SN - 978-3-540-35157-3

T3 - Lecture Notes in Computer Science

SP - 207

EP - 219

BT - Algorithmic Aspects in Information and Management

A2 - Cheng, Siu-Wing

A2 - Poon, Chung Keung

PB - Springer

CY - Berlin, Heidelberg

T2 - 2nd International Conference on Algorithmic Aspects in Information and Management, AAIM 2006

Y2 - 20 June 2006 through 22 June 2006

ER -

Gabor AF, van Ommeren JKCW. Note on a class of admission control policies for the stochastic knapsack problem. In Cheng SW, Poon CK, editors, Algorithmic Aspects in Information and Management: Second International Conference, AAIM 2006, Hong Kong, China, June 20-22, 2006. Proceedings. Berlin, Heidelberg: Springer. 2006. p. 207-219. (Lecture Notes in Computer Science). doi: 10.1007/11775096_20

Note on a class of admission control policies for the stochastic knapsack problem

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this