Search Results

Documents authored by Pfister, Pascal

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.58
The Maximum Label Propagation Algorithm on Sparse Random Graphs

Authors: Charlotte Knierim, Johannes Lengler, Pascal Pfister, Ulysse Schaller, and Angelika Steger

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

Abstract
In the Maximum Label Propagation Algorithm (Max-LPA), each vertex draws a distinct random label. In each subsequent round, each vertex updates its label to the label that is most frequent among its neighbours (including its own label), breaking ties towards the larger label. It is known that this algorithm can detect communities in random graphs with planted communities if the graphs are very dense, by converging to a different consensus for each community. In [Kothapalli et al., 2013] it was also conjectured that the same result still holds for sparse graphs if the degrees are at least C log n. We disprove this conjecture by showing that even for degrees n^epsilon, for some epsilon>0, the algorithm converges without reaching consensus. In fact, we show that the algorithm does not even reach almost consensus, but converges prematurely resulting in orders of magnitude more communities.
Cite as

Charlotte Knierim, Johannes Lengler, Pascal Pfister, Ulysse Schaller, and Angelika Steger. The Maximum Label Propagation Algorithm on Sparse Random Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{knierim_et_al:LIPIcs.APPROX-RANDOM.2019.58,
  author =	{Knierim, Charlotte and Lengler, Johannes and Pfister, Pascal and Schaller, Ulysse and Steger, Angelika},
  title =	{{The Maximum Label Propagation Algorithm on Sparse Random Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{58:1--58:15},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.58},
  URN =		{urn:nbn:de:0030-drops-112731},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.58},
  annote =	{Keywords: random graphs, distributed algorithms, label propagation algorithms, consensus, community detection}
}
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