7 Search Results for "Janson, Svante"

Document
DOI: 10.4230/LIPIcs.AofA.2022.4
A Modification of the Random Cutting Model

Authors: Fabian Burghart

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)

Abstract
We propose a modification to the random destruction of graphs: Given a finite network with a distinguished set of sources and targets, remove (cut) vertices at random, discarding components that do not contain a source node. We investigate the number of cuts required until all targets are removed, and the size of the remaining graph. This model interpolates between the random cutting model going back to Meir and Moon [Meir and Moon, 1970] and site percolation. We prove several general results, including that the size of the remaining graph is a tight family of random variables for compatible sequences of expander-type graphs, and determine limiting distributions complete binary trees.
Cite as

Fabian Burghart. A Modification of the Random Cutting Model. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{burghart:LIPIcs.AofA.2022.4,
  author =	{Burghart, Fabian},
  title =	{{A Modification of the Random Cutting Model}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.4},
  URN =		{urn:nbn:de:0030-drops-160903},
  doi =		{10.4230/LIPIcs.AofA.2022.4},
  annote =	{Keywords: Random cutting model, Random separation of graphs, Percolation}
}
Document
DOI: 10.4230/LIPIcs.AofA.2022.11
Depth-First Search Performance in a Random Digraph with Geometric Degree Distribution

Authors: Philippe Jacquet and Svante Janson

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)

Abstract
We present an analysis of the depth-first search algorithm in a random digraph model with geometric outdegree distribution. We give also some extensions to general outdegree distributions. This problem posed by Donald Knuth in his next to appear volume of The Art of Computer Programming gives interesting insight in one of the most elegant and efficient algorithm for graph analysis due to Tarjan.
Cite as

