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 contributionpeer-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 languageBritish English
Title of host publicationAlgorithmic Aspects in Information and Management - Second International Conference, AAIM 2006, Proceedings
PublisherSpringer Verlag
Pages207-219
Number of pages13
ISBN (Print)3540351574, 9783540351573
DOIs
StatePublished - 2006
Event2nd International Conference on Algorithmic Aspects in Information and Management, AAIM 2006 - Hong Kong, China
Duration: 20 Jun 200622 Jun 2006

Publication series

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

Conference

Conference2nd International Conference on Algorithmic Aspects in Information and Management, AAIM 2006
Country/TerritoryChina
CityHong Kong
Period20/06/0622/06/06

Fingerprint

Dive into the research topics of 'Note on a class of admission control policies for the stochastic knapsack problem'. Together they form a unique fingerprint.

Cite this