Introduction
The classic Knapsack Problem is a cornerstone of combinatorial optimization. In its online variant, items arrive sequentially, and a decision to accept or reject an item must be made immediately and irrevocably. The "Unit Profit" version, where every item has a value of 1, simplifies the objective to maximizing the total number of items packed. Despite this simplification, the online problem is notoriously difficult; without prior knowledge of the item sequence, any deterministic algorithm faces an unbounded competitive ratio. This paper explores how a single, potentially inaccurate prediction—the average size of items in an optimal offline solution—can fundamentally change the tractability of the problem.
Problem Formulation
In the Online Unit Profit Knapsack Problem, an algorithm is presented with items $s_1, s_2, \dots, s_n$ one by one. Each item has a size, and the total capacity of the knapsack is normalized to 1. The goal is to maximize the number of items accepted such that their total size does not exceed the capacity.
The difficulty lies in the "all-or-nothing" nature of the decisions. Accepting a large item early might preclude accepting many smaller items later, while rejecting items in anticipation of smaller ones that never arrive leads to under-utilization. In traditional competitive analysis, the performance is compared against an optimal offline adversary (OPT) that knows the entire sequence in advance.
The Adaptive Threshold (AT) Framework
The authors propose the Adaptive Threshold (AT) algorithm, which utilizes a machine-learned prediction $\hat{a}$ representing the average size of items in the optimal offline set.
Mechanism
Instead of a greedy approach, AT employs a threshold function $T(i)$. This function determines the maximum size an item can have to be accepted, given that $i$ items have already been packed. As the knapsack fills (i.e., as $i$ increases), the threshold $T(i)$ typically becomes more restrictive. This prevents the algorithm from exhausting its capacity on mediocre items early in the sequence.
Variants: AT and ATup
Two versions of the algorithm are analyzed:
- AT (Trusted): This version is optimized for scenarios where the prediction $\hat{a}$ is assumed to be highly accurate. It aims for "consistency"—maximizing performance when the error is zero.
- ATup (Untrusted Predictions): This version incorporates robustness. It acknowledges that the prediction $\hat{a}$ may be erroneous and adjusts the threshold logic to ensure a baseline level of performance even if the prediction is significantly far from the true average size $a$.
Key Theoretical Results
The paper's contributions are primarily theoretical, establishing bounds on what is achievable with average-size advice.
The $(e-1)/e$ Limit
A central finding is that with perfect advice ($r = a/\hat{a} = 1$), the AT algorithm achieves a competitive ratio of $(e-1)/e \approx 0.6321$. The authors prove that this is the fundamental limit for any deterministic algorithm using only the average size as advice. This constant is a recurring theme in online algorithms, representing the boundary of optimal decision-making under uncertainty.
Performance under Prediction Error
The authors analyze how performance degrades as the prediction error $r$ increases or decreases. For the robust ATup algorithm, the competitive ratio follows a predictable curve:
- When the prediction is an overestimate ($r \le 1$), the ratio is approximately $r/2$.
- When the prediction is an underestimate ($r \ge 1$), the ratio is approximately $1/(2r)$.
These results demonstrate a "smooth" degradation, avoiding the catastrophic failure (unbounded ratio) of standard online algorithms.
Optimality and Trade-offs
The research establishes matching lower bounds, proving that the proposed algorithms are near-optimal for the information provided. A key insight is the Pareto frontier between consistency and robustness: an algorithm cannot be perfectly consistent (optimal with perfect advice) without sacrificing robustness (performance with bad advice).
Discussion and Limitations
While the use of a single scalar prediction ($\hat{a}$) is powerful, it has limitations. The current work is restricted to deterministic algorithms and the unit profit case. In general knapsack problems, where items have varying values, the value-to-size ratio becomes the critical metric, significantly increasing the complexity of the thresholding strategy.
Furthermore, the paper treats the prediction as an exogenous input. In real-world applications, generating an accurate prediction of the average size in a non-stationary or adversarial environment remains a significant challenge for machine learning practitioners.
Conclusion
This work advances the field of learning-augmented algorithms by showing that even minimal advice—a single average—can bridge the gap between impossibility and constant-factor competitiveness in online knapsack problems. The Adaptive Threshold framework provides a robust template for balancing the benefits of machine-learned insights with the necessity of worst-case guarantees.
Summary updated