An FPTAS for Stochastic Unbounded Min-Knapsack Problem

Zhihao Jiang, Haoyu Zhao

TL;DR

This paper introduces the first Fully Polynomial Time Approximation Scheme (FPTAS) for the Stochastic Unbounded Min-Knapsack Problem (Min-SUKP). This algorithm provides a near-optimal solution within a guaranteed time complexity, making it practical for real-world applications where item weights are uncertain.

What Problem Does This Paper Address?

The classic Min-Knapsack problem involves selecting items with fixed costs and weights to meet a minimum total weight requirement while minimizing total cost. This paper tackles a more complex variant: the Stochastic Unbounded Min-Knapsack Problem (Min-SUKP). In Min-SUKP, the weights of items are not fixed but are random variables following known distributions. Furthermore, there's an unlimited supply of each item type. This stochastic nature arises in scenarios like system maintenance, where components have uncertain lifespans (weights) and need to be replaced to ensure continuous operation (meeting a minimum total "lifespan" or weight). The challenge is to devise a strategy that minimizes expected costs despite this uncertainty.

Methods

The authors develop a Fully Polynomial Time Approximation Scheme (FPTAS) for Min-SUKP. The core of their approach involves several key steps:

  • Constant Factor Estimation: They first establish a rough, constant-factor approximation of the optimal cost. This provides a baseline for subsequent steps.
  • Discretization and Dynamic Programming: The problem is then tackled by discretizing the possible weights and employing dynamic programming. This is a standard technique in approximation algorithms for knapsack-like problems.
  • Handling "Cheap" vs. "Expensive" Items: A crucial innovation is how they handle items with low costs (cheap items). They group multiple "cheap" items into "blocks" to effectively transform them into "expensive" items. This allows them to leverage the dynamic programming approach more effectively.
  • Approximating Sum of Distributions: A significant technical challenge is computing the distribution of the sum of multiple random variables (representing the combined weight of blocked items). They introduce methods to efficiently compute approximate distribution arrays, avoiding the computational burden of exact calculations.
  • Restricted and Block Strategies: To manage the complexity, they introduce "restricted strategies" (where the number of items of a certain type is a multiple of a specific value) and "block strategies" (where multiple items are inserted together). They prove that these restricted strategies closely approximate the optimal solution.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging Deterministic and Stochastic: The paper successfully extends approximation techniques from deterministic knapsack problems to their stochastic counterparts, a non-trivial feat.
  • The Power of Blocking: Grouping "cheap" items into "blocks" is a clever way to manage the unbounded supply and stochastic weights, transforming a potentially intractable problem into one amenable to dynamic programming.
  • Efficient Distribution Summation: Developing methods to approximate the distribution of sums of random variables is a key technical contribution, essential for the overall FPTAS.
  • Guaranteed Approximation: The FPTAS guarantees that the computed solution's cost is within a $(1+\epsilon)$ factor of the true optimum, with a runtime polynomial in $n$, $\log W$, and $1/\epsilon$.

Key Results

The paper presents an FPTAS for the Stochastic Unbounded Min-Knapsack Problem. The main result is Theorem 3, which states that the algorithm's output $\hat{V}$ satisfies $(1-\epsilon)\text{OPT}_W \le \hat{V} \le (1+\epsilon)\text{OPT}_W$, where $\text{OPT}_W$ is the optimal value. Theorem 4 details the time complexity of the algorithm as $O\left(\frac{n^3 \log^2 W}{\epsilon^3} + \frac{n^2 \log W}{\epsilon^2}\right)$, which is polynomial in $n$, $\log W$, and $1/\epsilon$.

Limitations and Future Work

  • Assumption of Known Distributions: The algorithm assumes that the weight distributions of all item types are known. In practice, these distributions might be estimated or unknown, which would require further research.
  • Open Problems: The authors suggest several interesting avenues for future work, including designing PTAS or FPTAS for related problems such as:
  • 0/1 stochastic minimization knapsack problem
    • 0/1 stochastic maximization knapsack problem
    • Stochastic unbounded maximization knapsack problem

Summary updated

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+\epsilon )$$ times the optimum, and our algorithm runs in $$poly(1/\epsilon ,n,\log W)$$ time.
BibTeX
@inproceedings{jiang2019fptas,
  author = {Zhihao Jiang and Haoyu Zhao},
  title = {{An FPTAS for Stochastic Unbounded Min-Knapsack Problem}},
  booktitle = {FAW},
  year = {2019},
  url = {https://openreview.net/forum?id=yCARJw033No},
}
Figure