טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentCook Enosh
SubjectAdaptivity in the Stochastic Covering Knapsack Problem
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Asaf Levin
Full Thesis textFull thesis text - English Version


Abstract

The covering knapsack problem is the following problem. The input consists of a set of items each of which is associated with a non-negative cost and a non-negative size, and the goal is to find a minimum-cost subset of these items whose total size is at least 1. In our stochastic model the costs are deterministic while the sizes are random variables with known, arbitrary distributions and these random variables are mutually independent. The goal is to compute a policy that minimizes the expected cost of items covering the total size of 1, where the first item to overflow the knapsack terminates the process of selecting items. Once an item is placed in the knapsack, the realization of its size is revealed (and is not changed later).

An adaptive policy decides upon the next action according to the realizations of the random variables which became known in previous stages of the optimization procedure while a non-adaptive policy is a permutation of the items. We examine the adaptivity gap, i.e., the supremum ratio between the expected cost of an optimal non-adaptive policy and the expected cost of an optimal adaptive policy, where the supremum is over all possible instances in the model. The main subject of this research is bounding the adaptivity gap.