Search Results

Documents authored by Böckenhauer, Hans-Joachim

Document
DOI: 10.4230/LIPIcs.MFCS.2026.41
Forbidden Subgraph Problems with Predictions

Authors: Hans-Joachim Böckenhauer, Melvin Jahn, Dennis Komm, and Moritz Stocker

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract
In the Online Delayed Connected H-Node-Deletion Problem, an unweighted graph is revealed vertex by vertex and it must remain free of any induced copies of a specific connected induced forbidden subgraph H at each point in time. To achieve this, an algorithm must, upon each occurrence of H, identify and irrevocably delete one or more vertices. The objective is to delete as few vertices as possible. We provide tight bounds on the competitive ratio for forbidden subgraphs H that do not contain true twins or that do not contain false twins. We further consider the problem within the model of predictions, where the algorithm is provided with a single bit of advice for each revealed vertex. These predictions are considered to be provided by an untrusted source and may be incorrect. We present a family of algorithms solving the problem with predictions and show that it is Pareto-optimal with respect to consistency and robustness for the online vertex cover problem, for 2-connected forbidden subgraphs that do not contain true twins or that do not contain false twins, as well as for any forbidden path of length at least five.
Cite as

Hans-Joachim Böckenhauer, Melvin Jahn, Dennis Komm, and Moritz Stocker. Forbidden Subgraph Problems with Predictions. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 41:1-41:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bockenhauer_et_al:LIPIcs.MFCS.2026.41,
  author =	{B\"{o}ckenhauer, Hans-Joachim and Jahn, Melvin and Komm, Dennis and Stocker, Moritz},
  title =	{{Forbidden Subgraph Problems with Predictions}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{41:1--41:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.41},
  URN =		{urn:nbn:de:0030-drops-274226},
  doi =		{10.4230/LIPIcs.MFCS.2026.41},
  annote =	{Keywords: online node deletion, competitive ratio, forbidden subgraphs, predictions}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.18
Removable Online Knapsack and Advice

Authors: Hans-Joachim Böckenhauer, Fabian Frei, and Peter Rossmanith

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
In the proportional knapsack problem, we are given a knapsack of some capacity and a set of variably sized items. The goal is to pack a selection of these items that fills the knapsack as much as possible. The online version of this problem reveals the items and their sizes not all at once but one by one. For each item, the algorithm has to decide immediately whether to pack it or not. We consider a natural variant of this online knapsack problem, which has been coined removable knapsack. It differs from the classical variant by allowing the removal of any packed item from the knapsack. Repacking is impossible, however: Once an item is removed, it is gone for good. We analyze the advice complexity of this problem. It measures how many advice bits an omniscient oracle needs to provide for an online algorithm to reach any given competitive ratio, which is - understood in its strict sense - just the algorithm’s approximation factor. The online knapsack problem is known for its peculiar advice behavior involving three jumps in competitivity. We show that the advice complexity of the version with removability is quite different but just as interesting: The competitivity starts from the golden ratio when no advice is given. It then drops down to 1+ε for a constant amount of advice already, which requires logarithmic advice in the classical version. Removability comes as no relief to the perfectionist, however: Optimality still requires linear advice as before. These results are particularly noteworthy from a structural viewpoint for the exceptionally slow transition from near-optimality to optimality. Our most important and demanding result shows that the general knapsack problem, which allows an item’s value to differ from its size, exhibits a similar behavior for removability, but with an even more pronounced jump from an unbounded competitive ratio to near-optimality within just constantly many advice bits. This is a unique behavior among the problems considered in the literature so far. An advice analysis is interesting in its own right, as it allows us to measure the information content of a problem and leads to structural insights. But it also provides insurmountable lower bounds, applicable to any kind of additional information about the instances, including predictions provided by machine-learning algorithms and artificial intelligence. Unexpectedly, advice algorithms are useful in various real-life situations, too. For example, they provide smart strategies for cooperation in winner-take-all competitions, where several participants pool together to implement different strategies and share the obtained prize. Further illustrating the versatility of our advice-complexity bounds, our results automatically improve some of the best known lower bounds on the competitive ratio for removable knapsack with randomization. The presented advice algorithms also automatically yield deterministic algorithms for established deterministic models such as knapsack with a resource buffer and various problems with more than one knapsack. In their seminal paper introducing removability to the knapsack problem, Iwama and Taketomi have indeed proposed a multiple knapsack problem for which we can establish a one-to-one correspondence with the advice model; this paper therefore even provides a comprehensive analysis for this up until now neglected problem.
Cite as

Hans-Joachim Böckenhauer, Fabian Frei, and Peter Rossmanith. Removable Online Knapsack and Advice. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bockenhauer_et_al:LIPIcs.STACS.2024.18,
  author =	{B\"{o}ckenhauer, Hans-Joachim and Frei, Fabian and Rossmanith, Peter},
  title =	{{Removable Online Knapsack and Advice}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.18},
  URN =		{urn:nbn:de:0030-drops-197283},
  doi =		{10.4230/LIPIcs.STACS.2024.18},
  annote =	{Keywords: Removable Online Knapsack, Multiple Knapsack, Advice Analysis, Advice Applications, Machine Learning and AI}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.16
Online Simple Knapsack with Reservation Costs

Authors: Hans-Joachim Böckenhauer, Elisabet Burjons, Juraj Hromkovič, Henri Lotze, and Peter Rossmanith

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
In the Online Simple Knapsack Problem we are given a knapsack of unit size 1. Items of size smaller or equal to 1 are presented in an iterative fashion and an algorithm has to decide whether to permanently reject or include each item into the knapsack without any knowledge about the rest of the instance. The goal is then to pack the knapsack as full as possible. In this work, we introduce a third option additional to those of packing and rejecting an item, namely that of reserving an item for the cost of a fixed fraction α of its size. An algorithm may pay this fraction in order to postpone its decision on whether to include or reject the item until after the last item of the instance was presented. While the classical Online Simple Knapsack Problem does not admit any constantly bounded competitive ratio in the deterministic setting, we find that adding the possibility of reservation makes the problem constantly competitive, with varying competitive ratios depending on the value of α. We give upper and lower bounds for the whole range of reservation costs, with tight bounds for costs up to 1/6 - an area that is strictly 2-competitive - , for costs between √2-1 and 1 - an area that is strictly (2+α)-competitive up to ϕ -1, and strictly 1/(1-α)-competitive above ϕ-1, where ϕ is the golden ratio. With our analysis, we find a counterintuitive characteristic of the problem: Intuitively, one would expect that the possibility of rejecting items becomes more and more helpful for an online algorithm with growing reservation costs. However, for higher reservation costs above √2-1, an algorithm that is unable to reject any items tightly matches the lower bound and is thus the best possible. On the other hand, for any positive reservation cost smaller than 1/6, any algorithm that is unable to reject any items performs considerably worse than one that is able to reject.
Cite as

Hans-Joachim Böckenhauer, Elisabet Burjons, Juraj Hromkovič, Henri Lotze, and Peter Rossmanith. Online Simple Knapsack with Reservation Costs. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bockenhauer_et_al:LIPIcs.STACS.2021.16,
  author =	{B\"{o}ckenhauer, Hans-Joachim and Burjons, Elisabet and Hromkovi\v{c}, Juraj and Lotze, Henri and Rossmanith, Peter},
  title =	{{Online Simple Knapsack with Reservation Costs}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.16},
  URN =		{urn:nbn:de:0030-drops-136613},
  doi =		{10.4230/LIPIcs.STACS.2021.16},
  annote =	{Keywords: Online problem, Simple knapsack, Reservation costs}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact