Search Results

Documents authored by Martinsson, Anders

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.30
On Connectivity in Random Graph Models with Limited Dependencies

Authors: Johannes Lengler, Anders Martinsson, Kalina Petrova, Patrick Schnider, Raphael Steiner, Simon Weber, and Emo Welzl

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

Abstract
For any positive edge density p, a random graph in the Erdős-Rényi G_{n,p} model is connected with non-zero probability, since all edges are mutually independent. We consider random graph models in which edges that do not share endpoints are independent while incident edges may be dependent and ask: what is the minimum probability ρ(n), such that for any distribution 𝒢 (in this model) on graphs with n vertices in which each potential edge has a marginal probability of being present at least ρ(n), a graph drawn from 𝒢 is connected with non-zero probability? As it turns out, the condition "edges that do not share endpoints are independent" needs to be clarified and the answer to the question above is sensitive to the specification. In fact, we formalize this intuitive description into a strict hierarchy of five independence conditions, which we show to have at least three different behaviors for the threshold ρ(n). For each condition, we provide upper and lower bounds for ρ(n). In the strongest condition, the coloring model (which includes, e.g., random geometric graphs), we show that ρ(n) → 2-ϕ ≈ 0.38 for n → ∞, proving a conjecture by Badakhshian, Falgas-Ravry, and Sharifzadeh. This separates the coloring models from the weaker independence conditions we consider, as there we prove that ρ(n) > 0.5-o(n). In stark contrast to the coloring model, for our weakest independence condition - pairwise independence of non-adjacent edges - we show that ρ(n) lies within O(1/n²) of the threshold 1-2/n for completely arbitrary distributions.
Cite as

Johannes Lengler, Anders Martinsson, Kalina Petrova, Patrick Schnider, Raphael Steiner, Simon Weber, and Emo Welzl. On Connectivity in Random Graph Models with Limited Dependencies. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 30:1-30:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lengler_et_al:LIPIcs.APPROX/RANDOM.2023.30,
  author =	{Lengler, Johannes and Martinsson, Anders and Petrova, Kalina and Schnider, Patrick and Steiner, Raphael and Weber, Simon and Welzl, Emo},
  title =	{{On Connectivity in Random Graph Models with Limited Dependencies}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{30:1--30:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.30},
  URN =		{urn:nbn:de:0030-drops-188556},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.30},
  annote =	{Keywords: Random Graphs, Independence, Dependency, Connectivity, Threshold, Probabilistic Method}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.17
An Optimal Decentralized (Δ + 1)-Coloring Algorithm

Authors: Daniel Bertschinger, Johannes Lengler, Anders Martinsson, Robert Meier, Angelika Steger, Miloš Trujić, and Emo Welzl

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
Consider the following simple coloring algorithm for a graph on n vertices. Each vertex chooses a color from {1, ..., Δ(G) + 1} uniformly at random. While there exists a conflicted vertex choose one such vertex uniformly at random and recolor it with a randomly chosen color. This algorithm was introduced by Bhartia et al. [MOBIHOC'16] for channel selection in WIFI-networks. We show that this algorithm always converges to a proper coloring in expected O(n log Δ) steps, which is optimal and proves a conjecture of Chakrabarty and de Supinski [SOSA'20].
Cite as

Daniel Bertschinger, Johannes Lengler, Anders Martinsson, Robert Meier, Angelika Steger, Miloš Trujić, and Emo Welzl. An Optimal Decentralized (Δ + 1)-Coloring Algorithm. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bertschinger_et_al:LIPIcs.ESA.2020.17,
  author =	{Bertschinger, Daniel and Lengler, Johannes and Martinsson, Anders and Meier, Robert and Steger, Angelika and Truji\'{c}, Milo\v{s} and Welzl, Emo},
  title =	{{An Optimal Decentralized (\Delta + 1)-Coloring Algorithm}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{17:1--17:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.17},
  URN =		{urn:nbn:de:0030-drops-128837},
  doi =		{10.4230/LIPIcs.ESA.2020.17},
  annote =	{Keywords: Decentralized Algorithm, Distributed Computing, Graph Coloring, Randomized Algorithms}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.144
Optimal Strategies for Patrolling Fences

Authors: Bernhard Haeupler, Fabian Kuhn, Anders Martinsson, Kalina Petrova, and Pascal Pfister

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
A classical multi-agent fence patrolling problem asks: What is the maximum length L of a line fence that k agents with maximum speeds v_1,..., v_k can patrol if each point on the line needs to be visited at least once every unit of time. It is easy to see that L = alpha sum_{i=1}^k v_i for some efficiency alpha in [1/2,1). After a series of works [Czyzowicz et al., 2011; Dumitrescu et al., 2014; Kawamura and Kobayashi, 2015; Kawamura and Soejima, 2015] giving better and better efficiencies, it was conjectured by Kawamura and Soejima [Kawamura and Soejima, 2015] that the best possible efficiency approaches 2/3. No upper bounds on the efficiency below 1 were known. We prove the first such upper bounds and tightly bound the optimal efficiency in terms of the minimum speed ratio s = {v_{max}}/{v_{min}} and the number of agents k. Our bounds of alpha <= 1/{1 + 1/s} and alpha <= 1 - 1/(sqrt{k)+1} imply that in order to achieve efficiency 1 - epsilon, at least k >= Omega(epsilon^{-2}) agents with a speed ratio of s >= Omega(epsilon^{-1}) are necessary. Guided by our upper bounds, we construct a scheme whose efficiency approaches 1, disproving the conjecture stated above. Our scheme asymptotically matches our upper bounds in terms of the maximal speed difference and the number of agents used. A variation of the fence patrolling problem considers a circular fence instead and asks for its circumference to be maximized. We consider the unidirectional case of this variation, where all agents are only allowed to move in one direction, say clockwise. At first, a strategy yielding L = max_{r in [k]} r * v_r where v_1 >= v_2 >= ... >= v_k was conjectured to be optimal by Czyzowicz et al. [Czyzowicz et al., 2011] This was proven not to be the case by giving constructions for only specific numbers of agents with marginal improvements of L. We give a general construction that yields L = 1/{33 log_e log_2(k)} sum_{i=1}^k v_i for any set of agents, which in particular for the case 1, 1/2, ..., 1/k diverges as k - > infty, thus resolving a conjecture by Kawamura and Soejima [Kawamura and Soejima, 2015] affirmatively.
Cite as

Bernhard Haeupler, Fabian Kuhn, Anders Martinsson, Kalina Petrova, and Pascal Pfister. Optimal Strategies for Patrolling Fences. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 144:1-144:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{haeupler_et_al:LIPIcs.ICALP.2019.144,
  author =	{Haeupler, Bernhard and Kuhn, Fabian and Martinsson, Anders and Petrova, Kalina and Pfister, Pascal},
  title =	{{Optimal Strategies for Patrolling Fences}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{144:1--144:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.144},
  URN =		{urn:nbn:de:0030-drops-107202},
  doi =		{10.4230/LIPIcs.ICALP.2019.144},
  annote =	{Keywords: multi-agent systems, patrolling algorithms}
}
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