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

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 languageEnglish
Title of host publicationAlgorithmic Aspects in Information and Management
Subtitle of host publicationSecond International Conference, AAIM 2006, Hong Kong, China, June 20-22, 2006. Proceedings
EditorsSiu-Wing Cheng, Chung Keung Poon
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages207-219
Number of pages13
ISBN (Electronic)978-3-540-35158-0
ISBN (Print)978-3-540-35157-3
DOIs
Publication statusPublished - 2006
Event2nd International Conference on Algorithmic Aspects in Information and Management, AAIM 2006 - Hong Kong, Hong Kong
Duration: 20 Jun 200622 Jun 2006

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume4041
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference2nd International Conference on Algorithmic Aspects in Information and Management, AAIM 2006
Abbreviated titleAAIM
CountryHong Kong
CityHong Kong
Period20/06/0622/06/06

Fingerprint

Admission Control
Knapsack Problem
Control Policy
Penalty Function
Optimal Solution
Knapsack
Thinning
Linear Program
Simplify
Class
Policy

Keywords

  • IR-63811
  • METIS-238723
  • EWI-8533

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). Berlin, Heidelberg: 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",

}

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 proceedingConference contributionAcademicpeer-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

ER -

Gabor AF, van Ommeren J-KCW. Note on a class of admission control policies for the stochastic knapsack problem. In Cheng S-W, 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). https://doi.org/10.1007/11775096_20