Search Results

Documents authored by Berendsohn, Benjamin Aram

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.19
Fast Approximation of Search Trees on Trees with Centroid Trees

Authors: Benjamin Aram Berendsohn, Ishay Golinsky, Haim Kaplan, and László Kozma

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
Search trees on trees (STTs) generalize the fundamental binary search tree (BST) data structure: in STTs the underlying search space is an arbitrary tree, whereas in BSTs it is a path. An optimal BST of size n can be computed for a given distribution of queries in 𝒪(n²) time [Knuth, Acta Inf. 1971] and centroid BSTs provide a nearly-optimal alternative, computable in 𝒪(n) time [Mehlhorn, SICOMP 1977]. By contrast, optimal STTs are not known to be computable in polynomial time, and the fastest constant-approximation algorithm runs in 𝒪(n³) time [Berendsohn, Kozma, SODA 2022]. Centroid trees can be defined for STTs analogously to BSTs, and they have been used in a wide range of algorithmic applications. In the unweighted case (i.e., for a uniform distribution of queries), the centroid tree can be computed in 𝒪(n) time [Brodal, Fagerberg, Pedersen, Östlin, ICALP 2001; Della Giustina, Prezza, Venturini, SPIRE 2019]. These algorithms, however, do not readily extend to the weighted case. Moreover, no approximation guarantees were previously known for centroid trees in either the unweighted or weighted cases. In this paper we revisit centroid trees in a general, weighted setting, and we settle both the algorithmic complexity of constructing them, and the quality of their approximation. For constructing a weighted centroid tree, we give an output-sensitive 𝒪(n log h) ⊆ 𝒪(n log n) time algorithm, where h is the height of the resulting centroid tree. If the weights are of polynomial complexity, the running time is 𝒪(n log log n). We show these bounds to be optimal, in a general decision tree model of computation. For approximation, we prove that the cost of a centroid tree is at most twice the optimum, and this guarantee is best possible, both in the weighted and unweighted cases. We also give tight, fine-grained bounds on the approximation-ratio for bounded-degree trees and on the approximation-ratio of more general α-centroid trees.
Cite as

