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

Mathematics

University of Twente

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

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	British English
Title of host publication	Algorithmic Aspects in Information and Management - Second International Conference, AAIM 2006, Proceedings
Publisher	Springer Verlag
Pages	207-219
Number of pages	13
ISBN (Print)	3540351574, 9783540351573
DOIs	https://doi.org/10.1007/11775096_20
State	Published - 2006
Event	2nd International Conference on Algorithmic Aspects in Information and Management, AAIM 2006 - Hong Kong, China Duration: 20 Jun 2006 → 22 Jun 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4041 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

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

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 Algorithmic Aspects in Information and Management - Second International Conference, AAIM 2006, Proceedings (pp. 207-219). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4041 LNCS). Springer Verlag. 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, Proceedings. Springer Verlag, 2006. pp. 207-219 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{32286a4729ad48da8e369a2c2e93f886,

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.",

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

year = "2006",

doi = "10.1007/11775096\_20",

language = "British English",

isbn = "3540351574",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "207--219",

booktitle = "Algorithmic Aspects in Information and Management - Second International Conference, AAIM 2006, Proceedings",

address = "Germany",

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

}

Gabor, AF & Van Ommeren, JKCW 2006, Note on a class of admission control policies for the stochastic knapsack problem. in Algorithmic Aspects in Information and Management - Second International Conference, AAIM 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4041 LNCS, Springer Verlag, pp. 207-219, 2nd International Conference on Algorithmic Aspects in Information and Management, AAIM 2006, Hong Kong, China, 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, Proceedings. Springer Verlag, 2006. p. 207-219 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4041 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › 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.

UR - https://www.scopus.com/pages/publications/33746266625

U2 - 10.1007/11775096_20

DO - 10.1007/11775096_20

M3 - Conference contribution

AN - SCOPUS:33746266625

SN - 3540351574

SN - 9783540351573

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 207

EP - 219

BT - Algorithmic Aspects in Information and Management - Second International Conference, AAIM 2006, Proceedings

PB - Springer Verlag

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 Algorithmic Aspects in Information and Management - Second International Conference, AAIM 2006, Proceedings. Springer Verlag. 2006. p. 207-219. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11775096_20

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

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this