Algorithmica

Journal: Algorithmica

Abbreviation

Algorithmica

Publisher

Springer

ISSN

0178-4617
1432-0541

Show all metadata

Search Results

Publications 1 - 10 of 67

The (1+1) Elitist Black-Box Complexity of LeadingOnes
Doerr, Carola; Lengler, Johannes (2018)
Algorithmica
Dynamic Graph Coloring
Barba, Luis; Cardinal, Jean; Korman, Matias; et al. (2019)
Algorithmica
In this paper we study the number of vertex recolorings that an algorithm needs to perform in order to maintain a proper coloring of a graph under insertion and deletion of vertices and edges. We present two algorithms that achieve different trade-offs between the number of recolorings and the number of colors used. For any d>0, the first algorithm maintains a proper O(CdN1/d)-coloring while recoloring at most O(d) vertices per update, where C and N are the maximum chromatic number and maximum number of vertices, respectively. The second algorithm reverses the trade-off, maintaining an O(Cd)-coloring with O(dN1/d) recolorings per update. The two converge when d=logN, maintaining an O(ClogN)-coloring with O(logN) recolorings per update. We also present a lower bound, showing that any algorithm that maintains a c-coloring of a 2-colorable graph on N vertices must recolor at least Ω(N2c(c−1)) vertices per update, for any constant c≥2.
Sorting by Swaps with Noisy Comparisons
Gavenčiak, Tomáš; Geissmann, Barbara; Lengler, Johannes (2019)
Algorithmica
We study sorting of permutations by random swaps if each comparison gives the wrong result with some fixed probability p < 1/2. We use this process as prototype for the behaviour of randomized, comparison-based optimization heuristics in the presence of noisy comparisons. As quality measure, we compute the expected fitness of the stationary distribution. To measure the runtime, we compute the minimal number of steps after which the average fitness approximates the expected fitness of the stationary distribution. We study the process where in each round a random pair of elements at distance at most r are compared. We give theoretical results for the extreme cases r = 1 and r = n, and experimental results for the intermediate cases. We find a trade-off between faster convergence (for large r) and better quality of the solution after convergence (for small r).
OneMax in Black-Box Models with Several Restrictions
Doerr, Carola; Lengler, Johannes (2017)
Algorithmica
Pure Nash Equilibria in Graphical Games and Treewidth
Thomas, Antonis; van Leeuwen, Jan (2015)
Algorithmica
We treat PNE-GG, the problem of deciding the existence of a Pure Nash Equilibrium in a graphical game, and the role of treewidth in this problem. PNE-GG is known to be 𝑁𝑃-complete in general, but polynomially solvable for graphical games of bounded treewidth. We prove that PNE-GG is 𝑊[1]-Hard when parameterized by treewidth. On the other hand, we give a dynamic programming approach that solves the problem in 𝑂∗(𝛼𝑤) time, where 𝛼 is the cardinality of the largest strategy set and 𝑤 is the treewidth of the input graph (and 𝑂∗ hides polynomial factors). This proves that PNE-GG is in 𝐹𝑃𝑇 for the combined parameter (𝛼,𝑤). Moreover, we prove that there is no algorithm that solves PNE-GG in 𝑂∗((𝛼−𝜖)𝑤) time for any 𝜖>0, unless the Strong Exponential Time Hypothesis fails. Our lower bounds implicitly assume that 𝛼≥3; we show that for 𝛼=2 the problem can be solved in polynomial time. Finally, we discuss the implication for computing pure Nash equilibria in graphical games (PNE-GG) of 𝑂(log𝑛) treewidth, the existence of polynomial kernels for PNE-GG parameterized by treewidth, and the construction of a sample and maximum-payoff pure Nash equilibrium.
Nearly linear time minimum spanning tree maintenance for transient node failures
Nardelli, Enrico; Proietti, Guido; Widmayer, Peter (2004)
Algorithmica
Given a 2-node connected, real weighted, and undirected graph $G=(V,E)$, with $n$ nodes and $m$ edges, and given a minimum spanning tree (MST) $T=(V,E_T)$ of $G$, we study the problem of finding, for every node $v \in V$, a set of replacement edges which can be used for constructing an MST of $G-v$ (i.e., the graph $G$ deprived of $v$ and all its incident edges). We show that this problem can be solved on a pointer machine in ${\cal O}(m \cdot \alpha(m,n))$ time and ${\cal O}(m)$ space, where $\alpha$ is the functional inverse of Ackermann’s function. Our solution improves over the previously best known ${\cal O}(\min\{m \cdot \alpha(n,n), m + n \log n\})$ time bound, and allows us to close the gap existing with the fastest solution for the edge-removal version of the problem (i.e., that of finding, for every edge $e \in E_T$, a replacement edge which can be used for constructing an MST of $G-e=(V,E \backslash \{e\})$). Our algorithm finds immediate application in maintaining MST-based communication networks undergoing temporary node failures. Moreover, in a distributed environment in which nodes are managed by selfish agents, it can be used to design an efficient, truthful mechanism for building an MST.
Topological Implications of Selfish Neighbor Selection in Unstructured Peer-to-Peer Networks
Moscibroda, Thomas; Schmid, Stefan; Wattenhofer, Roger (2011)
Algorithmica
Conflict-free chromatic art gallery coverage
Bärtschi, Andreas; Suri, Subhash (2014)
Algorithmica
We consider a chromatic variant of the art gallery problem, where each guard is assigned one of k distinct colors. A placement of such colored guards is conflict-free if each point of the polygon is seen by some guard whose color appears exactly once among the guards visible to that point. What is the smallest number k(n) of colors that ensure a conflict-free covering of all n-vertex polygons? We call this the conflict-free chromatic art gallery problem. Our main result shows that k(n) is O(logn) for orthogonal and for monotone polygons, and O(log2 n) for arbitrary simple polygons. By contrast, if all guards visible from each point must have distinct colors, then k(n) is Ω(n) for arbitrary simple polygons, as shown by Erickson and LaValle (Robotics: Science and Systems, vol. VII, pp. 81–88, 2012). The problem is motivated by applications in distributed robotics and wireless sensor networks but is also of interest from a theoretical point of view.
Ham-Sandwich Cuts for Abstract Order Types
Felsner, Stefan; Pilz, Alexander (2018)
Algorithmica
The linear-time ham-sandwich cut algorithm of Lo, Matoušek, and Steiger for bi-chromatic finite point sets in the plane works by appropriately selecting crossings of the lines in the dual line arrangement with a set of well-chosen vertical lines. We consider the setting where we are not given the coordinates of the point set, but only the orientation of each point triple (the order type) and give a deterministic linear-time algorithm for the mentioned sub-algorithm. This yields a linear-time ham-sandwich cut algorithm even in our restricted setting. We also show that our methods are applicable to abstract order types.
Analysing Equilibrium States for Population Diversity
Lengler, Johannes; Opris, Andre; Sudholt, Dirk (2024)
Algorithmica
Population diversity is crucial in evolutionary algorithms as it helps with global exploration and facilitates the use of crossover. Despite many runtime analyses showing advantages of population diversity, we have no clear picture of how diversity evolves over time. We study how the population diversity of (μ+1) algorithms, measured by the sum of pairwise Hamming distances, evolves in a fitness-neutral environment. We give an exact formula for the drift of population diversity and show that it is driven towards an equilibrium state. Moreover, we bound the expected time for getting close to the equilibrium state. We find that these dynamics, including the location of the equilibrium, are unaffected by surprisingly many algorithmic choices. All unbiased mutation operators with the same expected number of bit flips have the same effect on the expected diversity. Many crossover operators have no effect at all, including all binary unbiased, respectful operators. We review crossover operators from the literature and identify crossovers that are neutral towards the evolution of diversity and crossovers that are not.

Publications 1 - 10 of 67

Journal: Algorithmica

Abbreviation

Publisher

Journal Volumes

ISSN

Description

Filters

Search Results