Online Fractional Knapsack With Predictions

Thank you for your review and suggestions. We will take them into account while revising the paper. Below we answer your questions in detail:

• (motivation for fractional knapsack problem)
  While it is true that online fractional knapsack (OFKP) doesn't address all online knapsack problems, there are numerous problems that can be effectively modeled by OFKP. This includes, for example, dynamic bandwidth allocation in wireless or communication networks [3, 4], online electric vehicle charging in smart grids [5], and online trading problems in financial markets [5]. For bandwidth allocation problems, multiple users share the same bandwidth with fixed capacity. Upon the arrival of each user, it requests for at most $w_i$ amount of bandwidth and each unit of bandwidth has a value $v_i$. The system operator determines how much bandwidth is allocated to the user with the objective of maximizing the total profit of the allocated bandwidth. OFKP exactly models this problem and the integral version of the online knapsack cannot provide a meaningful solution, especially when $w_i$ is comparable to the bandwidth capacity.
  We do agree that it would be interesting to extend our approach to integral knapsack problems – often results for the fractional case can be extended to the integral case if we assume that the item sizes are small enough. However, detailed derivation of the results needs further analysis which is beyond the scope of current work.

• (random order model vs adversarial model)
  In our work, we focus on the most general adversarial model of input. As you point out, many prior works assume additional structure on the input to obtain better results (e.g., random order model or stochastic input model). However, the resulting algorithms and performance bounds for the problem with these assumptions are quite different from the adversarial model. Since the adversarial model does not assume any structure on the input, it is strictly more general than e.g. the random order model, which is a strength of our work. By simultaneously considering adversarial inputs and (possibly untrusted or imperfect) predictions about the input, we seek to obtain the “best of both worlds” between the fully adversarial model and e.g. stochastic inputs.

• (About Prediction model)
  The key novelty of our algorithm is to carefully design the decisions given an exact prediction of the cutoff value to give a better than 2 competitive ratio, which matches our lower bound results. Further, we show that this idea can be extended when the prediction of cutoff value is not exact (e.g., interval prediction or probabilistic prediction). This approximate setting is much more interesting in real world settings and requires a significantly more careful analysis. Prior work has considered much stronger prediction models – e.g. frequency predictions for all values [1]. Note that our prediction model is much weaker – as an approximation to the cutoff threshold can be derived from a set of frequency predictions but not vice-versa.

• (Related work of online knapsack with predictions)
  two points: (i) two existing works [1] [2] are for integral knapsack with small weights; their model cannot solve our problems since in OFKP, the weight of each item can be close to knapsack capacity; (ii) our prediction model is simple, asking for just a single value; the prediction model used in the other works is to predict the histogram of the item values, which is much more complicated.[1] provides bounds on the total weights for every unit value in advance in predictions. Such predictions are very stronger than our setting, since they give advanced knowledge of the total weight of items with unit values above the critical value $\hat{v}$, allowing us to adjust the amount we wish to accept at the critical value..

[1] Im et al., Online knapsack with frequency predictions. NeurIPS 2021.

[2] Balseiro et al., Single-leg revenue management with advice. EC 2023.

[3] John Noga, et al.. An online partially fractional knapsack problem. 8th International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'05), 2005.

[4] Hyun-Woo Kim, et al. Dynamic bandwidth provisioning using ARIMA-based traffic forecasting for Mobile WiMAX. Computer Communications 34.1, 2011.

[5] B. Sun, A. Zeynali, T. Li, M. Hajiesmaili, A. Wierman, and D.H.K. Tsang. Competitive algorithms for the online multiple knapsack problem with application to electric vehicle charging. Proc. ACM Meas. Anal. Comput. Syst., 2021.

Thank you for your review and suggestions, we will incorporate them into our revisions. Please find our response below:

• (algorithmic novelty)
  The key novelty of our algorithm is to carefully design the decisions given an exact prediction of $\hat{v}$ to achieve a competitive ratio better than 2 which matches the lower bound results. We further show that this idea can be extended when the prediction is not exact (e.g., interval prediction or probabilistic prediction), which is more natural in real-world applications. Although the extensions are based on existing algorithmic frameworks in the literature, we show that our new approach can be indeed integrated into the existing framework while attaining good performance guarantees. Moreover, our results are not required to have a bounded value-weight ratio assumption, unlike almost all prior work on these problems.
• (Comparison with [1])
  Thank you for the valuable suggestion. We believe that the frequency prediction model studied in [1] is stronger than ours, in the sense that it provides bounds on the total weights for every unit value in advance. Such predictions could yield a better competitive ratio in our setting, since they give advanced knowledge of the total weight of items with unit values above the critical value $\hat{v}$, allowing us to adjust the amount we wish to accept at the critical value. By employing their prediction system, we can compute $\hat{v}$, the largest value for which the cumulative weight, including itself and all greater values, surpasses the knapsack size. In our setting, we opted to constrain our approach and consider a comparatively weaker prediction model which directly predicts $\hat{v}$. It is possible that such simpler prediction models would be easier to learn and deploy in practice.
