Search Results

Documents authored by Gehnen, Matthias

Document
DOI: 10.4230/LIPIcs.FUN.2024.16
Tetris Is Not Competitive

Authors: Matthias Gehnen and Luca Venier

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract
In the video game Tetris, a player has to decide how to place pieces on a board that are revealed by the game one after another. We show that the missing information about the upcoming pieces is indeed crucial to a player’s success. We present a construction for piece sequences that force (online) players without or with a finite preview of upcoming pieces to lose while (offline) players who know the entire piece sequence can clear the board and continue to play. From a competitive analysis perspective, it follows that there cannot be any c-competitive online algorithm for various optimization goals in the context of playing Tetris. Furthermore, we improve existing results by providing a construction for piece sequences which force every player to lose for every possible board size with at least two columns. With this construction, we are also able to show that an instance with just 435 pieces is sufficient to force every player to lose on a standard-size board with ten columns and twenty rows.
Cite as

Matthias Gehnen and Luca Venier. Tetris Is Not Competitive. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gehnen_et_al:LIPIcs.FUN.2024.16,
  author =	{Gehnen, Matthias and Venier, Luca},
  title =	{{Tetris Is Not Competitive}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{16:1--16:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.16},
  URN =		{urn:nbn:de:0030-drops-199242},
  doi =		{10.4230/LIPIcs.FUN.2024.16},
  annote =	{Keywords: Online Algorithms, Tetris}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.37
Online Simple Knapsack with Bounded Predictions

Authors: Matthias Gehnen, Henri Lotze, and Peter Rossmanith

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

Abstract
In the Online Simple Knapsack problem, an algorithm has to pack a knapsack of unit size as full as possible with items that arrive sequentially. The algorithm has no prior knowledge of the length or nature of the instance. Its performance is then measured against the best possible packing of all items of the same instance, over all possible instances. In the classical model for online computation, it is well known that there exists no constant bound for the ratio between the size of an optimal packing and the size of an online algorithm’s packing. A recent variation of the classical online model is that of predictions. In this model, an algorithm is given knowledge about the instance in advance, which is in reality distorted by some factor δ that is commonly unknown to the algorithm. The algorithm only learns about the actual nature of the elements of an input once they are revealed and an irrevocable and immediate decision has to be made. In this work, we study a slight variation of this model in which the error term, and thus the range of sizes that an announced item may actually lay in, is given to the algorithm in advance. It thus knows the range of sizes from which the actual size of each item is selected from. We find that the analysis of the Online Simple Knapsack problem under this model is surprisingly involved. For values of 0 < δ ≤ 1/7, we prove a tight competitive ratio of 2. From there on, we are able to prove that there are at least three alternating functions that describe the competitive ratio. We provide partially tight bounds for the whole range of 0 < δ < 1, showing in particular that the function of the competitive ratio depending on δ is not continuous.
Cite as

Matthias Gehnen, Henri Lotze, and Peter Rossmanith. Online Simple Knapsack with Bounded Predictions. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gehnen_et_al:LIPIcs.STACS.2024.37,
  author =	{Gehnen, Matthias and Lotze, Henri and Rossmanith, Peter},
  title =	{{Online Simple Knapsack with Bounded Predictions}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{37:1--37:20},
  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.37},
  URN =		{urn:nbn:de:0030-drops-197476},
  doi =		{10.4230/LIPIcs.STACS.2024.37},
  annote =	{Keywords: Online problem, Simple Knapsack, Predictions, Machine-Learned Advice}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.29
The Online Simple Knapsack Problem with Reservation and Removability

Authors: Elisabet Burjons, Matthias Gehnen, Henri Lotze, Daniel Mock, and Peter Rossmanith

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
In the online simple knapsack problem, a knapsack of unit size 1 is given and an algorithm is tasked to fill it using a set of items that are revealed one after another. Each item must be accepted or rejected at the time they are presented, and these decisions are irrevocable. No prior knowledge about the set and sequence of items is given. The goal is then to maximize the sum of the sizes of all packed items compared to an optimal packing of all items of the sequence. In this paper, we combine two existing variants of the problem that each extend the range of possible actions for a newly presented item by a new option. The first is removability, in which an item that was previously packed into the knapsack may be finally discarded at any point. The second is reservations, which allows the algorithm to delay the decision on accepting or rejecting a new item indefinitely for a proportional fee relative to the size of the given item. If both removability and reservations are permitted, we show that the competitive ratio of the online simple knapsack problem rises depending on the relative reservation costs. As soon as any nonzero fee has to be paid for a reservation, no online algorithm can be better than 1.5-competitive. With rising reservation costs, this competitive ratio increases up to the golden ratio (ϕ ≈ 1.618) that is reached for relative reservation costs of 1-√5/3 ≈ 0.254. We provide a matching upper and lower bound for relative reservation costs up to this value. From this point onward, the tight bound by Iwama and Taketomi for the removable knapsack problem is the best possible competitive ratio, not using any reservations.
Cite as

Elisabet Burjons, Matthias Gehnen, Henri Lotze, Daniel Mock, and Peter Rossmanith. The Online Simple Knapsack Problem with Reservation and Removability. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 29:1-29:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{burjons_et_al:LIPIcs.MFCS.2023.29,
  author =	{Burjons, Elisabet and Gehnen, Matthias and Lotze, Henri and Mock, Daniel and Rossmanith, Peter},
  title =	{{The Online Simple Knapsack Problem with Reservation and Removability}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{29:1--29:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.29},
  URN =		{urn:nbn:de:0030-drops-185635},
  doi =		{10.4230/LIPIcs.MFCS.2023.29},
  annote =	{Keywords: online algorithm, knapsack, competitive ratio, reservation, preemption}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact