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

A.F. Gabor, J.C.W. Ommeren, van

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review


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.
Originele taal-2Engels
TitelAlgorithmic Aspects in Information and Management (Proceedings Second International Conference, AAIM'06, Hong Kong, June 20-22, 2006)
RedacteurenS.W. Cheng, C.K. Poon
Plaats van productieBerlin
ISBN van geprinte versie3-540-35157-4
StatusGepubliceerd - 2006

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743

Vingerafdruk Duik in de onderzoeksthema's van 'Note on a class of admission control policies for the stochastic knapsack problem'. Samen vormen ze een unieke vingerafdruk.

Citeer dit