• (probabilistic predictions model)
  Lemma 4.3 establishes the relationship between consistency and robustness of our proposed PIPA algorithm (Algorithm 5). While we have not explicitly explored lower bounds for this prediction model, we can claim that PIPA is on the Pareto frontier at two points. When γ = 1 and ƍ = 0, we match the optimal consistency bound when predictions are always correct, since we are exactly c-competitive, where c is the optimal competitive ratio of the inner algorithm with perfect predictions. On the other hand, for any value of ƍ, when γ = 0, we recover the optimal robustness bound, which is exactly the $\ln(U/L) + 1$ bound shown by [2]. It would be very interesting to explore whether our algorithm achieves the optimal consistency-robustness tradeoff within this probabilistic interval predictions framework for arbitrary values of ƍ and γ. Thank you for the suggestion!
• (experimental setup)
  We will further clarify our experiment setup in the appropriate sections. For Prediction Model 2, we initially generate an instance of the problem and solve it offline. We obtain the critical value $\hat{v}$ from the offline solution. We then uniformly randomly generate an interval containing the critical value, with size averaging x% of the entire unit value range. For instance, if x = 10, the size of the generated interval will be 10% of the unit value range $[L, U]$. For Prediction Model 3, we created an instance as previously and use a coin toss with success probability $p$ to determine whether to provide a generated interval as previously, or a uniformly random interval that does not contain the critical value. In the general case, the specific location of the critical value within the interval does not seem to have a large impact, as the inner algorithm for the interval can solve the problem independently. However, there is significance in how many high-valued items fall outside the interval. Algorithm 4 is designed to mitigate this impact by attempting to ensure that a consistent fractional amount is taken from every item (1/(competitive ratio)), thereby minimizing potential disruptions from an incorrect prediction which underestimates the unit values in the sequence.
• (experiments on real data)
  We appreciate the suggestion regarding experiments on real data or with less synthetic predictions derived from the data. While we acknowledge the importance of real-world experiments, most related work in this field has primarily presented numerical results without explicit datasets. Additionally, the utilization of real data often introduces its own set of challenges, including subjectivity in building predictions. We recognize the value of incorporating real-world data in future investigations, and we will look to do so in subsequent iterations of our work.

[1] S. Im et al. Online knapsack with frequency predictions. In Advances in Neural Information Processing Systems (NeurIPS), 2021.

[2] B. Sun et al. Competitive algorithms for the online multiple knapsack problem with application to electric vehicle charging. Proc. ACM Meas. Anal. Comput. Syst., 2021.

Thank you for the detailed review and for your suggestions. We will take them into account while revising the paper. Please find our response below:

• (Motivation for studying online fractional knapsack problem)
  While it is true that online fractional knapsack (OFKP) doesn't address all online knapsack problems, there are numerous problems that can be effectively modeled by OFKP. This includes, for example, dynamic bandwidth allocation in wireless or communication networks [1, 2], online electric vehicle charging in smart grids [4], and online trading problems in financial markets [4]. For bandwidth allocation problems, multiple users share the same bandwidth with fixed capacity. Upon the arrival of each user, it requests for at most $w_i$ amount of bandwidth and each unit of bandwidth has a value $v_i$. The system operator determines how much bandwidth is allocated to the user with the objective of maximizing the total profit of the allocated bandwidth. OFKP exactly models this problem and the integral version of the online knapsack cannot provide a meaningful solution, especially when $w_i$ is comparable to the bandwidth capacity.
  We do agree that it would be interesting to extend our approach to integral knapsack problems – often results for the fractional case can be extended to the integral case if we assume that the item sizes are small enough. However, detailed derivation of the results needs further analysis which is beyond the scope of current work.

• (About the algorithmic novelty)
  The key novelty of our algorithm is to carefully design the decisions given an exact prediction of the cutoff value to give a better than 2 competitive ratio, which matches our lower bound results. Further, we show that this idea can be extended when the prediction of cutoff value is not exact (e.g., interval prediction or probabilistic prediction). This approximate setting is much more interesting in real world settings and requires a significantly more careful analysis. Prior work has considered much stronger prediction models – e.g. frequency predictions for all values [5]. Note that our prediction model is much weaker – as an approximation to the cutoff threshold can be derived from a set of frequency predictions but not vice-versa.

• (About the comparison benchmark)
  Assuming by optimal online you mean matching upper bound and lower bound for the algorithm. We would like to clarify that without prediction Algorithm 1 is optimal which we used in comparisons and given the prediction of the cutoff value, we have already derived the optimal online algorithm(Algorithm 2,3) that can achieve the best possible competitive ratio.

• (Additional clarifications)
  Thanks to the reviewer for their suggestions on the presentation. We clarify those points below and will revise the paper accordingly. (i) Randomized algorithms also cannot achieve a bounded competitive ratio for the most general online (integral) knapsack problem without additional assumptions, which has been shown in [3]. (ii) We will add a citation in Section 2.2 to further clarify that the threshold-based algorithm (Algorithm TA) is due to [4]. In fact, we have cited this paper when presenting Lemma 2.1 that claims the performance of Algorithms. (iii) we will address the typos in Prediction Model II and adopt your suggestion to include an explanatory comment on line 10 of Algorithm 3.

