Loading...
Please wait, while we are loading the content...
Similar Documents
Improved approximation results for stochastic knapsack problems (2011)
| Content Provider | CiteSeerX |
|---|---|
| Author | Bhalgat, Anand Goel, Ashish Khanna, Sanjeev |
| Description | In SODA In the stochastic knapsack problem, we are given a set of items each associated with a probability distribution on sizes and a profit, and a knapsack of unit capacity. The size of an item is revealed as soon as it is inserted into the knapsack, and the goal is to design a policy that maximizes the expected profit of items that are successfully inserted into the knapsack. The stochastic knapsack problem is a natural generalization of the classical knapsack problem, and arises in many applications, including bandwidth allocation, budgeted learning, and scheduling. An adaptive policy for stochastic knapsack specifies the next item to be inserted based on observed sizes of the items inserted thus far. The adaptive policy can have an exponentially large explicit description and is known to be |
| File Format | |
| Language | English |
| Publisher Date | 2011-01-01 |
| Access Restriction | Open |
| Subject Keyword | Stochastic Knapsack Stochastic Knapsack Problem Approximation Result Adaptive Policy Many Application Natural Generalization Next Item Classical Knapsack Problem Observed Size Bandwidth Allocation Expected Profit Large Explicit Description Unit Capacity Probability Distribution |
| Content Type | Text |
| Resource Type | Article |
