14 Search Results for "Barbay, J�r�my"

Document
DOI: 10.4230/LIPIcs.CPM.2023.1
Trie-Compressed Adaptive Set Intersection

Authors: Diego Arroyuelo and Juan Pablo Castillo

Published in: LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)

Abstract
We introduce space- and time-efficient algorithms and data structures for the offline set intersection problem. We show that a sorted integer set S ⊆ [0..u) of n elements can be represented using compressed space while supporting k-way intersections in adaptive O(kδlg(u/δ)) time, δ being the alternation measure introduced by Barbay and Kenyon. Our experimental results suggest that our approaches are competitive in practice, outperforming the most efficient alternatives (Partitioned Elias-Fano indexes, Roaring Bitmaps, and Recursive Universe Partitioning (RUP)) in several scenarios, offering in general relevant space-time trade-offs.
Cite as

Diego Arroyuelo and Juan Pablo Castillo. Trie-Compressed Adaptive Set Intersection. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{arroyuelo_et_al:LIPIcs.CPM.2023.1,
  author =	{Arroyuelo, Diego and Castillo, Juan Pablo},
  title =	{{Trie-Compressed Adaptive Set Intersection}},
  booktitle =	{34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)},
  pages =	{1:1--1:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-276-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{259},
  editor =	{Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.1},
  URN =		{urn:nbn:de:0030-drops-179552},
  doi =		{10.4230/LIPIcs.CPM.2023.1},
  annote =	{Keywords: Set intersection problem, Adaptive Algorithms, Compressed and compact data structures}
}
Document
DOI: 10.4230/LIPIcs.FUN.2022.19
Wordle Is NP-Hard

Authors: Daniel Lokshtanov and Bernardo Subercaseaux

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract
Wordle is a single-player word-guessing game where the goal is to discover a secret word w that has been chosen from a dictionary D. In order to discover w, the player can make at most 𝓁 guesses, which must also be words from D, all words in D having the same length k. After each guess, the player is notified of the positions in which their guess matches the secret word, as well as letters in the guess that appear in the secret word in a different position. We study the game of Wordle from a complexity perspective, proving NP-hardness of its natural formalization: to decide given a dictionary D and an integer 𝓁 if the player can guarantee to discover the secret word within 𝓁 guesses. Moreover, we prove that hardness holds even over instances where words have length k = 5, and that even in this case it is NP-hard to approximate the minimum number of guesses required to guarantee discovering the secret word. We also present results regarding its parameterized complexity and offer some related open problems.
Cite as