• (Justification on algorithm 3 solves unique values problem)
  If one perturbs the input values by an arbitrarily small amount, then uniqueness can be ensured while keeping the objective function the same up to an arbitrarily small error. Thus, our results for interval predictions in $$ \ell,u $$ (with $u/\ell$ arbitrarily close to 1) indeed capture the non-unique value setting. We will add an explanation of this in the paper. We do think that extending our $1+\hat{w}$ competitive ratio result to the non-unique value/interval settings would be interesting. In fact, we are actively working in this direction, and have a conjectured algorithm but an incomplete analysis.

[1] John Noga, et al.. An online partially fractional knapsack problem. 8th International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'05), 2005.

[2] Hyun-Woo Kim, et al. Dynamic bandwidth provisioning using ARIMA-based traffic forecasting for Mobile WiMAX. Computer Communications 34.1,2011.

[3] Y. Zhou, D. Chakrabarty, and R. Lukose. Budget constrained bidding in keyword auctions and online knapsack problems. In Proceedings of the 17th International Conference on World Wide Web, pp. 1243–1244,2008.

[4] B. Sun, A. Zeynali, T. Li, M. Hajiesmaili, A. Wierman, and D.H.K. Tsang. Competitive algorithms for the online multiple knapsack problem with application to electric vehicle charging, 2021.

[5] S. Im, R. Kumar, M. Montazer Qaem, and M. Purohit, Online Knapsack with Frequency Predictions, in Advances in Neural Information Processing Systems, 2021.

Thank you for your detailed and positive review, and your suggestions. We will take them into account while revising the paper. Please find our response below:

• (LP definition)
  You are correct that in Section 2.1, we give an LP formulation only to illustrate the (offline) problem in a concise manner and convey to the reader the meaning of the problem parameters (e.g. decision variables $x_t$). It is not meant to indicate usage of LP solvers. We will clarify this in the writing.

• (Algorithm 2 (PPA-n))
  Thanks -- you are completely right that replacing line 7 with $x_i = w_i$ can help. However, if we do this, then we also need to take into account the 'extra capacity' spent on high-value items when determining how much of $\hat{v}$ to include in line 9. If we do not do this, then we may achieve competitive ratio worse than two. For example, consider the following sequence of items, where each item is represented by a (value, weight) pair: (10, 0.5), (1, 1), (10000, 0.49). The optimal offline solution will accept 0.5 of the first item, 0.01 of the second item, and 0.49 of the final item. Note that $\hat{v} = 1$.
  If line 7 is replaced with $x_i = w_i$, PPA-n will accept all of the first item and half of the second item, leaving no remaining capacity to accept the third (most valuable) item. This results in a competitive ratio which can be arbitrarily worse than 2.
  This trade-off between accepting too much early on and leaving enough space to accommodate high-value items which arrive later is the key insight into our design and analysis of PPA-a (Algorithm 3).
  Observe that in PPA-a, in line 8 we indeed set $x_i = w_i$ and in line 12, when admitting the item $\hat{v}$, we take into account the total capacity s of admitted items with higher values.
  Algorithm 2 is meant to serve as a simple warm up to this more optimal, but somewhat more complex procedure.

• (Minor comments)
  We will revise Algorithm 2 to initialize the variable $z = 0$ in the first line. Regarding line 12 in Algorithm 3 we believe our pseudocode is formally correct, we will clarify the presentation of the PPA-a algorithm. The primary intuition for line 12 originates in the proof of Theorem 3.4, which was deferred to the Appendix for space purposes. The high-level idea is as follows: we aim to set $x_i$ such that we accept exactly enough of the critical valued item to guarantee a competitive ratio of $(1 + \hat{\omega})$ in the event that the current item is the final item. Informally, this will be the amount that we expected to take if the critical valued item arrives first, minus any extra selections made in previous time steps (i.e. items of strictly better unit value which have already been accepted).

• (Q1: the performance when the single value prediction is not completely accurate)
  Since the setting we study is adversarial, there will be no competitive ratio guarantee for Algorithms 2 and 3 if predictions are not accurate. This motivates our development of IPA and PIPA (Algorithms 4 and 5), which are able to “hedge” against untrusted / inaccurate predictions, and use a similar approach as PPA-a (Algorithm 2) to solve IPA(Algorithm 4) which allow us to have prediction over range $$ \ell,u $$, moreover, we can use algorithm 2,3,4 in PIPA as subroutine. Algorithms 2 and 3 can be thought of as intermediate results building up to these more robust algorithms.

• (Q2)
  We can model arbitrary error in the interval prediction model, whether the prediction error is additive or multiplicative. For additive error, we can find the interval $[\hat{v}-e, \hat{v}+e]$, and for multiplicative error, we can find the interval $[\hat{v} \times (1+e), \hat{v} \times \frac{1}{1+e}]$. The only difference between these two cases would be the rate of increase in the competitive ratio, which is $\ln(u/\ell) + 2$.