4 Search Results for "Knudsen, Mathias B�k Tejs"

Document
DOI: 10.4230/LIPIcs.ICALP.2018.5
Power of d Choices with Simple Tabulation

Authors: Anders Aamand, Mathias Bæk Tejs Knudsen, and Mikkel Thorup

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We consider the classic d-choice paradigm of Azar et al. [STOC'94] in which m balls are put into n bins sequentially as follows: For each ball we are given a choice of d bins chosen according to d hash functions and the ball is placed in the least loaded of these bins, breaking ties arbitrarily. The interest is in the number of balls in the fullest bin after all balls have been placed. In this paper we suppose that the d hash functions are simple tabulation hash functions which are easy to implement and can be evaluated in constant time. Generalising a result by Dahlgaard et al. [SODA'16] we show that for an arbitrary constant d >= 2 the expected maximum load is at most (lg lg n)/(lg d) + O(1). We further show that by using a simple tie-breaking algorithm introduced by Vöcking [J.ACM'03] the expected maximum load is reduced to (lg lg n)/(d lg phi_d) + O(1) where phi_d is the rate of growth of the d-ary Fibonacci numbers. Both of these expected bounds match those known from the fully random setting. The analysis by Dahlgaard et al. relies on a proof by Patrascu and Thorup [J.ACM'11] concerning the use of simple tabulation for cuckoo hashing. We require a generalisation to d>2 hash functions, but the original proof is an 8-page tour de force of ad-hoc arguments that do not appear to generalise. Our main technical contribution is a shorter, simpler and more accessible proof of the result by Patrascu and Thorup, where the relevant parts generalise nicely to the analysis of d choices.
Cite as

