Online Unit Profit Knapsack with Predictions

Joan Boyar, Lene M. Favrholdt, Kim S. Larsen*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

5 Downloads (Pure)

Abstract

A variant of the online knapsack problem is considered in the setting of predictions. In Unit Profit Knapsack, the items have unit profit, i.e., the goal is to pack as many items as possible. For Online Unit Profit Knapsack, the competitive ratio is unbounded. In contrast, it is easy to find an optimal solution offline: Pack as many of the smallest items as possible into the knapsack. The prediction available to the online algorithm 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=aa^ where a is the actual value for this average size and a^ is the prediction. We give an algorithm which is e-1e-competitive, if r=1, and this is best possible among online algorithms knowing a and nothing else. More generally, the algorithm has a competitive ratio of e-1er, if r≤1, and e-rer, if 1≤r<e. Any algorithm with a better competitive ratio for some r<1 will have a worse competitive ratio for some r>1. To obtain a positive competitive ratio for all r, we adjust the algorithm, resulting in a competitive ratio of 12r for r≥1 and r2 for r≤1. We show that improving the result for any r<1 leads to a worse result for some r>1.

Original languageEnglish
JournalAlgorithmica
Volume86
Issue number9
Pages (from-to)2786-2821
ISSN0178-4617
DOIs
Publication statusPublished - Sept 2024

Keywords

  • Competitive analysis
  • Knapsack problem
  • Online algorithms
  • Predictions

Fingerprint

Dive into the research topics of 'Online Unit Profit Knapsack with Predictions'. Together they form a unique fingerprint.

Cite this