Daniel Lokshtanov and Bernardo Subercaseaux. Wordle Is NP-Hard. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 19:1-19:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lokshtanov_et_al:LIPIcs.FUN.2022.19,
  author =	{Lokshtanov, Daniel and Subercaseaux, Bernardo},
  title =	{{Wordle Is NP-Hard}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{19:1--19:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.19},
  URN =		{urn:nbn:de:0030-drops-159893},
  doi =		{10.4230/LIPIcs.FUN.2022.19},
  annote =	{Keywords: wordle, np-hardness, complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.24
An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility

Authors: Jean Cardinal, Justin Dallant, and John Iacono

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
Afshani, Barbay and Chan (2017) introduced the notion of instance-optimal algorithm in the order-oblivious setting. An algorithm A is instance-optimal in the order-oblivious setting for a certain class of algorithms 𝒜 if the following hold: - A takes as input a sequence of objects from some domain; - for any instance σ and any algorithm A' ∈ 𝒜, the runtime of A on σ is at most a constant factor removed from the runtime of A' on the worst possible permutation of σ. If we identify permutations of a sequence as representing the same instance, this essentially states that A is optimal on every possible input (and not only in the worst case). We design instance-optimal algorithms for the problem of reporting, given a bichromatic set of points in the plane S, all pairs consisting of points of different color which span an empty axis-aligned rectangle (or reporting all points which appear in such a pair). This problem has applications for training-set reduction in nearest-neighbour classifiers. It is also related to the problem consisting of finding the decision boundaries of a euclidean nearest-neighbour classifier, for which Bremner et al. (2005) gave an optimal output-sensitive algorithm. By showing the existence of an instance-optimal algorithm in the order-oblivious setting for this problem we push the methods of Afshani et al. closer to their limits by adapting and extending them to a setting which exhibits highly non-local features. Previous problems for which instance-optimal algorithms were proven to exist were based solely on local relationships between points in a set.
Cite as

Jean Cardinal, Justin Dallant, and John Iacono. An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cardinal_et_al:LIPIcs.ESA.2021.24,
  author =	{Cardinal, Jean and Dallant, Justin and Iacono, John},
  title =	{{An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.24},
  URN =		{urn:nbn:de:0030-drops-146057},
  doi =		{10.4230/LIPIcs.ESA.2021.24},
  annote =	{Keywords: computational geometry, instance-optimality, colored point sets, empty rectangles, visibility}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.23
The Computational Complexity of Evil Hangman

Authors: Jérémy Barbay and Bernardo Subercaseaux

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
The game of Hangman is a classical asymmetric two player game in which one player, the setter, chooses a secret word from a language, that the other player, the guesser, tries to discover through single letter matching queries, answered by all occurrences of this letter if any. In the Evil Hangman variant, the setter can change the secret word during the game, as long as the new choice is consistent with the information already given to the guesser. We show that a greedy strategy for Evil Hangman can perform arbitrarily far from optimal, and most importantly, that playing optimally as an Evil Hangman setter is computationally difficult. The latter result holds even assuming perfect knowledge of the language, for several classes of languages, ranging from Finite to Turing Computable. The proofs are based on reductions to Dominating Set on 3-regular graphs and to the Membership problem, combinatorial problems already known to be computationally hard.
Cite as

Jérémy Barbay and Bernardo Subercaseaux. The Computational Complexity of Evil Hangman. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 23:1-23:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{barbay_et_al:LIPIcs.FUN.2021.23,
  author =	{Barbay, J\'{e}r\'{e}my and Subercaseaux, Bernardo},
  title =	{{The Computational Complexity of Evil Hangman}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{23:1--23:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.23},
  URN =		{urn:nbn:de:0030-drops-127840},
  doi =		{10.4230/LIPIcs.FUN.2021.23},
  annote =	{Keywords: combinatorial game theory, computational complexity, decidability, hangman}
}
Document
DOI: 10.4230/DagRep.8.7.44
Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281)

Authors: Jérémy Barbay, Johannes Fischer, Stefan Kratsch, and Srinivasa Rao Satti

Published in: Dagstuhl Reports, Volume 8, Issue 7 (2019)

Abstract
From the 8th of July 2018 to the 13th of July 2018, a Dagstuhl Seminar took place with the topic "Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices". There, 40 participants from as many as 14 distinct countries and four distinct research areas, dealing with running time analysis and space usage analysis of algorithms and data structures, gathered to discuss results and techniques to "go beyond the worst-case" for classes of structurally restricted inputs, both for (fast) algorithms and (compressed) data structures. The seminar consisted of (1) a first session of personal introduction, each participant presenting his expertise and themes of interests in two slides; (2) a series of four technical talks; and (3) a larger series of presentations of open problems, with ample time left for the participants to gather and work on such open problems.
Cite as

Jérémy Barbay, Johannes Fischer, Stefan Kratsch, and Srinivasa Rao Satti. Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281). In Dagstuhl Reports, Volume 8, Issue 7, pp. 44-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{barbay_et_al:DagRep.8.7.44,
  author =	{Barbay, J\'{e}r\'{e}my and Fischer, Johannes and Kratsch, Stefan and Satti, Srinivasa Rao},
  title =	{{Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281)}},
  pages =	{44--61},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{8},
  number =	{7},
  editor =	{Barbay, J\'{e}r\'{e}my and Fischer, Johannes and Kratsch, Stefan and Satti, Srinivasa Rao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.8.7.44},
  URN =		{urn:nbn:de:0030-drops-101724},
  doi =		{10.4230/DagRep.8.7.44},
  annote =	{Keywords: adaptive (analysis of) algorithms, compressed data structures, compressed indices, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.63
Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs

Authors: J. Ian Munro and Sebastian Wild

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
We present two stable mergesort variants, "peeksort" and "powersort", that exploit existing runs and find nearly-optimal merging orders with negligible overhead. Previous methods either require substantial effort for determining the merging order (Takaoka 2009; Barbay & Navarro 2013) or do not have an optimal worst-case guarantee (Peters 2002; Auger, Nicaud & Pivoteau 2015; Buss & Knop 2018) . We demonstrate that our methods are competitive in terms of running time with state-of-the-art implementations of stable sorting methods.
Cite as

J. Ian Munro and Sebastian Wild. Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 63:1-63:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{munro_et_al:LIPIcs.ESA.2018.63,
  author =	{Munro, J. Ian and Wild, Sebastian},
  title =	{{Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{63:1--63:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.63},
  URN =		{urn:nbn:de:0030-drops-95265},
  doi =		{10.4230/LIPIcs.ESA.2018.63},
  annote =	{Keywords: adaptive sorting, nearly-optimal binary search trees, Timsort}
}
Document
DOI: 10.4230/LIPIcs.CPM.2017.31
Synergistic Solutions on MultiSets

Authors: Jérémy Barbay, Carlos Ochoa, and Srinivasa Rao Satti

Published in: LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)

Abstract
Karp et al. (1988) described Deferred Data Structures for Multisets as "lazy" data structures which partially sort data to support online rank and select queries, with the minimum amount of work in the worst case over instances of size n and number of queries q fixed. Barbay et al. (2016) refined this approach to take advantage of the gaps between the positions hit by the queries (i.e., the structure in the queries). We develop new techniques in order to further refine this approach and take advantage all at once of the structure (i.e., the multiplicities of the elements), some notions of local order (i.e., the number and sizes of runs) and global order (i.e., the number and positions of existing pivots) in the input; and of the structure and order in the sequence of queries. Our main result is a synergistic deferred data structure which outperforms all solutions in the comparison model that take advantage of only a subset of these features. As intermediate results, we describe two new synergistic sorting algorithms, which take advantage of some notions of structure and order (local and global) in the input, improving upon previous results which take advantage only of the structure (Munro and Spira 1979) or of the local order (Takaoka 1997) in the input; and one new multiselection algorithm which takes advantage of not only the order and structure in the input, but also of the structure in the queries.
Cite as

Jérémy Barbay, Carlos Ochoa, and Srinivasa Rao Satti. Synergistic Solutions on MultiSets. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{barbay_et_al:LIPIcs.CPM.2017.31,
  author =	{Barbay, J\'{e}r\'{e}my and Ochoa, Carlos and Satti, Srinivasa Rao},
  title =	{{Synergistic Solutions on MultiSets}},
  booktitle =	{28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-039-2},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{78},
  editor =	{K\"{a}rkk\"{a}inen, Juha and Radoszewski, Jakub and Rytter, Wojciech},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.31},
  URN =		{urn:nbn:de:0030-drops-73441},
  doi =		{10.4230/LIPIcs.CPM.2017.31},
  annote =	{Keywords: deferred data structure, multivariate analysis, quick sort, select}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.81
Tight Hardness Results for Maximum Weight Rectangles

Authors: Arturs Backurs, Nishanth Dikkala, and Christos Tzamos

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
Given n weighted points (positive or negative) in d dimensions, what is the axis-aligned box which maximizes the total weight of the points it contains? The best known algorithm for this problem is based on a reduction to a related problem, the Weighted Depth problem [Chan, FOCS, 2013], and runs in time O(n^d). It was conjectured [Barbay et al., CCCG, 2013] that this runtime is tight up to subpolynomial factors. We answer this conjecture affirmatively by providing a matching conditional lower bound. We also provide conditional lower bounds for the special case when points are arranged in a grid (a well studied problem known as Maximum Subarray problem) as well as for other related problems. All our lower bounds are based on assumptions that the best known algorithms for the All-Pairs Shortest Paths problem (APSP) and for the Max-Weight k-Clique problem in edge-weighted graphs are essentially optimal.
Cite as

Arturs Backurs, Nishanth Dikkala, and Christos Tzamos. Tight Hardness Results for Maximum Weight Rectangles. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 81:1-81:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{backurs_et_al:LIPIcs.ICALP.2016.81,
  author =	{Backurs, Arturs and Dikkala, Nishanth and Tzamos, Christos},
  title =	{{Tight Hardness Results for Maximum Weight Rectangles}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{81:1--81:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.81},
  URN =		{urn:nbn:de:0030-drops-62040},
  doi =		{10.4230/LIPIcs.ICALP.2016.81},
  annote =	{Keywords: Maximum Rectangles, Hardness in P}
}
Document
DOI: 10.4230/LIPIcs.CPM.2016.29
Optimal Prefix Free Codes with Partial Sorting

Authors: Jérémy Barbay

Published in: LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)

Abstract
We describe an algorithm computing an optimal prefix free code for n unsorted positive weights in less time than required to sort them on many large classes of instances, identified by a new measure of difficulty for this problem, the alternation alpha. This asymptotical complexity is within a constant factor of the optimal in the algebraic decision tree computational model, in the worst case over all instances of fixed size n and alternation alpha. Such results refine the state of the art complexity in the worst case over instances of size n in the same computational model, a landmark in compression and coding since 1952, by the mere combination of van Leeuwen's algorithm to compute optimal prefix free codes from sorted weights (known since 1976), with Deferred Data Structures to partially sort multisets (known since 1988).
Cite as

Jérémy Barbay. Optimal Prefix Free Codes with Partial Sorting. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{barbay:LIPIcs.CPM.2016.29,
  author =	{Barbay, J\'{e}r\'{e}my},
  title =	{{Optimal Prefix Free Codes with Partial Sorting}},
  booktitle =	{27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)},
  pages =	{29:1--29:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-012-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{54},
  editor =	{Grossi, Roberto and Lewenstein, Moshe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.29},
  URN =		{urn:nbn:de:0030-drops-60635},
  doi =		{10.4230/LIPIcs.CPM.2016.29},
  annote =	{Keywords: Deferred Data Structure, Huffman, Median, Optimal Prefix Free Codes, van Leeuwen.}
}
Document
DOI: 10.4230/LIPIcs.FUN.2016.5
Selenite Towers Move Faster Than Hanoï Towers, But Still Require Exponential Time

Authors: Jérémy Barbay

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

Abstract
The Hanoi Tower problem is a classic exercise in recursive programming: the solution has a simple recursive definition, and its complexity and the matching lower bound correspond to the solution of a simple recursive function (the solution is so simple that most students memorize it and regurgitate it at exams without truly understanding it). We describe how some minor change in the rules of the Hanoi Tower yields various increases of difficulty in the solution, so that to require a deeper mastery of recursion than the classical Hanoi Tower problem. In particular, we analyze the Selenite Tower problem, where just changing the insertion and extraction positions from the top to the middle of the tower results in a surprising increase in the intricacy of the solution: such a tower of n disks can be optimally moved in 3^(n/2) moves for n even (i.e. less than a Hanoi Tower of same height), via 5 recursive functions (or, equivalently, one recursion function with five states following three distinct patterns).
Cite as

Jérémy Barbay. Selenite Towers Move Faster Than Hanoï Towers, But Still Require Exponential Time. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{barbay:LIPIcs.FUN.2016.5,
  author =	{Barbay, J\'{e}r\'{e}my},
  title =	{{Selenite Towers Move Faster Than Hano\"{i} Towers, But Still Require Exponential Time}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{5:1--5:20},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.5},
  URN =		{urn:nbn:de:0030-drops-58729},
  doi =		{10.4230/LIPIcs.FUN.2016.5},
  annote =	{Keywords: Br\"{a}hma tower, Disk Pile, Hanoi Tower, Levitating Tower, Recursivity}
}
Document
DOI: 10.4230/DagSemProc.09171.1
09171 Abstracts Collection – Adaptive, Output Sensitive, Online and Parameterized Algorithms

Authors: Jérémy Barbay, Rolf Klein, Alejandro López-Ortiz, and Rolf Niedermeier

Published in: Dagstuhl Seminar Proceedings, Volume 9171, Adaptive, Output Sensitive, Online and Parameterized Algorithms (2009)

Abstract
From 19.01. to 24.04.2009, the Dagstuhl Seminar 09171 ``Adaptive, Output Sensitive, Online and Parameterized Algorithms '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Jérémy Barbay, Rolf Klein, Alejandro López-Ortiz, and Rolf Niedermeier. 09171 Abstracts Collection – Adaptive, Output Sensitive, Online and Parameterized Algorithms. In Adaptive, Output Sensitive, Online and Parameterized Algorithms. Dagstuhl Seminar Proceedings, Volume 9171, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{barbay_et_al:DagSemProc.09171.1,
  author =	{Barbay, J\'{e}r\'{e}my and Klein, Rolf and L\'{o}pez-Ortiz, Alejandro and Niedermeier, Rolf},
  title =	{{09171 Abstracts Collection  – Adaptive, Output Sensitive, Online and Parameterized Algorithms}},
  booktitle =	{Adaptive, Output Sensitive, Online and Parameterized Algorithms},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9171},
  editor =	{J\'{e}r\'{e}my Barbay and Rolf Klein and Alejandro Ortiz-L\'{o}pez and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09171.1},
  URN =		{urn:nbn:de:0030-drops-21228},
  doi =		{10.4230/DagSemProc.09171.1},
  annote =	{Keywords: Adaptive analysis, instance optimal algoritms, fixed parameter tractable, output sensitive algorithms}
}
Document
DOI: 10.4230/DagSemProc.09171.2
09171 Executive Summary – Adaptive, Output Sensitive, Online and Parameterized Algorithms

Authors: Jérémy Barbay, Rolf Klein, Alejandro López-Ortiz, and Rolf Niedermeier

Published in: Dagstuhl Seminar Proceedings, Volume 9171, Adaptive, Output Sensitive, Online and Parameterized Algorithms (2009)

Abstract
Traditionally the analysis of algorithms measures the complexity of a problem or algorithm in terms of the worst-case behavior over all inputs of a given size. However, in certain cases an improved algorithm can be obtained by considering a finer partition of the input space. As this idea has been independently rediscovered in many areas, the workshop gathered participants from different fields in order to explore the impact and the limits of this technique, in the hope to spring new collaboration and to seed the unification of the technique.
Cite as

Jérémy Barbay, Rolf Klein, Alejandro López-Ortiz, and Rolf Niedermeier. 09171 Executive Summary – Adaptive, Output Sensitive, Online and Parameterized Algorithms. In Adaptive, Output Sensitive, Online and Parameterized Algorithms. Dagstuhl Seminar Proceedings, Volume 9171, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{barbay_et_al:DagSemProc.09171.2,
  author =	{Barbay, J\'{e}r\'{e}my and Klein, Rolf and L\'{o}pez-Ortiz, Alejandro and Niedermeier, Rolf},
  title =	{{09171 Executive Summary – Adaptive, Output Sensitive, Online and Parameterized Algorithms}},
  booktitle =	{Adaptive, Output Sensitive, Online and Parameterized Algorithms},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9171},
  editor =	{J\'{e}r\'{e}my Barbay and Rolf Klein and Alejandro Ortiz-L\'{o}pez and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09171.2},
  URN =		{urn:nbn:de:0030-drops-21207},
  doi =		{10.4230/DagSemProc.09171.2},
  annote =	{Keywords: Adaptive analysis, instance optimal algorithms, fixed parameter tractable, output sensitive algorithms}
}
Document
DOI: 10.4230/DagSemProc.09171.3
Parameterized Analysis of Online Steiner Tree Problems

Authors: Spyros Angelopoulos

Published in: Dagstuhl Seminar Proceedings, Volume 9171, Adaptive, Output Sensitive, Online and Parameterized Algorithms (2009)

Abstract
Steiner tree problems occupy a central place in both areas of approximation and on-line algorithms. Many variants have been studied from the point of view of competitive analysis, and for several of these variants tight bounds are known. However, in several cases, worst-case analysis is overly pessimistic, which fails to explain the relative performance of algorithms. We show how adaptive analysis can help resolve this problem. As case studies, we consider the Steiner tree problem in directed graphs, and the Priority Steiner tree problem.
Cite as

Spyros Angelopoulos. Parameterized Analysis of Online Steiner Tree Problems. In Adaptive, Output Sensitive, Online and Parameterized Algorithms. Dagstuhl Seminar Proceedings, Volume 9171, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{angelopoulos:DagSemProc.09171.3,
  author =	{Angelopoulos, Spyros},
  title =	{{Parameterized Analysis of Online Steiner Tree Problems}},
  booktitle =	{Adaptive, Output Sensitive, Online and Parameterized Algorithms},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9171},
  editor =	{J\'{e}r\'{e}my Barbay and Rolf Klein and Alejandro Ortiz-L\'{o}pez and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09171.3},
  URN =		{urn:nbn:de:0030-drops-21210},
  doi =		{10.4230/DagSemProc.09171.3},
  annote =	{Keywords: Online algorithms, Steiner tree problems, adaptive and parameteried analysis}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1814
Compressed Representations of Permutations, and Applications

Authors: Jeremy Barbay and Gonzalo Navarro

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
We explore various techniques to compress a permutation $\pi$ over $n$ integers, taking advantage of ordered subsequences in $\pi$, while supporting its application $\pi(i)$ and the application of its inverse $\pi^{-1}(i)$ in small time. Our compression schemes yield several interesting byproducts, in many cases matching, improving or extending the best existing results on applications such as the encoding of a permutation in order to support iterated applications $\pi^{k}(i)$ of it, of integer functions, and of inverted lists and suffix arrays.
Cite as

Jeremy Barbay and Gonzalo Navarro. Compressed Representations of Permutations, and Applications. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 111-122, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{barbay_et_al:LIPIcs.STACS.2009.1814,
  author =	{Barbay, Jeremy and Navarro, Gonzalo},
  title =	{{Compressed Representations of Permutations, and Applications}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{111--122},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1814},
  URN =		{urn:nbn:de:0030-drops-18148},
  doi =		{10.4230/LIPIcs.STACS.2009.1814},
  annote =	{Keywords: Compression, Permutations, Succinct data structures, Adaptive sorting}
}
  • Refine by Author
  • 7 Barbay, Jérémy
  • 2 Klein, Rolf
  • 2 López-Ortiz, Alejandro
  • 2 Niedermeier, Rolf
  • 2 Satti, Srinivasa Rao
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Problems, reductions and completeness
  • 1 Information systems → Information retrieval query processing
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Data compression
  • Show More...

  • Refine by Keyword
  • 2 Adaptive analysis
  • 2 fixed parameter tractable
  • 2 output sensitive algorithms
  • 1 Adaptive Algorithms
  • 1 Adaptive sorting
  • Show More...

  • Refine by Type
  • 14 document

  • Refine by Publication Year
  • 4 2009
  • 3 2016
  • 1 2017
  • 1 2018
  • 1 2019
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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