Philippe Jacquet and Svante Janson. Depth-First Search Performance in a Random Digraph with Geometric Degree Distribution. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{jacquet_et_al:LIPIcs.AofA.2022.11,
  author =	{Jacquet, Philippe and Janson, Svante},
  title =	{{Depth-First Search Performance in a Random Digraph with Geometric Degree Distribution}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.11},
  URN =		{urn:nbn:de:0030-drops-160978},
  doi =		{10.4230/LIPIcs.AofA.2022.11},
  annote =	{Keywords: Combinatorics, Depth-First Search, Random Digraphs}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.17
Hidden Words Statistics for Large Patterns

Authors: Svante Janson and Wojciech Szpankowski

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Abstract
We study here the so called subsequence pattern matching also known as hidden pattern matching in which one searches for a given pattern w of length m as a subsequence in a random text of length n. The quantity of interest is the number of occurrences of w as a subsequence (i.e., occurring in not necessarily consecutive text locations). This problem finds many applications from intrusion detection, to trace reconstruction, to deletion channel, and to DNA-based storage systems. In all of these applications, the pattern w is of variable length. To the best of our knowledge this problem was only tackled for a fixed length m=O(1) [P. Flajolet et al., 2006]. In our main result Theorem 5 we prove that for m=o(n^{1/3}) the number of subsequence occurrences is normally distributed. In addition, in Theorem 6 we show that under some constraints on the structure of w the asymptotic normality can be extended to m=o(√n). For a special pattern w consisting of the same symbol, we indicate that for m=o(n) the distribution of number of subsequences is either asymptotically normal or asymptotically log normal. We conjecture that this dichotomy is true for all patterns. We use Hoeffding’s projection method for U-statistics to prove our findings.
Cite as

Svante Janson and Wojciech Szpankowski. Hidden Words Statistics for Large Patterns. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{janson_et_al:LIPIcs.AofA.2020.17,
  author =	{Janson, Svante and Szpankowski, Wojciech},
  title =	{{Hidden Words Statistics for Large Patterns}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.17},
  URN =		{urn:nbn:de:0030-drops-120476},
  doi =		{10.4230/LIPIcs.AofA.2020.17},
  annote =	{Keywords: Hidden pattern matching, subsequences, probability, U-statistics, projection method}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.60
Successive Minimum Spanning Trees

Authors: Svante Janson and Gregory B. Sorkin

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
In a complete graph K_n with edge weights drawn independently from a uniform distribution U(0,1) (or alternatively an exponential distribution Exp(1)), let T_1 be the MST (the spanning tree of minimum weight) and let T_k be the MST after deletion of the edges of all previous trees T_i, i<k. We show that each tree’s weight w(T_k) converges in probability to a constant gamma_k with 2k-2 sqrt k < gamma_k < 2k+2 sqrt k, and we conjecture that gamma_k = 2k-1+o(1). The problem is distinct from that of [Alan Frieze and Tony Johansson, 2018], finding k MSTs of combined minimum weight, and the combined cost for two trees in their problem is, asymptotically, strictly smaller than our gamma_1+gamma_2. Our results also hold (and mostly are derived) in a multigraph model where edge weights for each vertex pair follow a Poisson process; here we additionally have E(w(T_k)) -> gamma_k. Thinking of an edge of weight w as arriving at time t=n w, Kruskal’s algorithm defines forests F_k(t), each initially empty and eventually equal to T_k, with each arriving edge added to the first F_k(t) where it does not create a cycle. Using tools of inhomogeneous random graphs we obtain structural results including that C_1(F_k(t))/n, the fraction of vertices in the largest component of F_k(t), converges in probability to a function rho_k(t), uniformly for all t, and that a giant component appears in F_k(t) at a time t=sigma_k. We conjecture that the functions rho_k tend to time translations of a single function, rho_k(2k+x) -> rho_infty(x) as k -> infty, uniformly in x in R. Simulations and numerical computations give estimated values of gamma_k for small k, and support the conjectures stated above.
Cite as

Svante Janson and Gregory B. Sorkin. Successive Minimum Spanning Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 60:1-60:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{janson_et_al:LIPIcs.APPROX-RANDOM.2019.60,
  author =	{Janson, Svante and Sorkin, Gregory B.},
  title =	{{Successive Minimum Spanning Trees}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{60:1--60:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.60},
  URN =		{urn:nbn:de:0030-drops-112759},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.60},
  annote =	{Keywords: miminum spanning tree, second-cheapest structure, inhomogeneous random graph, optimization in random structures, discrete probability, multi-type branching process, functional fixed point, robust optimization, Kruskal’s algorithm}
}
Document
Keynote Speakers
DOI: 10.4230/LIPIcs.AofA.2018.6
Patterns in Random Permutations Avoiding Some Other Patterns (Keynote Speakers)

Authors: Svante Janson

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
Consider a random permutation drawn from the set of permutations of length n that avoid a given set of one or several patterns of length 3. We show that the number of occurrences of another pattern has a limit distribution, after suitable scaling. In several cases, the limit is normal, as it is in the case of unrestricted random permutations; in other cases the limit is a non-normal distribution, depending on the studied pattern. In the case when a single pattern of length 3 is forbidden, the limit distributions can be expressed in terms of a Brownian excursion. The analysis is made case by case; unfortunately, no general method is known, and no general pattern emerges from the results.
Cite as

Svante Janson. Patterns in Random Permutations Avoiding Some Other Patterns (Keynote Speakers). In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{janson:LIPIcs.AofA.2018.6,
  author =	{Janson, Svante},
  title =	{{Patterns in Random Permutations Avoiding Some Other Patterns}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{6:1--6:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.6},
  URN =		{urn:nbn:de:0030-drops-88996},
  doi =		{10.4230/LIPIcs.AofA.2018.6},
  annote =	{Keywords: Random permutations, patterns, forbidden patterns, limit in distribution, U-statistics}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.15
Inversions in Split Trees and Conditional Galton-Watson Trees

Authors: Xing Shi Cai, Cecilia Holmgren, Svante Janson, Tony Johansson, and Fiona Skerman

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
We study I(T), the number of inversions in a tree T with its vertices labeled uniformly at random. We first show that the cumulants of I(T) have explicit formulas. Then we consider X_n, the normalized version of I(T_n), for a sequence of trees T_n. For fixed T_n's, we prove a sufficient condition for X_n to converge in distribution. For T_n being split trees [Devroye, 1999], we show that X_n converges to the unique solution of a distributional equation. Finally, when T_n's are conditional Galton-Watson trees, we show that X_n converges to a random variable defined in terms of Brownian excursions. Our results generalize and extend previous work by Panholzer and Seitz [Panholzer and Seitz, 2012].
Cite as

Xing Shi Cai, Cecilia Holmgren, Svante Janson, Tony Johansson, and Fiona Skerman. Inversions in Split Trees and Conditional Galton-Watson Trees. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 15:1-15:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.AofA.2018.15,
  author =	{Cai, Xing Shi and Holmgren, Cecilia and Janson, Svante and Johansson, Tony and Skerman, Fiona},
  title =	{{Inversions in Split Trees and Conditional Galton-Watson Trees}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{15:1--15:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.15},
  URN =		{urn:nbn:de:0030-drops-89085},
  doi =		{10.4230/LIPIcs.AofA.2018.15},
  annote =	{Keywords: inversions, random trees, split trees, Galton-Watson trees, permutation, cumulant}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.21
On the Tails of the Limiting QuickSort Density

Authors: James Allen Fill and Wei-Chun Hung

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
We give upper and lower asymptotic bounds for the left tail and for the right tail of the continuous limiting QuickSort density f that are nearly matching in each tail. The bounds strengthen results from a paper of Svante Janson (2015) concerning the corresponding distribution function F. Furthermore, we obtain similar upper bounds on absolute values of derivatives of f of each order.
Cite as

James Allen Fill and Wei-Chun Hung. On the Tails of the Limiting QuickSort Density. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 21:1-21:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fill_et_al:LIPIcs.AofA.2018.21,
  author =	{Fill, James Allen and Hung, Wei-Chun},
  title =	{{On the Tails of the Limiting QuickSort Density}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{21:1--21:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.21},
  URN =		{urn:nbn:de:0030-drops-89144},
  doi =		{10.4230/LIPIcs.AofA.2018.21},
  annote =	{Keywords: Quicksort, density tails, asymptotic bounds, Landau-Kolmogorov inequality}
}
  • Refine by Author
  • 5 Janson, Svante
  • 1 Burghart, Fabian
  • 1 Cai, Xing Shi
  • 1 Fill, James Allen
  • 1 Holmgren, Cecilia
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Probabilistic algorithms
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Mathematics of computing → Distribution functions
  • 1 Mathematics of computing → Matroids and greedoids
  • 1 Mathematics of computing → Paths and connectivity problems
  • Show More...

  • Refine by Keyword
  • 2 U-statistics
  • 1 Combinatorics
  • 1 Depth-First Search
  • 1 Galton-Watson trees
  • 1 Hidden pattern matching
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 3 2018
  • 2 2022
  • 1 2019
  • 1 2020

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