We analyze the convergence of the k-opinion Undecided State Dynamics (USD) in the population protocol model. For k=2 opinions it is well known that the USD reaches consensus with high probability within O(n log n) interactions. Proving that the process also quickly solves the consensus problem for k > 2 opinions has remained open, despite analogous results for larger k in the related parallel gossip model. In this paper we prove such convergence: under mild assumptions on k and on the initial number of undecided agents we prove that the USD achieves plurality consensus within O(kn log n) interactions with high probability, regardless of the initial bias. Moreover, if there is an initial additive bias of at least Ω (√n log n) we prove that the initial plurality opinion wins with high probability, and if there is a multiplicative bias the convergence time is further improved. Note that this is the first result for k > 2 for the USD in the population protocol model. Furthermore, it is the first result for the unsynchronized variant of the USD with k > 2 which does not need any initial bias.

We consider the plurality consensus problem for population protocols. Here, n anonymous agents start each with one of k opinions. Their goal is to agree on the initially most frequent opinion (the plurality opinion) via random, pairwise interactions. Exact plurality consensus refers to the requirement that the plurality opinion must be identified even if the bias (difference between the most and second most frequent opinion) is only 1.

We consider the plurality consensus problem for n agents. Initially, each agent has one of k opinions. Agents choose random interaction partners and revise their state according to a fixed transition function, depending on their own state and the state of the interaction partners. The goal is to reach a configuration in which all agents agree on the same opinion. If there is initially a sufficiently large bias towards some opinions one of them should prevail. In this paper we consider a synchronized variant of the undecided state dynamics where the agents use so-called phase clocks. The phase clocks divide the time in overlapping phases. Each phase consists of a decision and a boosting part. In the decision part, any agent that encounters an agent with a different opinion becomes undecided. In the boosting part, undecided agents adopt the first opinion they encounter. We consider this dynamics both in the sequential population model and the parallel gossip model. In the population model agents interact in randomly chosen pairs, one pair per time step. The runtime is measured in parallel time (number of interactions divided by n). We show that our protocol reaches consensus (w.h.p.) in O(log2 n) parallel time, providing the first polylogarithmic result for k > 2 (w.h.p.) in this model. If there is an initial bias of , then (w.h.p.) that opinion wins. The gossip model assumes parallel rounds. During each round every agent is allowed to communicate with one randomly chosen agent. Here it is known that consensus can be reached fast (in polylogarithmic time) if there is a bias of order towards one opinion [Ghaffari and Parter, PODC'16; Berenbrink et al., ICALP'16]. Without any assumption on the bias, fast consensus has only been shown for k = 2 for the unsynchronized version of the undecided state dynamics [Clementi et al., MFCS'18]. To account for the yet unsolved general case, we show that the synchronized variant of the undecided state dynamics reaches consensus (w.h.p.) in time O(log2 n) for every initial configuration. Again, we guarantee that if there is an initial bias of , then (w.h.p.) that opinion wins. A simple extension of our protocol in the gossip model yields a dynamics that does not depend on n or k, is anonymous, and has (w.h.p.) runtime O(log2 n). This solves an open problem formulated by Becchetti et al. [Distributed Computing, 2017].

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.