A Competitive Analysis of Online Knapsack Problems with Unit Density

Will Ma, David Simchi-Levi, Jinglong ZhaoarXiv 2019 · OpenReview

Introduction

In modern logistics and supply chain management, the "online unit-density knapsack problem" represents a fundamental challenge. A supplier must decide in real-time whether to accept or reject incoming orders to maximize total stock utilization. The "unit-density" constraint implies that the value of an order is exactly equal to its size, making the objective a simple maximization of units sold. However, the decision is irrevocable: once an order is rejected, it cannot be reclaimed, and once accepted, it cannot be evicted to make room for a larger, potentially more beneficial order later.

While theoretical research has identified algorithms achieving a competitive ratio of 0.5, these methods often lack "explainability." They may reject an early order only to accept an identical one later, a behavior that is difficult to justify to customers and warehouse managers. This paper seeks a middle ground, deriving optimal randomized threshold policies that prioritize simplicity and consistency while maintaining rigorous performance guarantees.

Methodology: Randomized Threshold Policies

The authors focus on Randomized Threshold Policies. In this framework, the algorithm selects a random threshold ($\tau$) at the start of a period and adheres to it strictly: any order larger than $ au$ is accepted (subject to capacity), while smaller orders are rejected.

To determine the optimal probability distribution for this threshold, the researchers:

  1. Modeled the Cumulative Distribution Function (CDF): The search for an optimal distribution was treated as an infinite-dimensional optimization problem.
  2. Balanced Binding Scenarios: The policy must hedge against two worst-case outcomes: accepting small items early and exhausting capacity before a large item arrives, or waiting too long for a large item that never appears.
  3. Extended to Multi-Knapsack Settings: For scenarios involving multiple warehouses, the authors developed a "phantom routing" recipe. Items are routed to the warehouse where they would fit best according to a virtual process, after which the local threshold policy is applied.

Empirical Evaluation

The theoretical models were validated using real-world supply chain data from a major Latin American department store. The dataset included 974 Stock Keeping Units (SKUs) across 21 regional warehouses. To ensure the simulations remained challenging, the researchers used synthetic re-scaling of inventory levels, as the original data was "censored" (only reflecting fulfilled orders).

Key Results and Theoretical Bounds

The paper quantifies the "price of explainability." While general algorithms can reach a 0.5 ratio, the best threshold policy achieves approximately 0.43. This ~7% gap is often considered an acceptable trade-off for the operational benefits of a consistent, explainable policy. Furthermore, the authors provide the first proof that the multi-knapsack problem is fundamentally harder, establishing an impossibility result that no randomized algorithm can exceed a 0.4605 competitive ratio in that setting.

Summary of competitive ratios for various online resource allocation problems.

As shown in the table above, the derived algorithms for the single knapsack problem achieve competitive ratios of 0.4285 (relative to a fractional offline optimum) and 0.4324 (relative to an integral offline optimum). For multiple knapsacks, the "phantom routing" approach yields a 0.2142-competitive algorithm.

Discussion and Future Work

Simulations indicate that while simple "First-Come-First-Served" (FCFS) approaches may perform well on average, they are brittle in worst-case scenarios, sometimes achieving as little as 15% utilization. In contrast, the proposed threshold policies provide a much higher performance "floor," ensuring robustness against adversarial order sequences.

Future research directions include extending this logic to multiple consumptions (where orders require multiple resource types, such as labor and raw materials) and reusable products (where inventory, such as cloud server capacity or hotel rooms, becomes available again after a set duration).

Summary updated

BibTeX
@misc{ma2019competitive,
  author = {Will Ma and David Simchi-Levi and Jinglong Zhao},
  title = {{A Competitive Analysis of Online Knapsack Problems with Unit Density}},
  year = {2019},
  url = {https://openreview.net/forum?id=FBOAJcGeDQ},
}
Figure