Online Knapsack with Frequency Predictions
Authors: Sungjin Im
Ravi Kumar
Mahshid Montazer Qaem
Manish Purohit
Venue: NeurIPS 2021 Poster (2021)
Keywords: online knapsack
learning-augmented algorithms
semi-online algorithms

Abstract: There has been recent interest in using machine-learned predictions to improve the worst-case guarantees of online algorithms.  In this paper we continue this line of work by studying the online knapsack problem, but with very weak predictions: in the form of knowing an upper and lower bound for the number of items of each value.  We systematically derive online algorithms that attain the best possible competitive ratio for any fixed prediction; we also extend the results to more general settings such as generalized one-way trading and two-stage online knapsack. Our work shows that even seemingly weak predictions can be utilized effectively to provably improve the performance of online algorithms.

Online Knapsack with Frequency Predictions
Sungjin Im Electrical Engineering and Computer Science University of California, Merced sim3@ucmerced.ed.
Ravi Kumar
Google Research Mountain View, CA ravi wwwkkk3ammll...mmm com
Mahshid Montazer Qaem Electrical Engineering and Computer Science University of California, Merced
Manish Purohit
Google Research
Mountain View, CA
rmottazzerrqembbccerrrcc... edu
mpurohit@@oogle..oomm
Abstract
There has been recent interest in using machine-leamed predictions improve the worst-case guarantees of online algorithms. In this paper we continue this line work by studying the online knapsack problem, but with very weak predictions: in the form of knowing an upper and lower bound for the number of items of each value. We systematically derive online algorithms that attain the best possible competitive ratio for any fixed prediction; we also extend the results to more general settings such as generalized one-way trading and two-stage online knapsack. Our work shows that even seemingly weak predictions can be utilized effectively to provably improve the performance of online algorithms.
Introduction
An algorithm designer's ultimate goal is to develop algorithms that are reliable and work well in practice. High reliability has been the major focus of discrete algorithmic research that primarily seeks to give strong worst-case guarantees for all inputs. Unfortunately, such algorithms treat all input instances on equal footing-even pathological ones that rarely occur in practice-and do not necessarily exploit the latent structure that can be present in realistic instances. In contrast, machine learning has demonstrated amazing successes in many real-world applications, yet occasionally exhibits unacceptable failures on specific (worst-case) instances.
Leaming-augmentte algorithm design has recently emerged model achieve both reliability and worst-case guarantees, particularly in the online setting. In this model, an online algorithm is given certain predictions the input it will face in the future, and the algorithm then makes irrevocable decisions as the actual input is revealed one by one. Ideally, the algorithm should perform close to the optimum when the predictions are good, and yet possess worst-case guarantees even when the predictions are malicious. Recent work has shown that this is achievable for online problems such as
caching [7 26 29] ski-rental [4] 22] scheduling (6 [15 22 (28), load balancing [23], secretary problem metrical task systems set cover (7], flow/matching (24], bin packing [3, etc.
given as prediction specific value of key parameters of the online instance, e.g., the number of days to ski in the ski-rental problem the next request time of page in the caching problem. In this paper, take relaxed approach and assume that the prediction only gives a range of values for key parameters. This is natural way model weak predictions where the predictor has high uncertainty and only provide a reliable range in which the value must lie. Given such weak predictions, we seek to obtain beyond worst-case guarantees for all inputs respecting the prediction, by possibly exploiting the structure
Most prior work
augeeeted online algorithms assumes that
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

provided by these predictions. In fact, we seek algorithmss that give worst-case guarantees for all inputs while promising sharper bounds for instances that indeed respect the predictions. In this paper, we design such dearning-augmentie algorithms with weak predictions for the online knapsack problem, which a basic problem of practical importance
Knapsack Problem and the Prediction Model. In the classic online knapsack problem, we have knapsack of unit capacity" and n items that arrive online. Each item has profit pt 2 and size 0 S 8/ S 1. For convenience, we define the value of an item, V/ ;= pi/s;, to be the profit of the item per unit size. We assume that the value of each item lies in a range known a priori, i.e. we have Umin I 0 S Umax for some known constants Umin and Vmma algorithm must make an irrevocable choice of whether to accept or reject the item. The goal is to select subset of items of the highest total profit whose total size is at most the knapsack capacity.
ii When an item arrives, an online
Recall that online algorithm is said to have competitive ratio c, equivalently, be e-competitive if the algorithm's 's objective (profit) is at least e times the total profit obtained by the optimal solution for all inputs. Zhou, Chakrabarty, and Lukose [31] gave a 1/(1 In Ymax )-competitive algorithm (that we call ZCL) under the assumption that all items have infinitesimal sizes (or can be accepted fractionally) and further showed that no algorithm can obtain a better competitive ratio.
Vmin
Online knapsack is a fundamental problem in online algorithm design and finds applications in many real-world settings, e.g., in the context of online auctions [1 and charging electric vehicles [30]. For these practical applications however, the worst-case guarantees offered by standard competitive analysis are too pessimistic to be useful. Indeed, practical instances are not typically worst-case and further one often possesses some forcknowledge of the kind of items that expected to arrive in the future. In an online ad-auction, for instance, the advertiser can reliably predict a range such that the number of queries in a day for particular keyword lies within the range. In this work, we explore formal models to utilize such predictions to obtain provably good algorithms for online knapsack beyond what is possible via classical competitive analysis. In particular, we introduce and study the online knapsack problem with frequency predictions (KNAPSACK-FP),, described next.
Let Vdenote the set of all possible values that items may take, and Umin min(V) and Umaa mVx(V)) denote minimum and maximum values respectively. We may assume that the items have discrete values by rounding them to the closest power of (1 + e) for some > O, yielding [V| (log((mmax) (mmxx/mmm))) and making the competitive ratio only marginally worse. For any value u E V. let s, = E ble== S; denote the total size of items with value In the online knapsack with frequency predictions problem, for each value v V, the frequency predictions P {ly; uele provided to the algorithm are a lower bound E and an upper bound Uy such that eg I S. S. Uyg We say that the algorithm has a competitive ratio of a for KNAPSACK-FP with prediction P if the algorithm's 's profit is at least a times the optimum for all inputs respecting the given frequency prediction P. Our goal is to design an online algorithm with the best competitive ratio for this prediction model.
1.1 Our Results and Techniques
Our main result is a nearly optimal algorithm for KNAPSACK-FP.
Theorem 1. For KNAPSACK-FI -P,, given any frequency predictions, we can find an algorithm of competitive ratio a Smax
([VI + 1). max; 8ú, where a² is the best possible competitive ratio for the problem (with predictions).
Umin
Our algorithm, called SENTINEL, pre-computes a budger by for each value e and accepts items that maintain the invariant that the total size of accepted items of value at most v is at most B,- := Sang. by for all v E V. some sense, B, can be viewed as a sentinel to guard against accepting too many low-valued items. The key intuition underlying our algorithm that the knowledge regarding the arrival of future higher-valued items enables it to not over-allocate capacity to earlier lower-valued items. Our algorithm can also be implemented using only Olog VV) time per item. We note that the additive loss of Famax (1V++1) max; 8, in the competitive ratio in Theorem is
Eysin
'This without loss of generality by scaling all sizes. i "Such an assumption is necessary since otherwise we cannot hope for bounded competitive ratio in the adversarial model [27 31).

---

due to reduction to a continuous version of the problem (as discussed in Section 2 and this quantity approaches zero as max, s; - 0.
Interestingly our algorithm has a distinguishing feature from the ZCL [31 algorithm for the standard online knapsack. The ZCL algorithm constructs threshold function (t) (e Umax/ /maax//unin) //ninn ) (Emin/e) a priori and accepts an item online if its value is no smaller than (t) when é is the knapsack capacity that has been consumed. In contrast, we show that no such algorithm that maintains threshold function based on the capacity used can give the optimum algorithm (Section (.2).. We note that by combining our algorithm and ZCL (say by using a Y fraction of the capacity to run our algorithm and the other case guarantee of 1-y
fraction to run ZCL), we can simultaneously obtain a worst- Iolog Jmaxy as well as our improved guarantees for instances that respect the
prediction. Further, we can easily extend our result to show that our algorithm has a small loss in the competitive ratio when the predictions are slightly incorrect, for example, when have ( + S S, S u +)).
Extensions. We extend our model and results to two generalizations of the knapsack problem: the generalized one-way trading problem and the two-stage online knapsack problem. In generalized one-way trading [13] 30), each item of type is associated with certain concave function fa with fe(0) = 0. If an algorithm accepts s amount of items having type t, then it obtains profit f(()). The goal, as always, is to accept a set of items subject to the knapsack capacity maximize the total profit. This is a well-studied problem. motivated by converting given amount of money from one currency to another, in the presence of time-varying conversion rates.
The two-stage online knapsack a generalization that we introduce this paper. The key difference from the standard setting is that after sceing all the items, the online algorithm is given another chance in a second stage to accept any items that it rejected before. But, an item accepted in the second stage gives only À < 1 fraction of its original profit. The two-stage knapsack effectively interpolates between the online and offline problems: it becomes the standard online knapsack problem À = O, and the offline problem if X = 1. The two-stage setting has natural applications. For example, while clients typically prefer to know if their requests will be accepted instantly, some might choose to wait further for discount, albeit with the possibility of getting service if the service provider accepts other competing requests arriving later.
For both extensions we generalize our results and obtain the best competitive algorithms given frequency predictions (Sections 4 5p. This shows that our prediction model and analysis could find more applications, providing beyond-worst-cas. guarantees even with weak predictions.
Experiments. In Section 6 we conduct experiments on synthetic data sets, and show our algo- rithm augmented with frequency predictions considerably outperforms the classic worst-case ZCL algorithm.
1.2 Other Related Work
The knapsack problem has been extensively studied in the literature. For a comprehensive survey of the results the offline knapsack problem, [18). The offline version of the standard knapsack problem and most of its variants are well-known to be NP-hard.
The classic online knapsack problem falls into general class of problems called online packing problems and one can obtain an Q In(Umax (00ma//mmm))))) Ummnn) -compeiiceeeee algorithm via the online primal- dual technique [10 11 For a nice survey of online primal-dual technique and its applications for various packing and covering problems, see [12. Sun et al. [30] generalize the threshold algorithm in 31 by introducing control parameter that adjusts how fast the threshold grows. They empirically learn the best parameter within a certain range to retain some worst-case guarantees, but do not provide optimality. Kong et al. [2I] empirically show that reinforcement learning can find good threshold for the online knapsack.
Another line of work considers the stochastic online knapsack problem where items' profits and sizes are drawn from distribution (e.g.. see (2 25 20 and their follow-up works). In the random arrival model, the items are assumed to be chosen adversarially but arrive in uniformly random order. In this model, one can obtain constant competitive algorithms 19] and further if all items have an infinitesimal size, one can obtain nearly-optimal online algorithms
197. There are many other
3

---

variants studied and we only mention few here, e.g., removable online knapsack problems [16] and online knapsack with reservation costs [8]
2
Preliminaries
To ease the presentation, we will consider the following relaxed model, which differs from KNAPSACK-FI in aspects: first, we allow item to be accepted fractionally and second, we allow an item to have any value in [Umin, Umax] not from discrete set. The second relaxation is purely for ease of presentation and preserves the competitive ratio. The first relaxation results in a small additive loss in the competitive ratio since at most one item is accepted fractionally among those of the same value and all items assumed be small. We now formalize the relaxed model.
Continuous- Valued Online Knapsack with Frequency Predictions (C-KNAPSACK-FP) In the continuous version, we assume that there is a continuum of items, each having infinitesimal size and some value [Uming Umax]. In particular problem instance, for any value [Umin; Umax] let s(r)dv be the total size of items having value in the range [1; v + du] for some sufficiently small du. For each value [Umin: Umax]; we given a lower bound
and upper bound u(v) such that s(v) E [L(v), u(v]]. We assume that (v), ((v), u(u) are all continuous in v. Define S(v) = Sy= s(x)d I(v)= == Ja= ((x)dr, and U(v) == f -=mmin u(z)dr, which are differ- entiable at all E [umin: Umax by definition. As in the standard model, we have knapsack of unit capacity, and the goal to select subset of items of total size at most one that maximizes total value. The following relates the competitive ratio of the standard and the continuous-valuee versions.
[(v) ((())")(()))
Lemma 2. Given prediction P (fri ) NEV for KNAPSACK-FP. we can create prediction P' (L(v); (()))
(())) vElymin (mnne) for C- C-KNAPSACK-FF in polynomial time such that
1. An a-competitive algorithm for C-KNAPSACK-FI with prediction P' implies an (a Pmaa V max; 8.) comppttiieeee algorithm for KNAPSACK-FP with prediction P.
Vmin
2. If no algorithu has a competitive ratio better than a for C-KNAPSACK-FP with prediction Pt, then no algorithm has a competitive ratio better than a + max; s; for KNAPSACK-FP with prediction P.
Thus, if we find an algorithm with the optimum competitive ratio for C-KNAPSACK-FP, then we will have Theorem In the rest of the paper only consider the continuous version for convenience.
The SENTINEL algorithm
Let (l(v); u(v) ( (e( (moa: be a fixed set of predictions; this defines a family of knapsack instances, where each instance is a sequence of items, each with profit and size. Let denote the desired competitive ratio of our algorithm. We first derive an online algorithm that guarantees a competitive ratio of assuming one exists and then discuss how one can find the optimal such competitive ratio a". For any instance Z, let OZT(Z) denote the total value obtained by the optimal solution for instance I. To systematically derive our algorithm, it is instructive to consider the following family of instances. For any value v E [Umin: J. let M(r) denote an instance containing the maximum possible amount of items of value at most and the minimum possible amount of items
of value larger than v. Formally, M(U) is an instance such that s(x) = u(x) for all x S v and s(x) {(x) for all > Further, items in M(r) arrive in the following order: first ((x) items
of value x E [umins Umax] arrive in non non-decreasing order of value, followed by u(x) - f(x) items
of value x < arriving in non-decreasing order. Note that we consider M(r) only to derive algorithm.
Step
Let denote the largest value such that
Umax T f(x)dr aa OPT((((()
(1)
We use the functional notation (e.g., {(v)) for the continuous case and the subscript notation (e.g., f..) for the discrete case.

---

Intuitively v" denotes the largest value such that an algorithm is guaranteed to be a-competitive even it does not accept any items value less than v². Note that since assume that the functions {(-) and u(-) are continuous, such a value " is guaranteed to exist by the intermediate value theorem.
Step 2.
Consider an adversary that has constructed an instance of the form M(x) for some unknown value By instead constructing instance of the form MMx + dr), the adversary gain
additional profit of d OPT(MM())) In order to maintain competitive ratio of a, our algorithm must dx
accept enough additional items of value that it receives profit of at least d (PT((((x))
dr Motivated by this discussion, we define a function 7 [v", Umax] + [0, oc) to determine the additional amount items particular value that our algorithm accepts.
T(x)
a (M))) x de
Vor E [v", Umax]-
Step For any value x E min: ma we define budget function as follows.
[0, b(x) = (((x)+ + Txx),
< o² and B(v) Vx 2 U²
f b(x)dr
Vu
[Umins Umax]-
For any value the budget function ((v) defined above prescribes the maximum total amount of items of value most that must accepted. Formally, let A(v) denote the total amount of items of value at most that has been accepted by the online algorithm so far. Then, when an item of value arrives, the algorithm accepts the item if and only A(x) ((x) for all U.
Step 4. Finally, discuss how find the optimal competitive ratio. The functions T(-). 6(-), and B-) defined above are all (implicitly) functions of the desired competitive ratio a. To make this dependence explicit, let (-) denote the budget function for some fixed a. It can be easily verified that (Umax) is a continuous and monotonically increasing function of a. Assume U (? > 1 since otherwise
accept all items by setting b(z) = u(x) and we obtain competitive ratio of 1. We set a* E (0, 1) to be such that Ba (Umax) = 1. Again, by the intermediate value theorem, such a" is guaranteed to exist and further one compute it up arbitrary precision by binary search. For clarity, we include a formal description of the algorithm in the Supplementary Material.
3.1 Analysis
We begin by proving that our algorithm is indeed a" a--compttitive for any instance of C-KNAPSACK-FP that respects the given frequency predictions. Let ū be the largest value such that A(o) B(ū): if no such a value exists, 0 Emin- Let ALG and OPT denote the total value of items chosen by our online algorithm and the optimal solution respectively. In the following two claims, we first bound ALG and OPT respectively.
Claim 3. ALG
S Sam
b(x)))))))) dx + fiman x s(x) dr.
Proof. For convenience of notation, let ((v)
4 A(x))an denote the marginal amount of items of
de value u accepted by the algorithm. Since we have A(v) B(v) for all o, the algorithm accepts all items having value larger than and thus a(x) = (1;), Wo > 6. Also, by definition of ö, we have A (6) B()). Thus, we have the following.
a(z)dx + f x e-s(x)dr
ALG
a(x)dz=
z=vmin
integrating the first term by parts yields
Vmnax
ALG = 5 A(ö) Vnnn A(vmin)
A(x)dz +
x s(x)dr
Vmin
5

---

since A(o) B()) and A(x) I B(x), Vz, by definition of our algorithm
Ü. B(ū Umin ((emin)
B(x) +
z==
Pmin
x b(x)dx + [ a s.s())d
Claim 4. OPT S OPT(M(()) + J (s(x) (((x)) dr.
Proof. Let the optimum solution accept s(x) {(x) items of value for free without consuming the knapsack capacity for all x E (0, Unnax] The remaining items form an instance I' that is dominated by M()), Le., for any value I' is at most the amount of items with value x in M()). However, by definition, OPT(M(() the maximum profit that one obtain from M(ž) and the claim follows.
[Mmin mmax]. the amount of items having value in the instance
The following is from the definition of SENTINEL and is useful to relate the value of the optimal solution for any instance of the form M(r) to the budget function b(-) utilized by algorithm.
Claim 5. For any value v E [o", Umax] a" OPT(M(F)) femas (((x(())))){( dic + + Sammanu b(x) dr.
Proof. For all 2 vt, we have the following.
a' - OPT(M(()) = = (OPT(M(O'))
l" ==
d (PT(MM()))rr
substituting and
-f Je a.((x)d + S x T(r)dr.
Vmax
The claim follows by the definition of b(x) ((x)++(x) forall 2 v², and b(x) = 0, Vo v².
Finally, we are ready to show that the algorithm is indeed a competiiivee. Claims 3 and 5 together yield that:
Umax
ALG 2 a OPT((((()
+
x x (5(x) - {(x))dx
==
2a (OPT(O(TMM)
Pmaa
x (s(x) {(x))dr) 2 a OPT,
where the last inequality follows from Claim Thus, we have the following theorem. As discussed, the value of ax depends on the predictions.
Theorem 6. For any input instance that respects the frequency predictions (E(v), (Vmin Pmuax) the SENTINEL algorithm is o -=-copeetitive for C-KNAPSACK-FP.
3.1.1 Optimality of Competitive Ratio
In this section show that the competitive ratio obtained by SENTINEL is optimal. In other words, no algorithm, even randomized, can obtain a competitive ratio of better than a for C-KNAPSACK-FPP.
We will consider the family of instances ((x) amount of items of all values E [Umin; Umpax] arrive in non-decreasing order of value, followed by u(x) - {xx) amount of items of value x E [Umin: vr). which also arrive non-decreasing order of value. Consequently, until an algorithm sees items of value higher than in the second stage, it cannot distinguish between instances in
Recall that in the instance M(v), first
In other words, the instance M(U) is prefix of each of the instances in {M(x)) [efv:wa() Thus for any value v, the adversary can either strategically stop the instance M(v)) continue to release higher-valued items.
Lemma 7. For any given set {l(v). (((u))e((unn (e(lumnn of frequency predictions, let o² denote the competitive ratio of the SENTINEL algorithm. Then no deterministic algorithm can obtain a competi- tive ratio larger than a on all instances in the family {M(r) (0min Pmaas]

---

To see why randomization does not help, consider the deterministic algorithm that accepts each item by the expected amount that the optimum randomized algorithm accepts. This is well-defined as we are allowed to choose items fractionally. It is easy to see that the algorithm never exceeds the knapsack capacity and obtains as much value as the randomized algorithm. Thus, we have:
Theorem 8. For any given set { re((min (umin, of frequency predictions, there exists no randomized algorithm that attains a competitive ratio better than that of the SENTINEL algorithm.
Figure 1: Illustration of the optimal competitive ratio a' obtained by SENTINEL (in red) for predictions b, 1/100 and ut = (1 d) by for integers v [Umin 1, 1maxxx 100]. The competitive ratio is shown for E [0, 2]. For comparison, the competitive ratio result- ing from accepting & items of value e is shown in blue, i.e. (PT(M(O))/or(((((a))
C4-
412
37 5.%
125
188
Thus SENTINEL yields the optimal competitive ratio for any given set of predictions. It can be easily verified that the classical adversarial online knapsack problem is equivalent the special case with predictions {(v and u(v) oc for all v E [Vmin, Umax]] For this special case, we recover of ZCL. For more informative predictions, obtain much tighter
the competitive ratio I+In
Vaniin
competitive ratios. Indeed, ((2) u(v).. (, Ve [Umin Umax]. then a* 1 and SENTINEL obtains the optimum solution. Figure 1 illustrates the optimum competitive ratio for family of predictions.
3.2 Need for Sentinel
30 have all been threshold Prior algorithms for (variants of) the online knapsack problem 31 algorithms. i.e., the algorithm chooses a threshold y that is a function of the amount of residual capacity left in the knapsack and the algorithm accepts an item if and only if its value is higher than the threshold. On the other hand, the SENTINEL algorithm does not fit into this framework since the threshold for choosing an item depends on the values of items already chosen by the algorithm. In this section we show that there are predictions (l,; Uh hev such that no pure threshold-based algorithm can achieve the best competitive ratio. In fact, these predictions use only two values.
Let I denote a family of instances that respect the following predictions. There are two distinct values, V {1,2). The predicted bounds are given by 4 l2 and μ u2 2/3. As discussed in Section 3.1.I since randomization has no benefits, we only consider deterministic algorithms.
Claim 9. No deterministic online algorithm that maintains a non-decreasing threshold function (2), where is the knapsack capacity used, and accepts item and only if its value is higher than To (z) has competitive ratio better than 4/5 for the family of instances I.
On the other hand, with these predictions there is a simple algorithm that obtains competitive ratio of 6/7. 7. Let Agentinl denote the following algorithm: accept all items of value and accept at most 4/7 items of value 1. The proof of the following claim follows from simple case analysis.
Claim 10. For the instances in I, the algorithm Aventinet yields competitive ratio of 6/7.
4 Generalized One-Way Trading
In the classical one-way trading problem 13], trader needs to convert unit of money from one currency another. Faced with sequence of (unknown) exchange rates that are presented online, the goal is to maximize the amount of money obtained in the target currency. In this section we consider following generalized one-way trading problem, also considered by (30]: There are T different types of items and each type / is associated with concave value function ft. For convenience, we consider the setting where each item i has the same infinitesimal size X. Items arrive online and the total value carned by the algorithm is E. f(()), where I denotes the total size of items of type t
7

---

accepted by the algorithm. The goal is to design an algorithm that maximizes the total value such that the total size of accepted items is at most one. As the online knapsack problem, we assume that the algorithm has access to a lower bound & and an upper bound u4 on the total size of items of type I.
We now show that can reduce this problem to the online knapsack problem with predictions. For each type t, we create & f mandatory items with values fA), fe(2)) (f.)............. f:(4.........)))))-.....)..) f((e respectively. Additionally, we create /t/ Ä optional items with values fc f fe(w, - X) respectively. Note that many created items belonging to different types may have the same value. For each value v, let E(v) be the total size of mandatory items of value v and similarly let u(v) be the total size of all mandatory and optional items of value v. Let A be an online algorithm for the knapsack problem using predictions {E(v), u(v) J. For the generalized one-way trading problem, as items arrive online, we construct an instance of the knapsack problem online such that the kth item of type t has value (k-2 (e((k 1))). Finally, we accept an item (in the generalized one-way trading problem) iff the corresponding item is accepted by algorithm A in the knapsack instance.
(ue)
It is easy to verify that the optimum solution attains the same value, say OPT, in both the problem instances. Let a" denote the competitive ratio attained by A, and hence the total value obtained by A on the knapsack instance is at least a' OPT. On the other hand, suppose A accepts items of type i, then due to concavity of fe, it attains a value of at most Σ Sc(iA) - fe((i - 1)A) = (k())
Thus, the total value obtained by the online algorithm for the generalized one-way trading problem at least that obtained by A and hence it is also a -oomppttiiivee
5 Two-Stage Knapsack
Consider the following two-stage version of the typical fractional online knapsack problem. An instance here is parameterized by a discount factor 0 S X S 1. Once again, for convenience, we work in the continuous model, so there is continuum of items each having infinitesimal size") We assume that all items have value between [Umin: | When an item of value v arrives, an algorithm can either pick the item and receive value of v or it may choose to reject the item. After all items have arrived, the second stage starts and the algorithm can go back to previously rejected items and choose some of them, subject to the knapsack capacity. However, an item originally of value v is only worth Au in the second stage. Note that an item cannot be rejected once it gets accepted in either stage.
We note that this two-stage knapsack formulation naturally interpolates between the online and offline versions of the standard knapsack problem; when O. an algorithm cannot obtain any value from the second stage and hence reduces to the regular online knapsack problem, whereas with X = 1, an algorithm can commit to only accepting items the second stage after all items have been revealed and thus the problem reduces to the offline version.
To the best of our knowledge this problem has not been considered in the literature. Thus first show how to obtain the optimal competitive ratio for the problem in the absence of predictions. We then continue show how incorporate predictions on item frequencies for each value. We present the algorithm without predictions and defer the one with predictions to the Supplementary Material.
5.1 Algorithm for Two-Stage Knapsack without Frequency Predictions
As before let a* be the optimal competitive ratio for the problem, which will be decided later. In the absence of predictions, the optimal competitive ratio can be attained by threshold algorithm. In the first stage of the problem, the algorithm will maintain a threshold function depending on the knapsack capacity used and accept an item if and only if its value is higher than the current threshold. Finally, in the second stage, is easy to observe that any reasonable algorithm accepts the highest value items that can still be accommodated in the knapsack. We now show how to systematically derive such an algorithm.
For any value v. let 2()) be the fraction of the knapsack capacity for which the algorithm maintains the threshold at value v. To derive 2(0) we will consider the following family of adversarial instances: (i) items arrive in increasing order of value: (ii) there are enough items of each value to fill the entire knapsack; and (iii) the adversary can stop releasing items at any point in time.
" As in Lemma D when items have sufficiently small sizes, this assumption only leads to a small additive loss in the competitive ratio.
8

---

1.0
0.5
640
0.90
0.5
0.00
compaiiive
30.15
0.00
0.0
0.00
0.25
0.75
1.00
1.25
2.00
actual competitive ratio
ZCL's actual competitive ratio
Our theoretical competitive ratio
ZCL's theoretical competitive ratio
Figure 2: Illustration the empirical and theoretical competitive ratios our algorithm SENTINEL and ZCL. In the left, Umin 1, Umax 100, and 5 E [0, 2]; and in the right, Unin E 100] Pmax
Umin 99 and In both uh [(1 + 6) All items have size 1/10000.
We construct z(v) that is continuous at all E (Umins Mmax follows. First we set, 2(Umin) = e'-A This is because if the adversary only gives items of value Vmin and they enough to fill up the knapsack, then by accepting z(Vuin) of them in the first stage and more to the full capacity in the second stage we obtain profit (=(Umin) + A(1 - z(Umin) Mmiin a Umin
1-X
Now consider any value >> Umin If the adversary stops the instance at value the profit obtained by algorithm is:
ALG(u)= Umin a (Umin)
x. =xx)dx + Xu =(Umin)
[ =(x)dx)
Here, the first two terms denote the value earned by the algorithm in the first stage while the last term denotes the profit gained in the second stage. In particular, (1 - =(Umin) - Jz=e =(x)dr) is the amount of capacity left in the knapsack after the first stage and the algorithm will fill with the best items-ot value u u-and receive value of Au per each unit.
To maintain competitive ratio of ax, we need to maintain for all v E (Vmins Umax) M(v)) = a"v. By solving this, together with ((imin) + J.e (eean Umax] 2(x)dr we can find and 2(1). Then, set the threshold function & (t) as follows:
T (t) = Umin
if <
a'-2
1-X
Z
otherwise
<x;)dx;; this integral includes 2(Umin). And if we see an item value in the first phase when the knapsack is f-full, we accept v 2 (t). In other words, we keep the threshold at Umin until the knapsack gets ='uA-full; afterwards, keep the threshold at u for z(v) units. In the second phase, we accept the highest valued remaining items to the full capacity. Further details in the Supplementary Material.
where
6 Experiments
We design experiments to show that our algorithm, SENTINEL, achieves considerably larger profit than ZCL [31 even when we are given loose frequency bounds as predictions. Specifically, we consider the following setup. The knapsack capacity is set to 1. Each item is assumed to have a size 10-4 and an integer value the range of [Umin = 1, Umax = 100). For each value e, its frequency lower bound f, is sampled from [50, 150] independently and uniformly at random; therefore, in expectation, least 10a items arrive an instance. We use a control parameter 8 to derive the upper bounds from f, and set u, [(1 + 8)6, For each instance, s, is sampled from [L., up]

---

independently and uniformly at random and items arrive in random order. The results are the geometric average over 10 instances.
In the first experiment we observe how the competitive ratios of SENTINEL and ZCL. change as we vary ó from 0 to 2. Intuitively, smaller å value means better predictions. We confirm that SENTINEL outperforms ZCL for all values of in terms of empirical as well as theoretical competitive ratios. The actual competitive ratios degrade ô grows, but SENTINEL continues dominate ZCL.
In the second experiment, we consider different values of Umin in the range of {l...., 100), fixing the difference Umax Vmni 99 and 2. The goal of this experiment is ratios change as the ratio Vmaxx/ Umin changes. Note that the ratio decreases from 100 to nearly 2. Recall that ZCL has competitive ratio 1/(1 In(Vmax/ In((max//uun))) /min)) Again, SENTINEL consistently outperforms ZCL,, although the difference becomes smaller as Umax/ Umin decreases.
how the competitive
7 Conclusions
In this paper we studied the online knapsack problem and its extensions when given the range of the number of items of each value predictions. We showed that even such weak predictions can be exploited to give provably better competitive ratios. It would be interesting to revisit other problems with such weak predictions. Another fruitful direction is explore other types of weak predictions.
References
[1] Albers, A. Khan, and L. Ladewig. Improved online algorithms for knapsack and GAP the random order model. Algorithnica, pages 1-36, 2021.
[2] K. Anand, R. Ge, and D. Panigrahi. Customizing ML predictions for online algorithms. In ICML, pages 2020.
[3] S. Angelopoulos, S. Kamali, and K. Shadkami. Online bin packing with predictions, 2021. arXiv:2102.03311.
[4] A. Antoniadis, C. Coester, M. Elias, A. Polak, and B. Simon. Online metric algorithms with untrusted predictions. In ICML, pages 345-355, 2020.
[5] A. Antoniadis, T. Gouleakis, P. Kleer, and P. Kolev. Secretary and online matching problems with machine learned advice. In NeurlPS, 2020.
[6] É. Bamas, A. Maggiori, L. Rohwedder, and O. Svensson. Learning augmented energy mini- mization via speed scaling. In NeurlPS, 2020.
[7] É. Bamas, A. Maggiori, and O. Svensson. The primal-dual method for learning augmented algorithms. NeurlPS, 2020.
[8] H. Böckenhauer, E. Burjons, Hromkovic, H. Lotze, and Rossmanith. Online simple knapsack with reservation costs. STACS, 2021.
[9] C. Borgs, J. Chayes. N. Immorlica, K. Jain, O. Etesami, and M. Mahdian. Dynamics of bid optimization in online advertisement auctions. In WWW, pages 531-540, 2007.
[10] N. Buchbinder and Naor. Online primal-dual algorithms for covering and packing problems. In ESA, pages 689-701. Springer. 2005.
[11] N. Buchbinder and Naor. Improved bounds for online routing and packing via a primal-dual approach. In FOCS, pages 293-304, 2006.
[12] N. Buchbinder and Naor. The design of competitive online algorithms via primal-dual approach. Found. Trends Theor. Comput. Sci., 3(2-3):93-263, 2009.
[13] R. EI- Yaniv, A. Fiat, M. Karp, and Turpin. Optimal search and one-way trading online algorithms. Algorithmica, 3001):011-13, 2001.
10

---

[14] S. Gollapudi and D. Panigrahi. Online algorithms for rent-or-buy buy with expert advice. In ICML, pages 2319-2327, 2019.
[15] Im, R. Kumar, M. Montazer Qaem, and M. Purohit. Non-clairvoyant scheduling with predictions, In SPAA, pages 285-294, 2021.
[16] K. Iwama and S. Taketomi. Removable online knapsack problems. In ICALP, pages 293-305, 2002.
[17] Z.. Jiang, D. Panigrahi, and K. Sun. Online algorithms for weighted paging with predictions. ICALP, pages 69:1-69:18, 2020.
[18] H. Kellerer, U. Pferschy, and Pisinger. Knapsack Problems. Springer, Berlin, Germany, 2004.
[19] T. Kesselheim, K. Radke, A. Tonnis, and B. Vocking, Primal beats dual on online packing LPs the random-order model. SIAM Journal on Computing, 1735)11939-196,, 2018.
[20] A. J. Kleywegt and J. D. Papastavrou. The dynamic and stochastic knapsack problem. Opera- fions Research, 46(1):17-35, 1998.
[21] W. Kong, C. Liaw, A. Mehta, and D. Sivakumar, A dog learns old tricks: RL finds classic optimization algorithms. In ICLR, 2018.
[22] R. Kumar, M. Purohit, and Z. Svitkina. Improving online algorithms using ML predictions, In NeurIPS, pages 9661-96700 2018.
[23] Lattanzi, T. Lavastida, B. Moseley, and Vassilvitskii. Online scheduling via learned weights. In SODA, pages 1859-1877, 2020.
[24] T. Lavastida, B. Moseley, R. Ravi, and C. Xu. Learnable and instance-robust predictions for online matching, flows and load balancing. In ESA, pages 59:1-59:17, 2021.
[25] G. S. Lueker. Average-case analysis of off-line and on-line knapsack problems. Journal of Algorithms, 29(2):277-305, 1998.
[26] Lykouris and S. Vassilvtiskii. Competitive caching with machine learned advice. In ICML. pages 2296-3305,,0 2018.
[27] A. Saarchetti-Spaccammee and C. Vercellis. Stochastic on-line knapsack problems. Mathematical Programming, 68(1):33-004 1995.
[28] M. Mitzemmacher. Scheduling with predictions and the price of misprediction. In ITCS, pages 14:1-14:18, 2020.
[29] D. Rohatgi. Near-optimal bounds for online caching with machine learned advice. In SODA, pages 1834-1845, 2020.
[30] B. Sun, A. Zeynali. T. Li, M. H. Hajiesmaili, A. Wierman, and D. H. K. Tsang, Competitive algorithms for the online multiple knapsack problem with application electric vehicle charging. Proc. ACM Meas. Anal. Comput. Syst., 4(3):51:1-51:33 2020.
[31] Y. Zhou, D. Chakrabarty, and R. M. Lukose. Budget constrained bidding in keyword auctions and online knapsack problems. In WINE, pages 566-576, 2008


Reviews:
[{"review_id": "plAAP0hU4tn", "reviewer": "Reviewer_K1Av", "summary": "The paper considers the following variation of the online knapsack problem: Items of profit $p_i$ and size $s_i$ arrive online and upon arrival of an item it has to irrevocably be either packed to our knapsack (of unit capacity) or rejected. Let $v_i$ be the value of item $i$, and assume that $\\forall I$ there holds $v_{min}\\le v_i \\le v_{max}$. The best known algorithm for this problem (called ZCL) obtains a competitive ratio of $1/(1+\\ln\\frac{v_{min}}{v_{max}}$. Let further $V$ be the set of all possible values that the arriving items may take, and $s_v$ be the total size of items of value $v$. In the problem studied in the paper it is assumed that the algorithm knows an upper and lower bound on $s_v$ for all possible $v$, and gives an $\\alpha - \\frac{v_{max}}{v_{min}}(|V|-1)\\cdot\\max s_i$-competitive algorithm for this variation, where $\\alpha$ is the best possible competitive ratio that can be obtained for this problem variation.\n\nTwo natural extensions of the problem are then discussed: (i) to generalised one-way trading, and (ii) to two-stage online knapsack which is introduced in the current paper, before concluding with experimental results.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Although the algorithm itself is interesting and to the best of my knowledge also novel, I feel that the paper has a number of significant drawbacks:\n\n1. The authors try to sell the problem as a problem within the very active area of learning augmented algorithms which in my opinion is misleading. According to my understanding the crux of this area is that although the quality/accuracy of the predictions is not known these can still be used to obtain improved results in case the predictions are accurate (consistency). The current paper assumes that the \"predictions\" on the range of item values are correct. In turn there is no robustness result showed or discussed and I am quite confident that the algorithm will perform arbitrarily bad in case the real instance does not satisfy this \"prediction\". I would therefore mostly consider the paper as an interesting algorithm for a restricted case of the online knapsack problem, which may be of interest on its own but cannot be classified as a learning augmented algorithm (and in turn I am not sure if NeuRIPS is the correct venue for such a paper).\n\n2. It is a bit unusual to express the competitive ratio as a function of the best possible competitive ratio and I think this would deserve some more discussion.\n\n3. The extensions are in my opinion straightforward and don't provide additional value to the paper.\n\n4. The experiments are also not too interesting and show that naturally an algorithm with more information available will obtain a better solution.\n\nThat being said, the paper is generally well written and the intuition behind the design of the algorithm is conveyed reasonably well.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I have no concerns about negative social impact of this paper.", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical concerns for this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "bQ2VMerPqBX", "reviewer": "Reviewer_xbrn", "summary": "This paper designs an online algorithm for the online knapsack problem (OKP) with frequency prediction and shows its competitive ratio (CR) under assumptions that (i) the value density of each item, v, is bounded within [v_min, v_max], and (ii) the demand (frequency) of the items with value density v, s_v, is bounded within [l_v, u_v], for all v. \n\nIt also shows that the proposed algorithm is optimal (achieving the maximum CR) and can be extended to other variants of OKP (e.g., generalized one-way trading). \n\nIn the literature, the ZCL algorithm (a threshold algorithm) in Ref [30] has been shown to achieve the optimal CR for OKP under the assumption (i). The main contribution of this paper is to show that by taking additional information in assumption (ii), it can also design a nearly optimal competitive algorithm, and it presents an interesting idea of how to design the algorithm, which has essential modifications from that of designing the ZCL algorithm.\n\nFinally, the results have been extended to two additional variants with competitive analysis. \n", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this paper studies the online knapsack problem from a novel perspective of incorporating predictions into the algorithm design. But, the theoretical approach is different from the emerging direction of online algorithms with ML advice since it does not take into account quality of prediction and hence robustness/consistency analysis (more details below). The quality and clarity of results are satisfactory and results by themselves sound solid. The significance of the results, however, is limited since it just considers a very particular type of prediction into the model, which may not be easily applicable to other related problems, and even the current model is not complete since it does not take into account error of the prediction.\n\nMajor comments:\n\n-- This paper is of interest to the field of online algorithms with worst-case guarantees but has limited contributions to learning-augmented algorithms. It is in fact only focused on the worst-case algorithm design under perfect predictions on demand information $[l_v, u_v]$ (i.e., given accurate values of $l_v$ and $u_v$). The derived results can be considered as the consistency analysis in the works cited in the second paragraph of the introduction.  However, it lacks robustness analysis of the algorithm under malicious predictions (i.e., inaccurate $l_v$ and $u_v$ values), and the trade-off between the consistency and robustness. Thus, the current work is incomplete as a learning-augmented algorithm. The author mentions that there is a chance to combine the proposed algorithm and the ZCL algorithm to ensure robustness. However, the details of this important aspect are not elaborated and unjustified in the paper. \n\n\n-- about the lower bound result of the CR (Theorem 1). The CR of the proposed algorithm can be solved numerically, following Steps 1-4 in Section 3. But it lacks an essential understanding of how this CR depends on the given parameters. For example, the CR of the ZCL algorithm is $\\Omega(1/\\ln(v_{\\max}/v_{\\min}))$. It is important to know whether the proposed algorithm can improve this lower bound after taking additional information in assumption (ii). Thus, it is hard to evaluate the significance of the proposed algorithm.\n\n-- about the online algorithm in Steps 1-4. The algorithm is constructed by designing a budget that can meet the increment of OPT under a special instance. The idea is interesting. However, it seems some boundary conditions are not properly set in the current version of the algorithm. The core question is what the value of the initial budget $B(v_{\\min})$ is. If I understand correctly, $B(v_{\\min}) = 0$ in the proposed algorithm. Then if we consider an instance with $l_v = 0, u_v = \\infty$, and the value density of all items is $v_{\\min}$, the proposed algorithm seems to accept no items while $OPT = v_min$ (leading to an unbounded CR). In fact, this issue also arises in equation (1). When $l(x) = 0$ for all $x$, the LHS = 0 and the RHS is non-zero. It seems there may not exist $v^*$ to make equation (1) hold. \n\nMinor comments:\n\n-- in section 3, it would be clearer if an explicit online algorithm is presented first, followed by how to design in Steps 1-4.\n\n-- in experiments, it is not fair to compare the worst-case ZCL algorithm with the prediction-based algorithm proposed in this paper, rather, it might be good to compare with a simple prediction-based variant of ZCL\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes. ", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Xy4aXBjgSzp", "reviewer": "Reviewer_upZi", "summary": "This paper studies the online knapsack problem when the algorithm is endowed with some predictions about the input. In the online knapsack problem, a sequence items arrives online. Each item $i$ has a profit $p_i$ and a size $s_i$, and we refer to the ratio $v_i = p_i/s_i$ as the item’s value, which is assumed to be contained in an interval $[v_{min}, v_{max}]$. When each item arrives, the algorithm must make an irrevocable choice of whether to accept or reject the item. The goal is to maximize the profit of the items chosen while respecting the knapsack’s capacity constraint. The predictions have the following form: let’s say that s(v) is the total size of the items with value v. The algorithm receives as input an interval $[\\ell_v, u_v]$ with the guarantee that with probability 1, s(v) lies in the interval.\n\nThe paper provides an algorithm with the following guarantee. Let’s say that V is the set of all possible values that the items may take, which we assume to be finite (an infinite set could be discretized with little loss). Let $P=\\\\{\\ell_v, u_v \\mid v \\in V\\\\}$ be the set of frequency predictions provided to the algorithm. We say that the algorithm has a competitive ratio of $\\alpha$ for this knapsack problem with predictions $P$ if the algorithm’s profit is at least $\\alpha$ times the optimum for all inputs respecting the given frequency prediction $P$. Letting $\\alpha^*$ be the optimal competitive ratio of this type, the paper provides an algorithm with competitive ratio $\\alpha^* - \\frac{v_{max}}{v_{min}} \\cdot (|V| + 1) \\cdot \\max_i s_i$. They also provide extensions to other related problems, including the “generalized one-way trading problem” and the “two-stage online knapsack problem.”\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this paper seems to have some solid contributions with an interesting main result. The competitive ratio seems to be pretty good—it’s nice that the loss is only additive, not multiplicative. Also, I like the idea of relaxing the type of predictions that the algorithm gets.\n\nRegarding the model, it would be helpful if the authors could say a bit more about where the predictions might come from. If the predictions are obtained via machine learning, then it’s likely that the predictions would only hold with some high probability. I wonder if the paper’s techniques might be amenable to further relaxing the predictions in this way.\n\nI also think that the writing could be clarified. Perhaps since I’m not already familiar with approaches to the standard online knapsack problem, I found the transition to the continuous-valued online knapsack problem a bit hard to understand. In my detailed comments, I have some specific suggestions. It seems like some of the concepts in the algorithm could be visualized, so some pictures would really help. There were also some concepts that I couldn’t find the definitions of (like $B_{\\alpha}(v)$ and $\\alpha^*$, though the latter I picked up from context), so it seems like the paper could use a revamp for clarity’s sake.\n\nDetailed comments:\n-\tLine 22: “possesses” -> “possess”\n-\tI found the definition of $s_v$ to be a bit confusing. In line 39, the integer $i$ indexing the value $v_i$ corresponds to the item $i$. But in line 59, the integer $i$ indexing the value $v_i$ no longer seems to correspond to the item $i$--it seems to be indexing the set $V$. Which indexing are we using in the definition of $s_v$ in line 62? I think it’s the first indexing, but I’m not sure.\n-\tTheorem 1: At first, I was confused that SENTINEL’s competitive ratio didn’t seem to explicitly depend on the lengths of the intervals $u_v - \\ell_v$. Then I realized that $\\alpha$ must depend implicitly on these lengths. It would be helpful to mention this. Perhaps it would help to write $\\alpha(P)$ instead of $\\alpha$ to make it clear that $\\alpha$ depends on $P$ (from my understanding).\n-\tLine 81: Can you give an example where the maximum size approaches 0?\n-\tLine 175: Could you clarify why Opt(M(x)) is differentiable?\n-\tLine 176: “at” -> “at least”\n-\tLine 185: I couldn’t find the definition of $B_{\\alpha}(v)$.\n-\tLine 187: I couldn’t find the definition of $\\alpha^*$, but maybe it’s the best possible competitive ratio for all inputs respecting the given frequency prediction $P$.\n-\tLine 197: Could you clarify why A(x) is differentiable?\n-\tLines 205-207: Could you spell out a bit more why this is the case?\n-\tLine 323: It looks in Section 5.1, like $\\alpha^*$ is first mathematically defined in line 323, but the definition is a bit implicit, so it would be good to be more explicit.\n-\tLine 341: If $\\ell_v$ equals 100 in expectation, shouldn’t the expected number of items that arrive be $10^6$, since $10^6 \\cdot 10^{-4} = 100$?\n-\tSection 6: What happens for larger sizes?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the authors could be a bit more explicit about limitations, perhaps in the future research section.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new algorithm for the online knapsack problem. The algorithm utilizes the knowledge of upper and lower bounds for the number of items of each value, and its competitive ratio depends on the gap between the bounds. 

The reviewers found the problem formulation and the algorithm to be interesting and novel. However, there were concerns whether the proposed method can be viewed as a “learning-augmented algorithm”, given that the paper does not explicitly address the case where the predictions are inaccurate. Furthermore, some reviewers commented that the experiments demonstrating the applicability of the proposed algorithm were quite limited, and did not illustrate where the appropriate predictions would come from.

Decision: Accept (Poster)