Anders Aamand, Mathias Bæk Tejs Knudsen, and Mikkel Thorup. Power of d Choices with Simple Tabulation. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{aamand_et_al:LIPIcs.ICALP.2018.5,
  author =	{Aamand, Anders and B{\ae}k Tejs Knudsen, Mathias and Thorup, Mikkel},
  title =	{{Power of d Choices with Simple Tabulation}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.5},
  URN =		{urn:nbn:de:0030-drops-90096},
  doi =		{10.4230/LIPIcs.ICALP.2018.5},
  annote =	{Keywords: Hashing, Load Balancing, Balls and Bins, Simple Tabulation}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.64
Additive Spanners and Distance Oracles in Quadratic Time

Authors: Mathias Bæk Tejs Knudsen

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
Let G be an unweighted, undirected graph. An additive k-spanner of G is a subgraph H that approximates all distances between pairs of nodes up to an additive error of +k, that is, it satisfies d_H(u,v) <= d_G(u,v)+k for all nodes u,v, where d is the shortest path distance. We give a deterministic algorithm that constructs an additive O(1)-spanner with O(n^(4/3)) edges in O(n^2) time. This should be compared with the randomized Monte Carlo algorithm by Woodruff [ICALP 2010] giving an additive 6-spanner with O(n^(4/3)log^3 n) edges in expected time O(n^2 log^2 n). An (alpha,beta)-approximate distance oracle for G is a data structure that supports the following distance queries between pairs of nodes in G. Given two nodes u, v it can in constant time compute a distance estimate d' that satisfies d <= d' <= alpha d + beta where d is the distance between u and v in G. Sommer [ICALP 2016] gave a randomized Monte Carlo (2,1)-distance oracle of size O(n^(5/3) polylog n) in expected time O(n^2 polylog n). As an application of the additive O(1)-spanner we improve the construction by Sommer [ICALP 2016] and give a Las Vegas (2,1)-distance oracle of size O(n^(5/3)) in time O(n^2). This also implies an algorithm that in O(n^2) time gives approximate distance for all pairs of nodes in G improving on the O(n^2 log n) algorithm by Baswana and Kavitha [SICOMP 2010].
Cite as

Mathias Bæk Tejs Knudsen. Additive Spanners and Distance Oracles in Quadratic Time. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 64:1-64:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{knudsen:LIPIcs.ICALP.2017.64,
  author =	{Knudsen, Mathias B{\ae}k Tejs},
  title =	{{Additive Spanners and Distance Oracles in Quadratic Time}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{64:1--64:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.64},
  URN =		{urn:nbn:de:0030-drops-73924},
  doi =		{10.4230/LIPIcs.ICALP.2017.64},
  annote =	{Keywords: graph algorithms, data structures, additive spanners, distance oracles}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.128
Near-Optimal Induced Universal Graphs for Bounded Degree Graphs

Authors: Mikkel Abrahamsen, Stephen Alstrup, Jacob Holm, Mathias Bæk Tejs Knudsen, and Morten Stöckel

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
A graph U is an induced universal graph for a family F of graphs if every graph in F is a vertex-induced subgraph of U. We give upper and lower bounds for the size of induced universal graphs for the family of graphs with n vertices of maximum degree D. Our new bounds improve several previous results except for the special cases where D is either near-constant or almost n/2. For constant even D Butler [Graphs and Combinatorics 2009] has shown O(n^(D/2)) and recently Alon and Nenadov [SODA 2017] showed the same bound for constant odd D. For constant D Butler also gave a matching lower bound. For generals graphs, which corresponds to D = n, Alon [Geometric and Functional Analysis, to appear] proved the existence of an induced universal graph with (1+o(1)) \cdot 2^((n-1)/2) vertices, leading to a smaller constant than in the previously best known bound of 16 * 2^(n/2) by Alstrup, Kaplan, Thorup, and Zwick [STOC 2015]. In this paper we give the following lower and upper bound of binom(floor(n/2))(floor(D/2)) * n^(-O(1)) and binom(floor(n/2))(floor(D/2)) * 2^(O(sqrt(D log D) * log(n/D))), respectively, where the upper bound is the main contribution. The proof that it is an induced universal graph relies on a randomized argument. We also give a deterministic upper bound of O(n^k / (k-1)!). These upper bounds are the best known when D <= n/2 - tilde-Omega(n^(3/4)) and either D is even and D = omega(1) or D is odd and D = omega(log n/log log n). In this range we improve asymptotically on the previous best known results by Butler [Graphs and Combinatorics 2009], Esperet, Arnaud and Ochem [IPL 2008], Adjiashvili and Rotbart [ICALP 2014], Alon and Nenadov [SODA 2017], and Alon [Geometric and Functional Analysis, to appear].
Cite as

Mikkel Abrahamsen, Stephen Alstrup, Jacob Holm, Mathias Bæk Tejs Knudsen, and Morten Stöckel. Near-Optimal Induced Universal Graphs for Bounded Degree Graphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 128:1-128:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.ICALP.2017.128,
  author =	{Abrahamsen, Mikkel and Alstrup, Stephen and Holm, Jacob and Knudsen, Mathias B{\ae}k Tejs and St\"{o}ckel, Morten},
  title =	{{Near-Optimal Induced Universal Graphs for Bounded Degree Graphs}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{128:1--128:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.128},
  URN =		{urn:nbn:de:0030-drops-74114},
  doi =		{10.4230/LIPIcs.ICALP.2017.128},
  annote =	{Keywords: Adjacency labeling schemes, Bounded degree graphs, Induced universal graphs, Distributed computing}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.5
Sublinear Distance Labeling

Authors: Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Ely Porat

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
A distance labeling scheme labels the n nodes of a graph with binary strings such that, given the labels of any two nodes, one can determine the distance in the graph between the two nodes by looking only at the labels. A D-preserving distance labeling scheme only returns precise distances between pairs of nodes that are at distance at least D from each other. In this paper we consider distance labeling schemes for the classical case of unweighted and undirected graphs. We present a O(n/D * log^2(D)) bit D-preserving distance labeling scheme, improving the previous bound by Bollobás et al. [SIAM J. Discrete Math. 2005]. We also give an almost matching lower bound of Omega(n/D). With our D-preserving distance labeling scheme as a building block, we additionally achieve the following results: 1. We present the first distance labeling scheme of size o(n) for sparse graphs (and hence bounded degree graphs). This addresses an open problem by Gavoille et. al. [J. Algo. 2004], hereby separating the complexity from distance labeling in general graphs which require Omega(n) bits, Moon [Proc. of Glasgow Math. Association 1965]. 2. For approximate r-additive labeling schemes, that return distances within an additive error of r we show a scheme of size O(n/r * polylog(r*log(n))/log(n)) for r >= 2. This improves on the current best bound of O(n/r) by Alstrup et al. [SODA 2016] for sub-polynomial r, and is a generalization of a result by Gawrychowski et al. [arXiv preprint 2015] who showed this for r=2.
Cite as

Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Ely Porat. Sublinear Distance Labeling. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{alstrup_et_al:LIPIcs.ESA.2016.5,
  author =	{Alstrup, Stephen and Dahlgaard, S{\o}ren and Knudsen, Mathias B{\ae}k Tejs and Porat, Ely},
  title =	{{Sublinear Distance Labeling}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{5:1--5:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.5},
  URN =		{urn:nbn:de:0030-drops-63479},
  doi =		{10.4230/LIPIcs.ESA.2016.5},
  annote =	{Keywords: Graph labeling schemes, Distance labeling, Graph theory, Sparse graphs}
}
  • Refine by Author
  • 3 Knudsen, Mathias Bæk Tejs
  • 2 Alstrup, Stephen
  • 1 Aamand, Anders
  • 1 Abrahamsen, Mikkel
  • 1 Bæk Tejs Knudsen, Mathias
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Mathematics of computing → Random graphs
  • 1 Theory of computation → Bloom filters and hashing
  • 1 Theory of computation → Data structures design and analysis
  • 1 Theory of computation → Online algorithms
  • Show More...

  • Refine by Keyword
  • 1 Adjacency labeling schemes
  • 1 Balls and Bins
  • 1 Bounded degree graphs
  • 1 Distance labeling
  • 1 Distributed computing
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2017
  • 1 2016
  • 1 2018

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