DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2018.19

Experimental Study of Compressed Stack Algorithms in Limited Memory Environments

Authors: Jean-François Baffier, Yago Diez, and Matias Korman

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

Abstract

The compressed stack is a data structure designed by Barba et al. (Algorithmica 2015) that allows to reduce the amount of memory needed by a certain class of algorithms at the cost of increasing its runtime. In this paper we introduce the first implementation of this data structure and make its source code publicly available. Together with the implementation we analyse the performance of the compressed stack. In our synthetic experiments, considering different test scenarios and using data sizes ranging up to 2^{30} elements, we compare it with the classic (uncompressed) stack, both in terms of runtime and memory used. Our experiments show that the compressed stack needs significantly less memory than the usual stack (this difference is significant for inputs containing 2000 or more elements). Overall, with a proper choice of parameters, we can save a significant amount of space (from two to four orders of magnitude) with a small increase in the runtime (2.32 times slower on average than the classic stack). These results hold even in test scenarios specifically designed to be challenging for the compressed stack.

Cite as

Jean-François Baffier, Yago Diez, and Matias Korman. Experimental Study of Compressed Stack Algorithms in Limited Memory Environments. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{baffier_et_al:LIPIcs.SEA.2018.19,
  author =	{Baffier, Jean-Fran\c{c}ois and Diez, Yago and Korman, Matias},
  title =	{{Experimental Study of Compressed Stack Algorithms in Limited Memory Environments}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{19:1--19:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.19},
  URN =		{urn:nbn:de:0030-drops-89549},
  doi =		{10.4230/LIPIcs.SEA.2018.19},
  annote =	{Keywords: Stack algorithms, time-space trade-off, convex hull, implementation}
}

Document

DOI: 10.4230/LIPIcs.FUN.2016.4

Hanabi is NP-complete, Even for Cheaters who Look at Their Cards

Authors: Jean-Francois Baffier, Man-Kwun Chiu, Yago Diez, Matias Korman, Valia Mitsou, André van Renssen, Marcel Roeloffzen, and Yushi Uno

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)

Abstract

This paper studies a cooperative card game called Hanabi from an algorithmic combinatorial game theory viewpoint. The aim of the game is to play cards from 1 to n in increasing order (this has to be done independently in c different colors). Cards are drawn from a deck one by one. Drawn cards are either immediately played, discarded or stored for future use (overall each player can store up to h cards). The main feature of the game is that players know the cards their partners hold (but not theirs. This information must be shared through hints). We introduce a simplified mathematical model of a single-player version of the game, and show several complexity results: the game is intractable in a general setting even if we forego with the hidden information aspect of the game. On the positive side, the game can be solved in linear time for some interesting restricted cases (i.e., for small values of h and c).

Cite as

Jean-Francois Baffier, Man-Kwun Chiu, Yago Diez, Matias Korman, Valia Mitsou, André van Renssen, Marcel Roeloffzen, and Yushi Uno. Hanabi is NP-complete, Even for Cheaters who Look at Their Cards. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{baffier_et_al:LIPIcs.FUN.2016.4,
  author =	{Baffier, Jean-Francois and Chiu, Man-Kwun and Diez, Yago and Korman, Matias and Mitsou, Valia and van Renssen, Andr\'{e} and Roeloffzen, Marcel and Uno, Yushi},
  title =	{{Hanabi is NP-complete, Even for Cheaters who Look at Their Cards}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.4},
  URN =		{urn:nbn:de:0030-drops-58644},
  doi =		{10.4230/LIPIcs.FUN.2016.4},
  annote =	{Keywords: algorithmic combinatorial game theory, sorting}
}

Search Results

Documents authored by Diez, Yago

Experimental Study of Compressed Stack Algorithms in Limited Memory Environments

Abstract

Cite as

Hanabi is NP-complete, Even for Cheaters who Look at Their Cards

Abstract

Cite as

Thanks for your feedback!

Could not send message