TY - GEN

T1 - Online unit profit knapsack with untrusted predictions

AU - Boyar, Joan

AU - Favrholdt, Lene M.

AU - Larsen, Kim S.

N1 - Funding Information:
Funding Supported in part by the Independent Research Fund Denmark, Natural Sciences, grant DFF-0135-00018B.
Publisher Copyright:
© 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

PY - 2022/6/1

Y1 - 2022/6/1

N2 - A variant of the online knapsack problem is considered in the settings of trusted and untrusted predictions. In Unit Profit Knapsack, the items have unit profit, and it is easy to find an optimal solution offline: Pack as many of the smallest items as possible into the knapsack. For Online Unit Profit Knapsack, the competitive ratio is unbounded. In contrast, previous work on online algorithms with untrusted predictions generally studied problems where an online algorithm with a constant competitive ratio is known. The prediction, possibly obtained from a machine learning source, that our algorithm uses is the average size of those smallest items that fit in the knapsack. For the prediction error in this hard online problem, we use the ratio r = a a where a is the actual value for this average size and a is the prediction. The algorithm presented achieves a competitive ratio of 1 2r for r ≥ 1 and r 2 for r ≤ 1. Using an adversary technique, we show that this is optimal in some sense, giving a trade-off in the competitive ratio attainable for different values of r. Note that the result for accurate advice, r = 1, is only 12 , but we show that no deterministic algorithm knowing the value a can achieve a competitive ratio better than e-1 e ≈ 0.6321 and present an algorithm with a matching upper bound. We also show that this latter algorithm attains a competitive ratio of r e-1 e for r ≤ 1 and e-r e for 1 ≤ r < e, and no deterministic algorithm can be better for both r < 1 and 1 < r < e.

AB - A variant of the online knapsack problem is considered in the settings of trusted and untrusted predictions. In Unit Profit Knapsack, the items have unit profit, and it is easy to find an optimal solution offline: Pack as many of the smallest items as possible into the knapsack. For Online Unit Profit Knapsack, the competitive ratio is unbounded. In contrast, previous work on online algorithms with untrusted predictions generally studied problems where an online algorithm with a constant competitive ratio is known. The prediction, possibly obtained from a machine learning source, that our algorithm uses is the average size of those smallest items that fit in the knapsack. For the prediction error in this hard online problem, we use the ratio r = a a where a is the actual value for this average size and a is the prediction. The algorithm presented achieves a competitive ratio of 1 2r for r ≥ 1 and r 2 for r ≤ 1. Using an adversary technique, we show that this is optimal in some sense, giving a trade-off in the competitive ratio attainable for different values of r. Note that the result for accurate advice, r = 1, is only 12 , but we show that no deterministic algorithm knowing the value a can achieve a competitive ratio better than e-1 e ≈ 0.6321 and present an algorithm with a matching upper bound. We also show that this latter algorithm attains a competitive ratio of r e-1 e for r ≤ 1 and e-r e for 1 ≤ r < e, and no deterministic algorithm can be better for both r < 1 and 1 < r < e.

KW - competitive analysis

KW - knapsack problem

KW - online algorithms

KW - untrusted predictions

U2 - 10.4230/LIPIcs.SWAT.2022.20

DO - 10.4230/LIPIcs.SWAT.2022.20

M3 - Article in proceedings

AN - SCOPUS:85133406303

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022

A2 - Czumaj, Artur

A2 - Xin, Qin

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022

Y2 - 27 June 2022 through 29 June 2022

ER -