The stochastic knapsack problem

DOI10.1109/26.31166zbMath0675.90066OpenAlexW2115728730MaRDI QIDQ3830820

Danny H. K. Tsang, Keith W. Ross

Publication date: 1989

Published in: IEEE Transactions on Communications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/26.31166

zbMATH Keywords

knapsack problemlong-run average profitstochastic versionindependent birth processesthreshold type optimal control

Mathematics Subject Classification ID

Integer programming (90C10) Stochastic programming (90C15) Dynamic programming (90C39) Markov and semi-Markov decision processes (90C40)

Related Items (25)

An adaptive stochastic knapsack problem ⋮ Exact algorithms for the 0-1 time-bomb knapsack problem ⋮ An approximate dynamic programming approach to solving a dynamic, stochastic multiple knapsack problem ⋮ Multi-class, multi-resource advance scheduling with no-shows, cancellations and overbooking ⋮ Ameso optimization: a relaxation of discrete midpoint convexity ⋮ Optimization via trunk reservation in single resource loss systems under heavy traffic ⋮ Optimal patient and personnel scheduling policies for care-at-home service facilities ⋮ The traveling purchaser problem with stochastic prices: exact and approximate algorithms ⋮ STATIC STOCHASTIC KNAPSACK PROBLEMS ⋮ The stochastic generalized bin packing problem ⋮ On two-stage stochastic knapsack problems ⋮ Unnamed Item ⋮ Cutting stock problems with nondeterministic item lengths: a new approach to server consolidation ⋮ Lagrangian relaxation and constraint generation for allocation and advanced scheduling ⋮ A heuristic approach for allocation of data to RFID tags: a data allocation knapsack problem (DAKP) ⋮ Exponential penalty function control of loss networks ⋮ Upper bounds for the 0-1 stochastic knapsack problem and a B\&B algorithm ⋮ A single-resource allocation problem with Poisson resource requirements ⋮ Optimal road maintenance investment in traffic networks with random demands ⋮ Optimal access control for broadband services: Stochastic knapsack with advance information ⋮ The asymptotic value-to-capacity ratio for the multi-class stochastic knapsack problem ⋮ An agent-based stochastic ruler approach for a stochastic knapsack problem with sequential competition ⋮ An optimal stopping policy for car rental businesses with purchasing customers ⋮ Narrowing the search for optimal call-admission policies via a nonlinear stochastic knapsack model ⋮ A critically loaded multiclass Erlang loss system

This page was built for publication: The stochastic knapsack problem