Benjamin Aram Berendsohn, Ishay Golinsky, Haim Kaplan, and László Kozma. Fast Approximation of Search Trees on Trees with Centroid Trees. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 19:1-19:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{berendsohn_et_al:LIPIcs.ICALP.2023.19,
  author =	{Berendsohn, Benjamin Aram and Golinsky, Ishay and Kaplan, Haim and Kozma, L\'{a}szl\'{o}},
  title =	{{Fast Approximation of Search Trees on Trees with Centroid Trees}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{19:1--19:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.19},
  URN =		{urn:nbn:de:0030-drops-180711},
  doi =		{10.4230/LIPIcs.ICALP.2023.19},
  annote =	{Keywords: centroid tree, search trees on trees, approximation}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.17
Fixed-Point Cycles and Approximate EFX Allocations

Authors: Benjamin Aram Berendsohn, Simona Boyadzhiyska, and László Kozma

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
We study edge-labelings of the complete bidirected graph K^↔_n with functions that map the set [d] = {1, … , d} to itself. We call a directed cycle in K^↔_n a fixed-point cycle if composing the labels of its edges in order results in a map that has a fixed point, and we say that a labeling is fixed-point-free if no fixed-point cycle exists. For a given d, we ask for the largest value of n, denoted R_f(d), for which there exists a fixed-point-free labeling of K^↔_n. Determining R_f(d) for all d > 0 is a natural Ramsey-type question, generalizing some well-studied zero-sum problems in extremal combinatorics. The problem was recently introduced by Chaudhury, Garg, Mehlhorn, Mehta, and Misra [EC 2021], who proved that d ≤ R_f(d) ≤ d⁴+d and showed that the problem has close connections to EFX allocations, a central problem of fair allocation in social choice theory. In this paper we show the improved bound R_f(d) ≤ d^{2 + o(1)}, yielding an efficient (1-ε)-EFX allocation with n agents and O((n/ε)^{0.67}) unallocated goods; this improves the bound of O((n/ε)^{0.8}) of Chaudhury, Garg, Mehlhorn, Mehta, and Misra. {Additionally, we prove the stronger upper bound 2d-2, in the case where all edge-labels are permutations. A very special case of this problem, that of finding zero-sum cycles in digraphs whose edges are labeled with elements of ℤ_d, was recently considered by Alon and Krivelevich [JGT 2021] and by Mészáros and Steiner [EJC 2021]. Our result improves the bounds obtained by these authors and extends them to labelings with elements of an arbitrary (not necessarily commutative) group, while also simplifying the proof.}
Cite as

Benjamin Aram Berendsohn, Simona Boyadzhiyska, and László Kozma. Fixed-Point Cycles and Approximate EFX Allocations. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{berendsohn_et_al:LIPIcs.MFCS.2022.17,
  author =	{Berendsohn, Benjamin Aram and Boyadzhiyska, Simona and Kozma, L\'{a}szl\'{o}},
  title =	{{Fixed-Point Cycles and Approximate EFX Allocations}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{17:1--17:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.17},
  URN =		{urn:nbn:de:0030-drops-168153},
  doi =		{10.4230/LIPIcs.MFCS.2022.17},
  annote =	{Keywords: fixed-point, zero-sum cycle, Ramsey theory, fair allocation, EFX}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.14
The Diameter of Caterpillar Associahedra

Authors: Benjamin Aram Berendsohn

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
The caterpillar associahedron 𝒜(G) is a polytope arising from the rotation graph of search trees on a caterpillar tree G, generalizing the rotation graph of binary search trees (BSTs) and thus the conventional associahedron. We show that the diameter of 𝒜(G) is Θ(n + m ⋅ (H+1)), where n is the number of vertices, m is the number of leaves, and H is the entropy of the leaf distribution of G. Our proofs reveal a strong connection between caterpillar associahedra and searching in BSTs. We prove the lower bound using Wilber’s first lower bound for dynamic BSTs, and the upper bound by reducing the problem to searching in static BSTs.
Cite as

Benjamin Aram Berendsohn. The Diameter of Caterpillar Associahedra. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{berendsohn:LIPIcs.SWAT.2022.14,
  author =	{Berendsohn, Benjamin Aram},
  title =	{{The Diameter of Caterpillar Associahedra}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{14:1--14:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.14},
  URN =		{urn:nbn:de:0030-drops-161743},
  doi =		{10.4230/LIPIcs.SWAT.2022.14},
  annote =	{Keywords: Graph Associahedra, Binary Search Trees, Elimination Trees}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2019.1
Finding and Counting Permutations via CSPs

Authors: Benjamin Aram Berendsohn, László Kozma, and Dániel Marx

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
Permutation patterns and pattern avoidance have been intensively studied in combinatorics and computer science, going back at least to the seminal work of Knuth on stack-sorting (1968). Perhaps the most natural algorithmic question in this area is deciding whether a given permutation of length n contains a given pattern of length k. In this work we give two new algorithms for this well-studied problem, one whose running time is n^{k/4 + o(k)}, and a polynomial-space algorithm whose running time is the better of O(1.6181^n) and O(n^{k/2 + 1}). These results improve the earlier best bounds of n^{0.47k + o(k)} and O(1.79^n) due to Ahal and Rabinovich (2000) resp. Bruner and Lackner (2012) and are the fastest algorithms for the problem when k in Omega(log{n}). We show that both our new algorithms and the previous exponential-time algorithms in the literature can be viewed through the unifying lens of constraint-satisfaction. Our algorithms can also count, within the same running time, the number of occurrences of a pattern. We show that this result is close to optimal: solving the counting problem in time f(k) * n^{o(k/log{k})} would contradict the exponential-time hypothesis (ETH). For some special classes of patterns we obtain improved running times. We further prove that 3-increasing and 3-decreasing permutations can, in some sense, embed arbitrary permutations of almost linear length, which indicates that an algorithm with sub-exponential running time is unlikely, even for patterns from these restricted classes.
Cite as

Benjamin Aram Berendsohn, László Kozma, and Dániel Marx. Finding and Counting Permutations via CSPs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{berendsohn_et_al:LIPIcs.IPEC.2019.1,
  author =	{Berendsohn, Benjamin Aram and Kozma, L\'{a}szl\'{o} and Marx, D\'{a}niel},
  title =	{{Finding and Counting Permutations via CSPs}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{1:1--1:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.1},
  URN =		{urn:nbn:de:0030-drops-114627},
  doi =		{10.4230/LIPIcs.IPEC.2019.1},
  annote =	{Keywords: permutations, pattern matching, constraint satisfaction, exponential time}
}
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