DROPS

Document

DOI: 10.4230/LIPIcs.SAND.2022.7

Loosely-Stabilizing Phase Clocks and The Adaptive Majority Problem

Authors: Petra Berenbrink, Felix Biermeier, Christopher Hahn, and Dominik Kaaser

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract

We present a loosely-stabilizing phase clock for population protocols. In the population model we are given a system of n identical agents which interact in a sequence of randomly chosen pairs. Our phase clock is leaderless and it requires O(log n) states. It runs forever and is, at any point of time, in a synchronous state w.h.p. When started in an arbitrary configuration, it recovers rapidly and enters a synchronous configuration within O(n log n) interactions w.h.p. Once the clock is synchronized, it stays in a synchronous configuration for at least poly(n) parallel time w.h.p. We use our clock to design a loosely-stabilizing protocol that solves the adaptive variant of the majority problem. We assume that the agents have either opinion A or B or they are undecided and agents can change their opinion at a rate of 1/n. The goal is to keep track which of the two opinions is (momentarily) the majority. We show that if the majority has a support of at least Ω(log n) agents and a sufficiently large bias is present, then the protocol converges to a correct output within O(n log n) interactions and stays in a correct configuration for poly(n) interactions, w.h.p.

Cite as

Petra Berenbrink, Felix Biermeier, Christopher Hahn, and Dominik Kaaser. Loosely-Stabilizing Phase Clocks and The Adaptive Majority Problem. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{berenbrink_et_al:LIPIcs.SAND.2022.7,
  author =	{Berenbrink, Petra and Biermeier, Felix and Hahn, Christopher and Kaaser, Dominik},
  title =	{{Loosely-Stabilizing Phase Clocks and The Adaptive Majority Problem}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.7},
  URN =		{urn:nbn:de:0030-drops-159493},
  doi =		{10.4230/LIPIcs.SAND.2022.7},
  annote =	{Keywords: Population Protocols, Phase Clocks, Loose Self-stabilization, Clock Synchronization, Majority, Adaptive}
}

Document

DOI: 10.4230/LIPIcs.ESA.2019.8

On the Complexity of Anchored Rectangle Packing

Authors: Antonios Antoniadis, Felix Biermeier, Andrés Cristi, Christoph Damerius, Ruben Hoeksma, Dominik Kaaser, Peter Kling, and Lukas Nölke

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract

In the Anchored Rectangle Packing (ARP) problem, we are given a set of points P in the unit square [0,1]^2 and seek a maximum-area set of axis-aligned interior-disjoint rectangles S, each of which is anchored at a point p in P. In the most prominent variant - Lower-Left-Anchored Rectangle Packing (LLARP) - rectangles are anchored in their lower-left corner. Freedman [W. T. Tutte (Ed.), 1969] conjectured in 1969 that, if (0,0) in P, then there is a LLARP that covers an area of at least 0.5. Somewhat surprisingly, this conjecture remains open to this day, with the best known result covering an area of 0.091 [Dumitrescu and Tóth, 2015]. Maybe even more surprisingly, it is not known whether LLARP - or any ARP-problem with only one anchor - is NP-hard. In this work, we first study the Center-Anchored Rectangle Packing (CARP) problem, where rectangles are anchored in their center. We prove NP-hardness and provide a PTAS. In fact, our PTAS applies to any ARP problem where the anchor lies in the interior of the rectangles. Afterwards, we turn to the LLARP problem and investigate two different resource-augmentation settings: In the first we allow an epsilon-perturbation of the input P, whereas in the second we permit an epsilon-overlap between rectangles. For the former setting, we give an algorithm that covers at least as much area as an optimal solution of the original problem. For the latter, we give an (1 - epsilon)-approximation.

Cite as

Antonios Antoniadis, Felix Biermeier, Andrés Cristi, Christoph Damerius, Ruben Hoeksma, Dominik Kaaser, Peter Kling, and Lukas Nölke. On the Complexity of Anchored Rectangle Packing. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{antoniadis_et_al:LIPIcs.ESA.2019.8,
  author =	{Antoniadis, Antonios and Biermeier, Felix and Cristi, Andr\'{e}s and Damerius, Christoph and Hoeksma, Ruben and Kaaser, Dominik and Kling, Peter and N\"{o}lke, Lukas},
  title =	{{On the Complexity of Anchored Rectangle Packing}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.8},
  URN =		{urn:nbn:de:0030-drops-111297},
  doi =		{10.4230/LIPIcs.ESA.2019.8},
  annote =	{Keywords: anchored rectangle, rectangle packing, resource augmentation, PTAS, NP, hardness}
}

Search Results

Documents authored by Biermeier, Felix

Loosely-Stabilizing Phase Clocks and The Adaptive Majority Problem

Abstract

Cite as

On the Complexity of Anchored Rectangle Packing

Abstract

Cite as

Thanks for your feedback!

Could not send message