Online Knapsack Problems with Estimates

D 2025

Online Knapsack Problems with Estimates

BALABÁN, Jakub; Matthias GEHNEN; Henri LOTZE; Finn SEESEMANN; Moritz STOCKER et al.

Základní údaje

Originální název

Online Knapsack Problems with Estimates

Autoři

BALABÁN, Jakub; Matthias GEHNEN; Henri LOTZE; Finn SEESEMANN a Moritz STOCKER

Vydání

Dagstuhl, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025), od s. "12:1"-"12:19", 19 s. 2025

Nakladatel

Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/25:00141841

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-388-1

EID Scopus

2-s2.0-105014731847

Klíčová slova anglicky

Knapsack; Online Knapsack; Removability; Estimate; Prediction

Štítky

core_A, firank_A

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 9. 4. 2026 12:04, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

Imagine you are a computer scientist who enjoys attending conferences or workshops within the year. Sadly, your travel budget is limited, so you must select a subset of events you can travel to. When you are aware of all possible events and their costs at the beginning of the year, you can select the subset of the possible events that maximizes your happiness and is within your budget. On the other hand, if you are blind about the options, you will likely have a hard time when trying to decide if you want to register somewhere or not, and will likely regret decisions you made in the future. These scenarios can be modeled by knapsack variants, either by an offline or an online problem. However, both scenarios are somewhat unrealistic: Usually, you will not know the exact costs of each workshop at the beginning of the year. The online version, however, is too pessimistic, as you might already know which options there are and how much they cost roughly. At some point, you have to decide whether to register for some workshop, but then you are aware of the conference fee and the flight and hotel prices. We model this problem within the setting of online knapsack problems with estimates: in the beginning, you receive a list of potential items with their estimated size as well as the accuracy of the estimates. Then, the items are revealed one by one in an online fashion with their actual size, and you need to decide whether to take one or not. In this article, we show a best-possible algorithm for each estimate accuracy δ (i.e., when each actual item size can deviate by ±δ from the announced size) for both the simple knapsack (also known as subset sum problem) and the simple knapsack with removability.

Návaznosti

MUNI/A/1600/2024, interní kód MU

Název: Modelování, analýza a verifikace (2025)

Investor: Masarykova univerzita, Modelování, analýza a verifikace (2025)

MUNI/A/1666/2024, interní kód MU

Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 25

Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 25

Citovat

BALABÁN, Jakub; Matthias GEHNEN; Henri LOTZE; Finn SEESEMANN a Moritz STOCKER. Online Knapsack Problems with Estimates. Online. In Pawel Gawrychowski, Filip Mazowiecki, and Michal Skrzypczak. 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, 2025, s. "12:1"-"12:19", 19 s. ISBN 978-3-95977-388-1.

@inproceedings{2513998,
   author = {Balabán, Jakub and Gehnen, Matthias and Lotze, Henri and Seesemann, Finn and Stocker, Moritz},
   address = {Dagstuhl},
   booktitle = {50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
   editor = {Pawel Gawrychowski, Filip Mazowiecki, and Michal Skrzypczak},
   keywords = {Knapsack; Online Knapsack; Removability; Estimate; Prediction},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Dagstuhl},
   isbn = {978-3-95977-388-1},
   pages = {"12:1"-"12:19"},
   publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
   title = {Online Knapsack Problems with Estimates},
   year = {2025}
}

TY  - CONF
ID  - 2513998
AU  - Balabán, Jakub - Gehnen, Matthias - Lotze, Henri - Seesemann, Finn - Stocker, Moritz
PY  - 2025
TI  - Online Knapsack Problems with Estimates
PB  - Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik
CY  - Dagstuhl
SN  - 9783959773881
KW  - Knapsack
KW  - Online Knapsack
KW  - Removability
KW  - Estimate
KW  - Prediction
N2  - Imagine you are a computer scientist who enjoys attending conferences or workshops within the year. Sadly, your travel budget is limited, so you must select a subset of events you can travel to. When you are aware of all possible events and their costs at the beginning of the year, you can select the subset of the possible events that maximizes your happiness and is within your budget. On the other hand, if you are blind about the options, you will likely have a hard time when trying to decide if you want to register somewhere or not, and will likely regret decisions you made in the future. These scenarios can be modeled by knapsack variants, either by an offline or an online problem. However, both scenarios are somewhat unrealistic: Usually, you will not know the exact costs of each workshop at the beginning of the year. The online version, however, is too pessimistic, as you might already know which options there are and how much they cost roughly. At some point, you have to decide whether to register for some workshop, but then you are aware of the conference fee and the flight and hotel prices. We model this problem within the setting of online knapsack problems with estimates: in the beginning, you receive a list of potential items with their estimated size as well as the accuracy of the estimates. Then, the items are revealed one by one in an online fashion with their actual size, and you need to decide whether to take one or not. In this article, we show a best-possible algorithm for each estimate accuracy δ (i.e., when each actual item size can deviate by ±δ from the announced size) for both the simple knapsack (also known as subset sum problem) and the simple knapsack with removability.
ER  -

BALABÁN, Jakub; Matthias GEHNEN; Henri LOTZE; Finn SEESEMANN a Moritz STOCKER. Online Knapsack Problems with Estimates. Online. In Pawel Gawrychowski, Filip Mazowiecki, and Michal Skrzypczak. \textit{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)}. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum f$\{\backslash$''$\{$u$\}\}$r Informatik, 2025, s.~''12:1''-''12:19'', 19 s. ISBN~978-3-95977-388-1.

Přehled o publikaci