Abstract. In this paper, we study the stochastic unbounded min-knapsack problem (Min-SUKP). The ordinary unbounded min-knapsack problem states that: There are n types of items, and there is an infinite number of items of each type. The items of the same type have the same cost and weight. We want to choose a set of items such that the total weight is at least W and the total cost is minimized. The Min-SUKP generalizes the ordinary unbounded min-knapsack problem to the stochastic setting, where the weight of each item is a random variable following a known distribution and the items of the same type follow the same weight distribution. In Min-SUKP, different types of items may have different cost and weight distributions. In this paper, we provide an FPTAS for Min-SUKP, i.e., the approximate value our algorithm computes is at most (1 + ǫ) times the optimum, and our algorithm runs in poly(1/ǫ, n, log W ) time.
e unbounded version of Stoch-Knapsack Cover (each item has infinite number of copies) was studied by REF and they provide an FPTAS for this problem.
An FPTAS for Stochastic Unbounded Min-Knapsack Problem
In Chen Y., Deng X., Lu M. (eds) Frontiers in Algorithmics. FAW 2019. Lecture Notes in Computer Science, vol 11458. Springer, Cham
Computer Science Mathematics