
Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton Hyperbolic Random Graphs: Separators and Treewidth. European Symposium on Algorithms (ESA) 2016: 15:115:16
When designing and analyzing algorithms, one can obtain better and more realistic results for practical instances by assuming a certain probability distribution on the input. The worstcase runtime is then replaced by the expected runtime or by bounds that hold with high probability (whp), i.e., with probability \(1 \neq O(1/n)\), on the random input. Hyperbolic random graphs can be used to model complex realworld networks as they share many important properties such as a small diameter, a large clustering coefficient, and a powerlaw degreedistribution. Divide and conquer is an important algorithmic design principle that works particularly well if the instance admits small separators. We show that hyperbolic random graphs in fact have comparatively small separators. More precisely, we show that a hyperbolic random graph can be expected to have a balanced separator hierarchy with separators of size \(O(\sqrt(n^(3\beta)))\), \(O(log n)\), and \(O(1)\) if \(2 < \beta < 3\), \(\beta = 3\) and \(3 < \beta\), respectively (\(\beta\) is the powerlaw exponent). We infer that these graphs have whp a treewidth of \(O(\sqrt(n^(3  \beta)))\), \(O(log^2n)\), and \(O(log n)\), respectively. For \(2 < \beta < 3\), this matches a known lower bound. For the more realistic (but harder to analyze) binomial model, we still prove a sublinear bound on the treewidth. To demonstrate the usefulness of our results, we apply them to obtain fast matching algorithms and an approximation scheme for Independent Set.

Arndt, Tobias; Hafner, Danijar; Kellermeier, Thomas; Krogmann, Simon; Razmjou, Armin; Krejca, Martin S.; Rothernberger, Ralf; Friedrich, Tobias Probabilistic Routing for OnStreet Parking Search. European Symposium on Algorithms (ESA) 2016: 6:16:13
An estimated 30% of urban traffic is caused by search for parking spots [10]. Traffic could be reduced by suggesting effective routes leading along potential parking spots. In this paper, we formalize parking search as a probabilistic problem on a road graph and show that it is NPcomplete. We explore heuristics that optimize for the driving duration and the walking distance to the destination. Routes are constrained to reach a certain probability threshold of finding a spot. Empirically estimated probabilities of successful parking attempts are provided by TomTom on a perstreet basis. We release these probabilities as a dataset of about 80,000 roads covering the Berlin area. This allows to evaluate parking search algorithms on a real road network with realistic probabilities for the first time. However, for many other areas, parking probabilities are not openly available. Because they are effortful to collect, we propose an algorithm that relies on conventional road attributes only. Our experiments show that this algorithm comes close to the baseline by a factor of 1.3 in our cost measure. This leads to the conclusion that conventional road attributes may be sufficient to compute reasonably good parking search routes.

Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S. EDAs cannot be Balanced and Stable. Genetic and Evolutionary Computation Conference (GECCO) 2016: 11391146
Estimation of Distribution Algorithms (EDAs) work by iteratively updating a distribution over the search space with the help of samples from each iteration. Up to now, theoretical analyses of EDAs are scarce and present run time results for specific EDAs. We propose a new framework for EDAs that captures the idea of several known optimizers, including PBIL, UMDA, λMMASIB, cGA, and (1,λ)EA. Our focus is on analyzing two core features of EDAs: a balanced EDA is sensitive to signals in the fitness; a stable EDA remains uncommitted under a biasless fitness function. We prove that no EDA can be both balanced and stable. The LeadingOnes function is a prime example where, at the beginning of the optimization, the fitness function shows no bias for many bits. Since many wellknown EDAs are balanced and thus not stable, they are not wellsuited to optimize LeadingOnes. We give a stable EDA which optimizes LeadingOnes within a time of \(O(n log n)\).

Gao, Wanru; Friedrich, Tobias; Neumann, Frank FixedParameter Single Objective Search Heuristics for Minimum Vertex Cover. Parallel Problem Solving From Nature (PPSN) 2016: 740750
We consider how wellknown branching approaches for the classical minimum vertex cover problem can be turned into randomized initialization strategies with provable performance guarantees and investigate them by experimental investigations. Furthermore, we show how these techniques can be built into local search components and analyze a basic local search variant that is similar to a stateoftheart approach called NuMVC. Our experimental results for the two local search approaches show that making use of more complex branching strategies in the local search component can lead to better results on various benchmark graphs.

Doerr, Benjamin; Doerr, Carola; Kötzing, Timo Provably Optimal SelfAdjusting Step Sizes for MultiValued Decision Variables. Parallel Problem Solving From Nature (PPSN) 2016: 782791
We regard the problem of maximizing a OneMaxlike function defined over an alphabet of size $r$. In previous work [GECCO 2016] we have investigated how three different mutation operators influence the performance of Randomized Local Search (RLS) and the (1+1) Evolutionary Algorithm. This work revealed that among these natural mutation operators none is superior to the other two for any choice of $r$. We have also given in [GECCO 2016] some indication that the best achiev able run time for large $r$ is $\Theta(n log r(log n + log r))$, regardless of how the mutation operator is chosen, as long as it is a static choice (i.e., the distribution used for variation of the current individual does not change over time). Here in this work we show that we can achieve a better performance if we allow for adaptive mutation operators. More precisely, we analyze the performance of RLS using a selfadjusting mutation strength. In this algorithm the size of the steps taken in each iteration depends on the success of previous iterations. That is, the mutation strength is increased after a successful iteration and it is decreased otherwise. We show that this idea yields an expected optimization time of $\Theta(n(log n + log r))$, which is optimal among all comparisonbased search heuristics. This is the first time that selfadjusting parameter choices are shown to outperform static choices on a discrete multivalued optimization problem.

Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton; Laue, Sören Efficient Embedding of ScaleFree Graphs in the Hyperbolic Plane. European Symposium on Algorithms (ESA) 2016: 16:116:18
Hyperbolic geometry appears to be intrinsic in many large real networks. We construct and implement a new maximum likelihood estimation algorithm that embeds scalefree graphs in the hyperbolic space. All previous approaches of similar embedding algorithms require a runtime of \(\Omega(n^2)\). Our algorithm achieves quasilinear runtime, which makes it the first algorithm that can embed networks with hundreds of thousands of nodes in less than one hour. We demonstrate the performance of our algorithm on artificial and real networks. In all typical metrics like Loglikelihood and greedy routing our algorithm discovers embeddings that are very close to the ground truth.

Kötzing, Timo; Schirneck, Martin Towards an Atlas of Computational Learning Theory. Symposium on Theoretical Aspects of Computer Science (STACS) 2016: 47:147:13
A major part of our knowledge about Computational Learning stems from comparisons of the learning power of different learning criteria. These comparisons inform about tradeoffs between learning restrictions and, more generally, learning settings; furthermore, they inform about what restrictions can be observed without losing learning power. With this paper we propose that one main focus of future research in Computational Learning should be on a structured approach to determine the relations of different learning criteria. In particular, we propose that, for small sets of learning criteria, all pairwise relations should be determined; these relations can then be easily depicted as a map, a diagram detailing the relations. Once we have maps for many relevant sets of learning criteria, the collection of these maps is an Atlas of Computational Learning Theory, informing at a glance about the landscape of computational learning just as a geographical atlas informs about the earth. In this paper we work toward this goal by providing three example maps, one pertaining to partially setdriven learning, and two pertaining to strongly monotone learning. These maps can serve as blueprints for future maps of similar base structure.

Bläsius, Thomas; Rutter, Ignaz Simultaneous PQOrdering with Applications to Constrained Embedding Problems. Transactions on Algorithms 2016: 16
In this article, we define and study the new problem of SIMULTANEOUS PQORDERING. Its input consists of a set of PQtrees, which represent sets of circular orders of their leaves, together with a set of childparent relations between these PQtrees, such that the leaves of the child form a subset of the leaves of the parent. SIMULTANEOUS PQORDERING asks whether orders of the leaves of each of the trees can be chosen simultaneously; that is, for every childparent relation, the order chosen for the parent is an extension of the order chosen for the child. We show that SIMULTANEOUS PQORDERING is NPcomplete in general, and we identify a family of instances that can be solved efficiently, the 2fixed instances. We show that this result serves as a framework for several other problems that can be formulated as instances of SIMULTANEOUS PQORDERING. In particular, we give lineartime algorithms for recognizing simultaneous interval graphs and extending partial interval representations. Moreover, we obtain a lineartime algorithm for PARTIALLY PQCONSTRAINED PLANARITY for biconnected graphs, which asks for a planar embedding in the presence of 16 PQtrees that restrict the possible orderings of edges around vertices, and a quadratictime algorithm for SIMULTANEOUS EMBEDDING WITH FIXED EDGES for biconnected graphs with a connected intersection. Both results can be extended to the case where the input graphs are not necessarily biconnected but have the property that each cutvertex is contained in at most two nontrivial blocks. This includes, for example, the case where both graphs have a maximum degree of 5.

Jain, Sanjay; Kötzing, Timo; Ma, Junqi; Stephan, Frank On the Role of Update Constraints and TextTypes in Iterative Learning. Information and Computation 2016: 152168
The present work investigates the relationship of iterative learning with other learning criteria such as decisiveness, caution, reliability, nonUshapedness, monotonicity, strong monotonicity and conservativeness. Building on the result of Case and Moelius that iterative learners can be made nonUshaped, we show that they also can be made cautious and decisive. Furthermore, we obtain various special results with respect to oneone texts, fat texts and oneone hypothesis spaces.

Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. Robustness of Ant Colony Optimization to Noise. Evolutionary Computation 2016: 237254
Recently Ant Colony Optimization (ACO) algorithms have been proven to be efficient in uncertain environments, such as noisy or dynamically changing fitness functions. Most of these analyses focus on combinatorial problems, such as path finding. We analyze an ACO algorithm in a setting where we try to optimize the simple OneMax test function, but with additive posterior noise sampled from a Gaussian distribution. Without noise the classical (μ+1)EA outperforms any ACO algorithm, with smaller μ being better; however, with large noise, the (μ+1)EA fails, even for high values of μ (which are known to help against small noise). In this paper we show that ACO is able to deal with arbitrarily large noise in a graceful manner, that is, as long as the evaporation factor p is small enough dependent on the parameter δ^2 of the noise and the dimension n of the search space (p = o(1/(n(n + δlog n)^2 log n))), optimization will be successful.

Doerr, Benjamin; Doerr, Carola; Kötzing, Timo The Right Mutation Strength for MultiValued Decision Variables. Genetic and Evolutionary Computation Conference (GECCO) 2016: 11151122
The most common representation in evolutionary computation are bit strings. This is ideal to model binary decision variables, but less useful for variables taking more values. With very little theoretical work existing on how to use evolutionary algorithms for such optimization problems, we study the run time of simple evolutionary algorithms on some OneMaxlike functions defined over Ω=0,1,…,r−1n. More precisely, we regard a variety of problem classes requesting the componentwise minimization of the distance to an unknown target vector z∈Ω. For such problems we see a crucial difference in how we extend the standardbit mutation operator to these multivalued domains. While it is natural to select each position of the solution vector to be changed independently with probability 1/n, there are various ways to then change such a position. If we change each selected position to a random value different from the original one, we obtain an expected run time of Θ(nrlogn). If we change each selected position by either +1 or −1 (random choice), the optimization time reduces to Θ(nr+nlogn). If we use a random mutation strength i∈0,1,…,r−1n with probability inversely proportional to i and change the selected position by either +i or −i (random choice), then the optimization time becomes Θ(nlog(r)(log(n)+log(r))), bringing down the dependence on r from linear to polylogarithmic. One of our results depends on a new variant of the lower bounding multiplicative drift theorem.

Sutton, Andrew M. Superpolynomial Lower Bounds for the (1+1) EA on Some Easy Combinatorial Problems. Algorithmica 2016: 507528
The (1+1) EA is a simple evolutionary algorithm that is known to be efficient on linear functions and on some combinatorial optimization problems. In this paper, we rigorously study its behavior on two easy combinatorial problems: finding the 2coloring of a class of bipartite graphs, and constructing satisfying assignments for a class of satisfiable 2CNF Boolean formulas. We prove that it is inefficient on both problems in the sense that the number of iterations the algorithm needs to minimize the cost functions is superpolynomial with high probability. Our motivation is to better understand the influence of problem instance structure on the runtime character of a simple evolutionary algorithm. We are interested in what kind of structural features give rise to socalled metastable states at which, with probability 1  o(1), the (1+1) EA becomes trapped and subsequently has difficulty leaving. Finally, we show how to modify the (1+1) EA slightly in order to obtain a polynomialtime performance guarantee on both problems.

Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. Graceful Scaling on Uniform versus SteepTailed Noise. Parallel Problem Solving From Nature (PPSN) 2016: 761770
Recently, different evolutionary algorithms (EAs) have been analyzed in noisy environments. The most frequently used noise model for this was additive posterior noise (noise added after the fitness evaluation) taken from a Gaussian distribution. In particular, for this setting it was shown that the $(\mu + 1)$EA on OneMax does not scale gracefully (higher noise cannot efficiently be compensated by higher $\mu$). In this paper we want to understand whether there is anything special about the Gaussian distribution which makes the $(\mu + 1)$EA not scale gracefully. We keep the setting of posterior noise, but we look at other distributions. We see that for exponential tails the $(\mu + 1)$EA on OneMax does also not scale gracefully, for similar reasons as in the case of Gaussian noise. On the other hand, for uniform distributions (as well as other, similar distributions) we see that the $(\mu + 1)$EA on OneMax does scale gracefully, indicating the importance of the noise model.

Baum, Moritz; Bläsius, Thomas; Gemsa, Andreas; Rutter, Ignaz; Wegner, Franziska Scalable Exact Visualization of Isocontours in Road Networks via MinimumLink Paths. European Symposium on Algorithms (ESA) 2016: 7:17:18
Isocontours in road networks represent the area that is reachable from a source within a given resource limit. We study the problem of computing accurate isocontours in realistic, largescale networks. We propose isocontours represented by polygons with minimum number of segments that separate reachable and unreachable components of the network. Since the resulting problem is not known to be solvable in polynomial time, we introduce several heuristics that run in (almost) linear time and are simple enough to be implemented in practice. A key ingredient is a new practical lineartime algorithm for minimumlink paths in simple polygons. Experiments in a challenging realistic setting show excellent performance of our algorithms in practice, computing nearoptimal solutions in a few milliseconds on average, even for long ranges.

Friedrich, Tobias; Kötzing, Timo; Sutton, Andrew M. On the Robustness of Evolving Populations. Parallel Problem Solving From Nature (PPSN) 2016: 771781
Most theoretical work that studies the benefit of recombination focuses on the ability of crossover to speed up optimization time on specific search problems. In this paper, we take a slightly different perspective and investigate recombination in the context of evolving solutions that exhibit \emphmutational robustness, i.e., they display insensitivity to small perturbations. Various models in population genetics have demonstrated that increasing the effective recombination rate promotes the evolution of robustness. We show this result also holds in the context of evolutionary computation by proving crossover promotes the evolution of robust solutions in the standard $(\mu+1)$ GA. Surprisingly, our results show that the effect is present even when robust solutions are at a selective disadvantage due to lower fitness values.

Friedrich, Tobias ScaleFree Networks, Hyperbolic Geometry and Efficient Algorithms. Mathematical Foundations of Computer Science (MFCS) 2016: 4:1  4:3
The node degrees of large realworld networks often follow a powerlaw distribution. Such scalefree networks can be social networks, internet topologies, the web graph, power grids, or many other networks from literally hundreds of domains. The talk will introduce several mathematical models of scalefree networks (e.g. preferential attachment graphs, ChungLu graphs, hyperbolic random graphs) and analyze some of their properties (e.g. diameter, average distance, clustering). We then present several algorithms and distributed processes on and for these network models (e.g. rumor spreading, load balancing, deanonymization, embedding) and discuss a number of open problems. The talk assumes no prior knowledge about scalefree networks, distributed computing or hyperbolic geometry.

Chauhan, Ankit; Friedrich, Tobias; Rothenberger, Ralf Greed is Good for Deterministic ScaleFree Networks. Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2016
Large realworld networks typically follow a powerlaw degree distribution. To study such networks, numerous random graph models have been proposed. However, realworld networks are not drawn at random. Therefore, Brach, Cygan, Lacki, and Sankowski [SODA 2016] introduced two natural deterministic conditions: (1) a powerlaw upper bound on the degree distribution (PLBU) and (2) powerlaw neighborhoods, that is, the degree distribution of neighbors of each vertex is also upper bounded by a power law (PLBN). They showed that many realworld networks satisfy both deterministic properties and exploit them to design faster algorithms for a number of classical graph problems. We complement the work of Brach et al. by showing that some wellstudied random graph models exhibit both the mentioned PLB properties and additionally also a powerlaw lower bound on the degree distribution (PLBL). All three properties hold with high probability for ChungLu Random Graphs and Geometric Inhomogeneous Random Graphs and almost surely for Hyperbolic Random Graphs. As a consequence, all results of Brach et al. also hold with high probability or almost surely for those random graph classes. In the second part of this work we study three classical NPhard combinatorial optimization problems on PLB networks. It is known that on general graphs with maximum degree ∆, a greedy algorithm, which chooses nodes in the order of their degree, only achieves a Ω(ln∆)approximation for Minimum Vertex Cover and Minimum Dominating Set, and a Ω(∆)approximation for Maximum Independent Set. We prove that the PLBU property suffices for the greedy approach to achieve a constantfactor approximation for all three problems. We also show that all three combinatorial optimization problems are APXcomplete even if all PLBproperties holds hence, PTAS cannot be expected unless P=NP.

Friedrich, Tobias; Kötzing, Timo; Quinzan, Francesco; Sutton, Andrew M. Ant Colony Optimization Beats Resampling on Noisy Functions. Genetic and Evolutionary Computation Conference (GECCO) 2016: 34
Despite the pervasiveness of noise in realworld optimization, there is little understanding of the interplay between the operators of randomized search heuristics and explicit noisehandling techniques such as statistical resampling. Ant Colony Optimization (ACO) algorithms are claimed to be particularly wellsuited to dynamic and noisy problems, even without explicit noisehandling techniques. In this work, we empirically investigate the tradeoffs between resampling an the noisehandling abilities of ACO algorithms. Our main focus is to locate the point where resampling costs more than it is worth.

Dang, DucCuong; Friedrich, Tobias; Krejca, Martin S.; Kötzing, Timo; Lehre, Per Kristian; Oliveto, Pietro S.; Sudholt, Dirk; Sutton, Andrew Michael Escaping Local Optima with Diversity Mechanisms and Crossover. Genetic and Evolutionary Computation Conference (GECCO) 2016: 645652
Population diversity is essential for the effective use of any crossover operator. We compare seven commonly used diversity mechanisms and prove rigorous run time bounds for the (μ+1) GA using uniform crossover on the fitness function Jumpk. All previous results in this context only hold for unrealistically low crossover probability p_c=O(k/n), while we give analyses for the setting of constant p_c < 1 in all but one case. Our bounds show a dependence on the problem size n, the jump length k, the population size μ, and the crossover probability p_c. For the typical case of constant k > 2 and constant p_c, we can compare the resulting expected optimisation times for different diversity mechanisms assuming an optimal choice of μ: O(n^k1) for duplicate elimination/minimisation, O(n^2 log n) for maximising the convex hull, O(n log n) for det. crowding (assuming p_c = k/n), O(n log n) for maximising the Hamming distance, O(n log n) for fitness sharing, O(n log n) for the singlereceiver island model. This proves a sizeable advantage of all variants of the (μ+1) GA compared to the (1+1) EA, which requires θ(n^k). In a short empirical study we confirm that the asymptotic differences can also be observed experimentally.

Dang, DucCuong; Lehre, Per Kristian; Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Oliveto, Pietro S.; Sudholt, Dirk; Sutton, Andrew M. Emergence of Diversity and its Benefits for Crossover in Genetic Algorithms. Parallel Problem Solving From Nature (PPSN) 2016: 890900
Population diversity is essential for avoiding premature convergence in Genetic Algorithms (GAs) and for the effective use of crossover. Yet the dynamics of how diversity emerges in populations are not well understood. We use rigorous runtime analysis to gain insight into population dynamics and GA performance for a standard \((\mu+1)\) GA and the \(Jump_k\) test function. By studying the stochastic process underlying the size of the largest collection of identical genotypes we show that the interplay of crossover followed by mutation may serve as a catalyst leading to a sudden burst of diversity. This leads to improvements of the expected optimisation time of order \(\Omega(n/ \log n)\) compared to mutationonly algorithms like the \((1+1)\) EA.

Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Nallaperuma, Samadhi; Neumann, Frank; Schirneck, Martin Fast Building Block Assembly by Majority Vote Crossover. Genetic and Evolutionary Computation Conference (GECCO) 2016: 661668
Different works have shown how crossover can help with building block assembly. Typically, crossover might get lucky to select good building blocks from each parent, but these lucky choices are usually rare. In this work we consider a crossover operator which works on three parent individuals. In each component, the offspring inherits the value present in the majority of the parents; thus, we call this crossover operator majority vote. We show that, if good components are sufficiently prevalent in the individuals, majority vote creates an optimal individual with high probability. Furthermore, we show that this process can be amplified: as long as components are good independently and with probability at least 1/2+δ, we require only O(log 1/δ + log log n) successive stages of majority vote to create an optimal individual with high probability! We show how this applies in two scenarios. The first scenario is the Jump test function. With sufficient diversity, we get an optimization time of O(n log n) even for jump sizes as large as O(n^(1/2ε)). Our second scenario is a family of vertex cover instances. Majority vote optimizes this family efficiently, while local searches fail and only highly specialized twoparent crossovers are successful.

Chauhan, Ankit; Lenzner, Pascal; Melnichenko, Anna; Münn, Martin On Selfish Creation of Robust Networks. Symposium on Algorithmic Game Theory (SAGT) 2016: 141152
Robustness is one of the key properties of nowadays networks. However, robustness cannot be simply enforced by design or regulation since many important networks, most prominently the Internet, are not created and controlled by a central authority. Instead, Internetlike networks emerge from strategic decisions of many selfish agents. Interestingly, although lacking a coordinating authority, such naturally grown networks are surprisingly robust while at the same time having desirable properties like a small diameter. To investigate this phenomenon we present the first simple model for selfish network creation which explicitly incorporates agents striving for a central position in the network while at the same time protecting themselves against random edgefailure. We show that networks in our model are diverse and we prove the versatility of our model by adapting various properties and techniques from the nonrobust versions which we then use for establishing bounds on the Price of Anarchy. Moreover, we analyze the computational hardness of finding best possible strategies and investigate the game dynamics of our model.

Friedrich, Tobias; Krohmer, Anton Cliques in hyperbolic random graphs. International Conference on Computer Communications (INFOCOM) 2015: 15441552
Most complex realworld networks display scalefree features. This motivated the study of numerous random graph models with a powerlaw degree distribution. There is, however, no established and simple model which also has a high clustering of vertices as typically observed in real data. Hyperbolic random graphs bridge this gap. This natural model has recently been introduced by Papadopoulos, Krioukov, Boguñá, Vahdat (INFOCOM, pp. 29732981, 2010) and has shown theoretically and empirically to fulfill all typical properties of realworld networks, including powerlaw degree distribution and high clustering. We study cliques in hyperbolic random graphs G and present new results on the expected number of kcliques E[K_k] and the size of the largest clique ω(G). We observe that there is a phase transition at powerlaw exponent γ = 3. More precisely, for γ ε (2,3) we prove E[K_k] = n^k(3γ)/2 Θ(k)^k and ω(G) = Θ(n(3γ)/2) while for γ ≥ 3 we prove E[K_k] = nΘ(k)^k and ω(G) = Θ(log(n)/log log n). We empirically compare the ω(G) value of several scalefree random graph models with realworld networks. Our experiments show that the ω(G)predictions by hyperbolic random graphs are much closer to the data than other scalefree random graph models.

Bringmann, Karl; Friedrich, Tobias; Klitzke, Patrick Efficient computation of twodimensional solution sets maximizing the epsilonindicator. Congress on Evolutionary Computation (CEC) 2015: 970977
The majority of empirical comparisons of multiobjective evolutionary algorithms (MOEAs) are performed on synthetic benchmark functions. One of the advantages of synthetic test functions is the apriori knowledge of the optimal Pareto front. This allows measuring the proximity to the optimal front for the solution sets returned by the different MOEAs. Such a comparison is only meaningful if the cardinality of all solution sets is bounded by some fixed k. In order to compare MOEAs to the theoretical optimum achievable with k solutions, we determine best possible εindicator values achievable with solution sets of size k, up to an error of δ. We present a new algorithm with runtime O(k · log^2(δ1)), which is an exponential improvement regarding the dependence on the error δ compared to all previous work. We show mathematical correctness of our algorithm and determine optimal solution sets for sets of cardinality k ∈ 2, 3, 4, 5, 10, 20, 50, 100, 1000 for the well known test suits DTLZ, ZDT, WFG and LZ09 up to error δ = 10^25.

Friedrich, Tobias; Neumann, Frank; Thyssen, Christian Multiplicative Approximations, Optimal Hypervolume Distributions, and the Choice of the Reference Point. Evolutionary Computation (ECJ) 2015: 131159
Many optimization problems arising in applications have to consider several objective functions at the same time. Evolutionary algorithms seem to be a very natural choice for dealing with multiobjective problems as the population of such an algorithm can be used to represent the tradeoffs with respect to the given objective functions. In this paper, we contribute to the theoretical understanding of evolutionary algorithms for multiobjective problems. We consider indicatorbased algorithms whose goal is to maximize the hypervolume for a given problem by distributing μ points on the Pareto front. To gain new theoretical insights into the behavior of hypervolumebased algorithms we compare their optimization goal to the goal of achieving an optimal multiplicative approximation ratio. Our studies are carried out for different Pareto front shapes of biobjective problems. For the class of linear fronts and a class of convex fronts, we prove that maximizing the hypervolume gives the best possible approximation ratio when assuming that the extreme points have to be included in both distributions of the points on the Pareto front. Furthermore, we investigate the choice of the reference point on the approximation behavior of hypervolumebased approaches and examine Pareto fronts of different shapes by numerical calculations.

Friedrich, Tobias; Neumann, Frank Maximizing Submodular Functions under Matroid Constraints by MultiObjective Evolutionary Algorithms. Evolutionary Computation 2015: 543558
Many combinatorial optimization problems have underlying goal functions that are submodular. The classical goal is to find a good solution for a given submodular function f under a given set of constraints. In this paper, we investigate the runtime of a multiobjective evolutionary algorithm called GSEMO until it has obtained a good approximation for submodular functions. For the case of monotone submodular functions and uniform cardinality constraints we show that GSEMO achieves a (1 − 1/e)approximation in expected time O(n^2(logn+k)), where k is the value of the given constraint. For the case of nonmonotone submodular functions with k matroid intersection constraints, we show that GSEMO achieves a 1/(k + 2 + 1/k + ε)approximation in expected time O(n^k+5log(n)/ε).

Friedrich, Tobias; Krohmer, Anton Parameterized clique on inhomogeneous random graphs. Discrete Applied Mathematics 2015: 130138
Finding cliques in graphs is a classical problem which is in general NPhard and parameterized intractable. In typical applications like social networks or biological networks, however, the considered graphs are scalefree, i.e., their degree sequence follows a power law. Their specific structure can be algorithmically exploited and makes it possible to solve clique much more efficiently. We prove that on inhomogeneous random graphs with n nodes and power law exponent β, cliques of size k can be found in time O(n) for β ≥ 3 and in time O (ne^k^4 for 2 < β < 3 .

CordLandwehr, Andreas; Lenzner, Pascal Network Creation Games: Think Global  Act Local. Mathematical Foundations of Computer Science (MFCS) 2015: 248260
We investigate a noncooperative gametheoretic model for the formation of communication networks by selfish agents. Each agent aims for a central position at minimum cost for creating edges. In particular, the general model (Fabrikant et al., PODC’03) became popular for studying the structure of the Internet or social networks. Despite its significance, locality in this game was first studied only recently (Bilò et al., SPAA’14), where a worst case locality model was presented, which came with a high efficiency loss in terms of quality of equilibria. Our main contribution is a new and more optimistic view on locality: agents are limited in their knowledge and actions to their local view ranges, but can probe different strategies and finally choose the best. We study the influence of our locality notion on the hardness of computing best responses, convergence to equilibria, and quality of equilibria. Moreover, we compare the strength of local versus nonlocal strategy changes. Our results address the gap between the original model and the worst case locality variant. On the bright side, our efficiency results are in line with observations from the original model, yet we have a nonconstant lower bound on the Price of Anarchy.

Friedrich, Tobias; Krohmer, Anton On the Diameter of Hyperbolic Random Graphs. International Colloquium on Automata, Languages and Programming (ICALP) 2015: 614625
Large realworld networks are typically scalefree. Recent research has shown that such graphs are described best in a geometric space. More precisely, the internet can be mapped to a hyperbolic space such that geometric greedy routing performs close to optimal (Boguná, Papadopoulos, and Krioukov. Nature Communications, 1:62, 2010). This observation pushed the interest in hyperbolic networks as a natural model for scalefree networks. Hyperbolic random graphs follow a powerlaw degree distribution with controllable exponent β and show high clustering (Gugelmann, Panagiotou, and Peter. ICALP, pp. 573585, 2012). For understanding the structure of the resulting graphs and for analyzing the behavior of network algorithms, the next question is bounding the size of the diameter. The only known explicit bound is O((logn)^32/((3−β)(5−β))) (Kiwi and Mitsche. ANALCO, pp. 2639, 2015). We present two much simpler proofs for an improved upper bound of O((logn)^2/(3−β)) and a lower bound of Ω(logn).

Nguyen, Anh Quang; Sutton, Andrew M.; Neumann, Frank Population size matters: Rigorous runtime results for maximizing the hypervolume indicator. Theoretical Computer Science 2015: 2436
Using the hypervolume indicator to guide the search of evolutionary multiobjective algorithms has become very popular in recent years. We contribute to the theoretical understanding of these algorithms by carrying out rigorous runtime analyses. We consider multiobjective variants of the problems OneMax and LeadingOnes called OMM and LOTZ, respectively, and investigate hypervolumebased algorithms with population sizes that do not allow coverage of the entire Pareto front. Our results show that LOTZ is easier to optimize than OMM for hypervolumebased evolutionary multiobjective algorithms which is contrary to the results on their singleobjective variants and the wellstudied (1+1)~EA.

Freydenberger, Dominik D.; Kötzing, Timo Fast Learning of Restricted Regular Expressions and DTDs. Theory of Computing Systems 2015: 11141158
We study the problem of generalizing from a finite sample to a language taken from a predefined language class. The two language classes we consider are subsets of the regular languages and have significance in the specification of XML documents (the classes corresponding to so called chain regular expressions, Chares, and to single occurrence regular expressions, Sores). The previous literature gave a number of algorithms for generalizing to Sores providing a trade off between quality of the solution and speed. Furthermore, a fast but nonoptimal algorithm for generalizing to Chares is known. For each of the two language classes we give an efficient algorithm returning a minimal generalization from the given finite sample to an element of the fixed language class; such generalizations are called descriptive. In this sense, both our algorithms are optimal.

Friedrich, Tobias; Hercher, Christian On the kernel size of clique cover reductions for random intersection graphs. Journal of Discrete Algorithms 2015: 128136
Covering all edges of a graph by a minimum number of cliques is a well known NP hard problem. For the parameter k being the maximal number of cliques to be used, the problem becomes fixed parameter tractable. However, assuming the Exponential Time Hypothesis, there is no kernel of subexponential size in the worstcase.We study the average kernel size for random intersection graphs with n vertices, edge probability p, and clique covers of size k. We consider the wellknown set of reduction rules of Gramm, Guo, Hüffner, and Niedermeier (2009) 17 and show that with high probability they reduce the graph completely if p is bounded away from 1 and k < c log ¿ n for some constant c 0 . This shows that for large probabilistic graph classes like random intersection graphs the expected kernel size can be substantially smaller than the known exponential worstcase bounds.

Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. Robustness of Ant Colony Optimization to Noise. Genetic and Evolutionary Computation Conference (GECCO) 2015: 1724
Recently Ant Colony Optimization (ACO) algorithms have been proven to be efficient in uncertain environments, such as noisy or dynamically changing fitness functions. Most of these analyses focus on combinatorial problems, such as path finding. We analyze an ACO algorithm in a setting where we try to optimize the simple OneMax test function, but with additive posterior noise sampled from a Gaussian distribution. Without noise the classical (μ+1)EA outperforms any ACO algorithm, with smaller μ being better; however, with large noise, the (μ+1)EA fails, even for high values of μ (which are known to help against small noise). In this paper we show that ACO is able to deal with arbitrarily large noise in a graceful manner, that is, as long as the evaporation factor p is small enough dependent on the parameter δ^2 of the noise and the dimension n of the search space (p = o(1/(n(n + δlog n)^2 log n))), optimization will be successful.

Doerr, Benjamin; Doerr, Carola; Kötzing, Timo Unbiased BlackBox Complexities of Jump Functions. Evolutionary Computation 2015: 641670
We analyze the unbiased blackbox complexity of jump functions with small, medium, and large sizes of the fitness plateau surrounding the optimal solution. Among other results, we show that when the jump size is (1/2−ε)n, that is, only a small constant fraction of the fitness values is visible, then the unbiased blackbox complexities for arities 3 and higher are of the same order as those for the simple \textscOneMax function. Even for the extreme jump function, in which all but the two fitness values n/2 and n are blanked out, polynomialtime mutationbased (i.e., unary unbiased) blackbox optimization algorithms exist. This is quite surprising given that for the extreme jump function almost the whole search space (all but a Θ(n^−1/2) fraction) is a plateau of constant fitness. To prove these results, we introduce new tools for the analysis of unbiased blackbox complexities, for example, selecting the new parent individual not by comparing the fitnesses of the competing search points, but also by taking into account the (empirical) expected fitnesses of their offspring.

Fountoulakis, Nikolaos; Friedrich, Tobias; Hermelin, Danny On the averagecase complexity of parameterized clique. Theoretical Computer Science 2015: 1829
The kClique problem is a fundamental combinatorial problem that plays a prominent role in classical as well as in parameterized complexity theory. It is among the most wellknown NPcomplete and W[1]complete problems. Moreover, its averagecase complexity analysis has created a long thread of research already since the 1970s. Here, we continue this line of research by studying the dependence of the averagecase complexity of the kClique problem on the parameter k. To this end, we define two natural parameterized analogs of efficient averagecase algorithms. We then show that kClique admits both analogues for Erdős–Rényi random graphs of arbitrary density. We also show that kClique is unlikely to admit either of these analogs for some specific computable input distribution.

Chicano, Francisco; Sutton, Andrew M.; Whitley, L. Darrell; Alba, Enrique Fitness Probability Distribution of BitFlip Mutation. Evolutionary Computation 2015: 217248
Bitflip mutation is a common mutation operator for evolutionary algorithms applied to optimize functions over binary strings. In this paper, we develop results from the theory of landscapes and Krawtchouk polynomials to exactly compute the probability distribution of fitness values of a binary string undergoing uniform bitflip mutation. We prove that this probability distribution can be expressed as a polynomial in p, the probability of flipping each bit. We analyze these polynomials and provide closedform expressions for an easy linear problem Onemax, and an NPhard problem, MAXSAT. We also discuss a connection of the results with runtime analysis.

Doerr, Benjamin; Doerr, Carola; Kötzing, Timo Solving Problems with Unknown Solution Length at (Almost) No Extra Cost. Genetic and Evolutionary Computation Conference (GECCO) 2015: 831838
Most research in the theory of evolutionary computation assumes that the problem at hand has a fixed problem size. This assumption does not always apply to realworld optimization challenges, where the length of an optimal solution may be unknown a priori. Following up on previous work of Cathabard, Lehre, and Yao [FOGA 2011] we analyze variants of the (1+1) evolutionary algorithm for problems with unknown solution length. For their setting, in which the solution length is sampled from a geometric distribution, we provide mutation rates that yield an expected optimization time that is of the same order as that of the (1+1) EA knowing the solution length. We then show that almost the same run times can be achieved even if no a priori information on the solution length is available. Finally, we provide mutation rates suitable for settings in which neither the solution length nor the positions of the relevant bits are known. Again we obtain almost optimal run times for the OneMax and LeadingOnes test functions, thus solving an open problem from Cathabard et al.

Doerr, Benjamin; Neumann, Frank; Sutton, Andrew M. Improved Runtime Bounds for the (1+1) EA on Random 3CNF Formulas Based on FitnessDistance Correlation. Genetic and Evolutionary Computation Conference (GECCO) 2015: 14151422
With this paper, we contribute to the theoretical understanding of randomized search heuristics by investigating their behavior on random 3SAT instances. We improve the results for the (1+1) EA obtained by Sutton and Neumann [PPSN 2014, 942951] in three ways. First, we reduce the upper bound by a linear factor and prove that the (1+1) EA obtains optimal solutions in time $O(n \log n)$ with high probability on asymptotically almost all highdensity satisfiable 3CNF formulas. Second, we extend the range of densities for which this bound holds to satisfiable formulas of at least logarithmic density. Finally, we complement these mathematical results with numerical experiments that summarize the behavior of the (1+1) EA on formulas along the density spectrum, and suggest that the implicit constants hidden in our bounds are low. Our proofs are based on analyzing the run of the algorithm by establishing a fitnessdistance correlation. This approach might be of independent interest and we are optimistic that it is useful for the analysis of randomized search heuristics in various other settings. To our knowledge, this is the first time that fitnessdistance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.

Wagner, Markus; Bringmann, Karl; Friedrich, Tobias; Neumann, Frank Efficient optimization of many objectives by approximationguided evolution. European Journal of Operational Research 2015: 465479
Multiobjective optimization problems arise frequently in applications, but can often only be solved approximately by heuristic approaches. Evolutionary algorithms have been widely used to tackle multiobjective problems. These algorithms use different measures to ensure diversity in the objective space but are not guided by a formal notion of approximation. We present a framework for evolutionary multiobjective optimization that allows to work with a formal notion of approximation. This approximationguided evolutionary algorithm (AGE) has a worstcase runtime linear in the number of objectives and works with an archive that is an approximation of the nondominated objective vectors seen during the run of the algorithm. Our experimental results show that AGE finds competitive or better solutions not only regarding the achieved approximation, but also regarding the total hypervolume. For all considered test problems, even for many (i.e., more than ten) dimensions, AGE discovers a good approximation of the Pareto front. This is not the case for established algorithms such as NSGAII, SPEA2, and SMSEMOA. In this paper we compare AGE with two additional algorithms that use very fast hypervolumeapproximations to guide their search. This significantly speeds up the runtime of the hypervolumebased algorithms, which now allows a comparison of the underlying selection schemes.

Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton Unbounded Discrepancy of Deterministic Random Walks on Grids. International Symposium on Algorithms and Computation (ISAAC) 2015: 212222
Random walks are frequently used in randomized algorithms. We study a derandomized variant of a random walk on graphs, called rotorrouter model. In this model, instead of distributing tokens randomly, each vertex serves its neighbors in a fixed deterministic order. For most setups, both processes behave remarkably similar: Starting with the same initial configuration, the number of tokens in the rotorrouter model deviates only slightly from the expected number of tokens on the corresponding vertex in the random walk model. The maximal difference over all vertices and all times is called single vertex discrepancy. Cooper and Spencer (2006) showed that on ℤ^d the single vertex discrepancy is only a constant c_d. Other authors also determined the precise value of c_d for d=1,2. All these results, however, assume that initially all tokens are only placed on one partition of the bipartite graph ℤ^d. We show that this assumption is crucial by proving that otherwise the single vertex discrepancy can become arbitrarily large. For all dimensions d≥1 and arbitrary discrepancies ℓ≥0, we construct configurations that reach a discrepancy of at least ℓ.

Bringmann, Karl; Friedrich, Tobias; Hoefer, Martin; Rothenberger, Ralf; Sauerwald, Thomas UltraFast Load Balancing on ScaleFree Networks. International Colloquium on Automata, Languages and Programming (ICALP) 2015: 516527
The performance of large distributed systems crucially depends on efficiently balancing their load. This has motivated a large amount of theoretical research how an imbalanced load vector can be smoothed with local algorithms. For technical reasons, the vast majority of previous work focuses on regular (or almost regular) graphs including symmetric topologies such as grids and hypercubes, and ignores the fact that large networks are often highly heterogenous. We model large scalefree networks by ChungLu random graphs and analyze a simple local algorithm for iterative load balancing. On nnode graphs our distributed algorithm balances the load within O((loglogn)^2) steps. It does not need to know the exponent β∈(2,3) of the powerlaw degree distribution or the weights w_i of the graph model. To the best of our knowledge, this is the first result which shows that loadbalancing can be done in doublelogarithmic time on realistic graph classes.

Alam, Md. Jawaherul; Bläsius, Thomas; Rutter, Ignaz; Ueckerdt, Torsten; Wolff, Alexander Pixel and Voxel Representations of Graphs. Graph Drawing (GD) 2015: 472486
We study contact representations for graphs, which we call pixel representations in 2D and voxel representations in 3D. Our representations are based on the unit square grid whose cells we call pixels in 2D and voxels in 3D. Two pixels are adjacent if they share an edge, two voxels if they share a face. We call a connected set of pixels or voxels a blob. Given a graph, we represent its vertices by disjoint blobs such that two blobs contain adjacent pixels or voxels if and only if the corresponding vertices are adjacent. We are interested in the size of a representation, which is the number of pixels or voxels it consists of. We first show that finding minimumsize representations is NPcomplete. Then, we bound representation sizes needed for certain graph classes. In 2D, we show that, for kouterplanar graphs with n vertices, Θ(kn) pixels are always sufficient and sometimes necessary. In particular, outerplanar graphs can be represented with a linear number of pixels, whereas general planar graphs sometimes need a quadratic number. In 3D, Θ(n^2) voxels are always sufficient and sometimes necessary for any nvertex graph. We improve this bound to Θ(n⋅τ) for graphs of treewidth τ and to O((g+1)^2 n log^2 n) for graphs of genus g. In particular, planar graphs admit representations with O(nlog^2 n) voxels.

Paixão, Tiago; Badkobeh, Golnaz; Barton, Nick H.; Çörüş, Doğan; Dang, DucCuong; Friedrich, Tobias; Lehre, Per Kristian; Sudholt, Dirk; Sutton, Andrew; Trubenová, Barbora Toward a unifying framework for evolutionary processes. Journal of Theoretical Biology 2015: 2843
The theory of population genetics and evolutionary computation have been evolving separately for nearly 30 years. Many results have been independently obtained in both fields and many others are unique to its respective field. We aim to bridge this gap by developing a unifying framework for evolutionary processes that allows both evolutionary algorithms and population genetics models to be cast in the same formal framework. The framework we present here decomposes the evolutionary process into its several components in order to facilitate the identification of similarities between different models. In particular, we propose a classification of evolutionary operators based on the defining properties of the different components. We cast several commonly used operators from both fields into this common framework. Using this, we map different evolutionary and genetic algorithms to different evolutionary regimes and identify candidates with the most potential for the translation of results between the fields. This provides a unified description of evolutionary processes and represents a stepping stone towards new tools and results to both fields.

Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David Counting Homomorphisms to SquareFree Graphs, Modulo 2. International Colloquium on Automata, Languages, and Programming (ICALP) 2015: 642653
We study the problem ⊕HomsToH of counting, modulo 2, the homomorphisms from an input graph to a fixed undirected graph H. A characteristic feature of modular counting is that cancellations make wider classes of instances tractable than is the case for exact (nonmodular) counting; thus, subtle dichotomy theorems can arise. We show the following dichotomy: for any H that contains no 4cycles, ⊕HomsToH is either in polynomial time or is ⊕Pcomplete. This partially confirms a conjecture of Faben and Jerrum that was previously only known to hold for trees and for a restricted class of treewidth2 graphs called cactus graphs. We confirm the conjecture for a rich class of graphs, including graphs of unbounded treewidth. In particular, we focus on squarefree graphs, which are graphs without 4cycles. These graphs arise frequently in combinatorics, for example, in connection with the strong perfect graph theorem and in certain graph algorithms. Previous dichotomy theorems required the graph to be treelike so that treelike decompositions could be exploited in the proof. We prove the conjecture for a much richer class of graphs by adopting a much more general approach.

Chauhan, Ankit; Rao, B. V. Raghavendra Parameterized Analogues of Probabilistic Computation. Conference on Algorithms and Discrete Applied Mathematics (CALDAM) 2015: 181192
We study structural aspects of randomized parameterized computation. We introduce a new class W[P]−PFPT as a natural parameterized analogue of PP. Our definition uses the machine based characterization of the parameterized complexity class W[P] obtained by Chen et.al [TCS 2005]. We translate most of the structural properties and characterizations of the class PP to the new class W[P]−PFPT. We study a parameterization of the polynomial identity testing problem based on the degree of the polynomial computed by the arithmetic circuit. We obtain a parameterized analogue of the well known SchwartzZippel lemma [Schwartz, JACM 80 and Zippel, EUROSAM 79]. Additionally, we introduce a parameterized variant of permanent, and prove its #W[1] completeness.

Rothenberger, Ralf; Grau, Sascha; Rossberg, Michael Dominating an stCut in a Network. Conference on Current Trends in Theory and Practice of Informatics (SOFSEM) 2015: 401411
We study an optimization problem with applications in design and analysis of resilient communication networks: given two vertices s, t in a graph G = (V,E), find a vertex set X ⊂ V of minimum cardinality, such that X and its neighborhood constitute an st vertex separator. Although the problem naturally combines notions of graph connectivity and domination, its computational properties significantly differ from these relatives. In particular, we show that on general graphs the problem cannot be approximated to within a factor of 2^log^1−δn, with δ = 1 / loglog^cn and arbitrary c<1/2 (if P ≠ NP). This inapproximability result even applies if the subgraph induced by a solution set has the additional constraint of being connected. Furthermore, we give a 2√napproximation algorithm and study the problem on graphs with bounded node degree. With Δ being the maximum degree of nodes V ∖ s,t, we identify a (Δ + 1) approximation algorithm.

Friedrich, Tobias; Neumann, Frank Maximizing Submodular Functions under Matroid Constraints by Evolutionary Algorithms. Evolutionary Computation 2015: 543558
Many combinatorial optimization problems have underlying goal functions that are submodular. The classical goal is to find a good solution for a given submodular function f under a given set of constraints. In this paper, we investigate the runtime of a simple single objective evolutionary algorithm called (1+1) EA and a multiobjective evolutionary algorithm called GSEMO until they have obtained a good approximation for submodular functions. For the case of monotone submodular functions and uniform cardinality constraints we show that the GSEMO achieves a (11/e)approximation in expected polynomial time. For the case of monotone functions where the constraints are given by the intersection of k ≥ 2 matroids, we show that the (1+1) EA achieves a (1 + k/δ)approximation in expected polynomial time for any constant δ > 0. Turning to nonmonotone symmetric submodular functions with k ≥ 1 matroid intersection constraints, we show that the GSEMO achieves a 1/((k+2)(1+ϵ)))approximation in expected time O(n^k+6 log(n)/ϵ).

Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. The Benefit of Recombination in Noisy Evolutionary Search. International Symposium of Algorithms and Computation (ISAAC) 2015: 140150
Practical optimization problems frequently include uncertainty about the quality measure, for example due to noisy evaluations. Thus, they do not allow for a straightforward application of traditional optimization techniques. In these settings metaheuristics are a popular choice for deriving good optimization algorithms, most notably evolutionary algorithms which mimic evolution in nature. Empirical evidence suggests that genetic recombination is useful in uncertain environments because it can stabilize a noisy fitness signal. With this paper we want to support this claim with mathematical rigor. The setting we consider is that of noisy optimization. We study a simple noisy fitness function that is derived by adding Gaussian noise to a monotone function. First, we show that a classical evolutionary algorithm that does not employ sexual recombination (the (μ+1)EA) cannot handle the noise efficiently, regardless of the population size. Then we show that an evolutionary algorithm which does employ sexual recombination (the Compact Genetic Algorithm, short: cGA) can handle the noise using a graceful scaling of the population.

Bläsius, Thomas; Lehmann, Sebastian; Rutter, Ignaz Orthogonal Graph Drawing with Inflexible Edges. Conference on Algorithms and Complexity (CIAC) 2015: 6173
We consider the problem of creating plane orthogonal drawings of 4planar graphs (planar graphs with maximum degree 4) with constraints on the number of bends per edge. More precisely, we have a flexibility function assigning to each edge e a natural number flex(e), its flexibility. The problem FlexDraw asks whether there exists an orthogonal drawing such that each edge e has at most flex(e) bends. It is known that FlexDraw is NPhard if flex(e)=0 for every edge e [7]. On the other hand, FlexDraw can be solved efficiently if flex(e)≥1 [2] and is trivial if flex(e)≥2 [1] for every edge e. To close the gap between the NPhardness for flex(e)=0 and the efficient algorithm for flex(e)≥1, we investigate the computational complexity of FlexDraw in case only few edges are inflexible (i.e., have flexibility 0). We show that for any ε>0 FlexDraw is NPcomplete for instances with O(n^ε) inflexible edges with pairwise distance Ω(n^1−ε) (including the case where they induce a matching). On the other hand, we give an FPTalgorithm with running time O(2^k⋅n⋅T_flow(n)), where T_flow(n) is the time necessary to compute a maximum flow in a planar flow network with multiple sources and sinks, and k is the number of inflexible edges having at least one endpoint of degree 4.

Friedrich, Tobias; Wagner, Markus Seeding the initial population of multiobjective evolutionary algorithms: A computational study. Applied Soft Computing 2015: 223230
Most experimental studies initialize the population of evolutionary algorithms with random genotypes. In practice, however, optimizers are typically seeded with good candidate solutions either previously known or created according to some problemspecific method. This seeding has been studied extensively for singleobjective problems. For multiobjective problems, however, very little literature is available on the approaches to seeding and their individual benefits and disadvantages. In this article, we are trying to narrow this gap via a comprehensive computational study on common realvalued test functions. We investigate the effect of two seeding techniques for five algorithms on 48 optimization problems with 2, 3, 4, 6, and 8 objectives. We observe that some functions (e.g., DTLZ4 and the LZ family) benefit significantly from seeding, while others (e.g., WFG) profit less. The advantage of seeding also depends on the examined algorithm.

Bläsius, Thomas; Rutter, Ignaz Disconnectivity and relative positions in simultaneous embeddings. Computational Geometry 2015: 459478
For two planar graphs G^1 = ( V^1, E^1) and G^2 = ( V^2, E^2) sharing a common subgraph G = G^1 ∩ G^2 the problem Simultaneous Embedding with Fixed Edges (SEFE) asks whether they admit planar drawings such that the common graph is drawn the same. Previous algorithms only work for cases where G is connected, and hence do not need to handle relative positions of connected components. We consider the problem where G, G^1 and G^2 are not necessarily connected.First, we show that a general instance of SEFE can be reduced in linear time to an equivalent instance where V^1 = V^2 and G^1 and G^2 are connected. Second, for the case where G consists of disjoint cycles, we introduce the CCtree which represents all embeddings of G that extend to planar embeddings of G^1. We show that CCtrees can be computed in linear time, and that their intersection is again a CCtree. This yields a lineartime algorithm for SEFE if all k input graphs (possibly k > 2) pairwise share the same set of disjoint cycles. These results, including the CCtree, extend to the case where G consists of arbitrary connected components, each with a fixed planar embedding on the sphere. Then the running time is O (n^2) .

Kötzing, Timo; Lissovoi, Andrei; Witt, Carsten (1+1) EA on Generalized Dynamic OneMax. Foundations of Genetic Algorithms (FOGA) 2015: 4051
Evolutionary algorithms (EAs) perform well in settings involving uncertainty, including settings with stochastic or dynamic fitness functions. In this paper, we analyze the (1+1) EA on dynamically changing OneMax, as introduced by Droste (2003). We reprove the known results on first hitting times using the modern tool of drift analysis. We extend these results to search spaces which allow for more than two values per dimension. Furthermore, we make an anytime analysis as suggested by Jansen and Zarges (2014), analyzing how closely the (1+1) EA can track the dynamically moving optimum over time. We get tight bounds both for the case of bit strings, as well as for the case of more than two values per position. Surprisingly, in the latter setting, the expected quality of the search point maintained by the (1+1) EA does not depend on the number of values per dimension.

Bringmann, Karl; Friedrich, Tobias; Klitzke, Patrick Twodimensional subset selection for hypervolume and epsilonindicator. Genetic and Evolutionary Computation Conference (GECCO) 2014: 589596
The goal of biobjective optimization is to find a small set of good compromise solutions. A common problem for biobjective evolutionary algorithms is the following subset selection problem (SSP): Given n solutions P ⊂ R^2 in the objective space, select k solutions P^* from P that optimize an indicator function. In the hypervolume SSP we want to select k points P^* that maximize the hypervolume indicator I_HYP(P^*, r) for some reference point r ∈ R^2. Similarly, the εindicator SSP aims at selecting k~points P^* that minimize the εindicator I_ε(P^*,R) for some reference set R ⊂ R^2 of size m (which can be R=P). We first present a new algorithm for the hypervolume SSP with runtime O(n (k + log n)). Our second main result is a new algorithm for the εindicator SSP with runtime O(n log n + m log m). Both results improve the current state of the art runtimes by a factor of (nearly) n and make the problems tractable for new applications. Preliminary experiments confirm that the theoretical results translate into substantial empirical runtime improvements.

Doerr, Benjamin; Friedrich, Tobias; Sauerwald, Thomas Quasirandom Rumor Spreading. Transactions on Algorithms 2014: 9:19:35
We propose and analyze a quasirandom analogue of the classical push model for disseminating information in networks (“randomized rumor spreading”). In the classical model, in each round, each informed vertex chooses a neighbor at random and informs it, if it was not informed before. It is known that this simple protocol succeeds in spreading a rumor from one vertex to all others within O(log n) rounds on complete graphs, hypercubes, random regular graphs, ErdősRényi random graphs, and Ramanujan graphs with probability 1 − o(1). In the quasirandom model, we assume that each vertex has a (cyclic) list of its neighbors. Once informed, it starts at a random position on the list, but from then on informs its neighbors in the order of the list. Surprisingly, irrespective of the orders of the lists, the abovementioned bounds still hold. In some cases, even better bounds than for the classical model can be shown.

Friedrich, Tobias; Neumann, Frank Maximizing Submodular Functions under Matroid Constraints by Multiobjective Evolutionary Algorithms. Parallel Problem Solving from Nature (PPSN) 2014: 922931
Many combinatorial optimization problems have underlying goal functions that are submodular. The classical goal is to find a good solution for a given submodular function f under a given set of constraints. In this paper, we investigate the runtime of a multiobjective evolutionary algorithm called GSEMO until it has obtained a good approximation for submodular functions. For the case of monotone submodular functions and uniform cardinality constraints we show that GSEMO achieves a (1 − 1/e)approximation in expected time O(n^2(logn+k)), where k is the value of the given constraint. For the case of nonmonotone submodular functions with k matroid intersection constraints, we show that GSEMO achieves a 1/(k + 2 + 1/k + ε)approximation in expected time O(n^k+5log(n)/ε).

Göbel, Andreas; Goldberg, Leslie Ann; McQuillan, Colin; Richerby, David; Yamakami, Tomoyuki Counting List Matrix Partitions of Graphs. Conference on Computational Complexity (CCC) 2014: 5665
Given a symmetric DxD matrix M over 0, 1, *, a list Mpartition of a graph G is a partition of the vertices of G into D parts which are associated with the rows of M. The part of each vertex is chosen from a given list in such a way that no edge of G is mapped to a 0 in M and no nonedge of G is mapped to a 1 in M. Many important graphtheoretic structures can be represented as list Mpartitions including graph colourings, split graphs and homogeneous sets, which arise in the proofs of the weak and strong perfect graph conjectures. Thus, there has been quite a bit of work on determining for which matrices M computations involving list Mpartitions are tractable. This paper focuses on the problem of counting list Mpartitions, given a graph G and given lists for each vertex of G. We give an algorithm that solves this problem in polynomial time for every (fixed) matrix M for which the problem is tractable. The algorithm relies on data structures such as sparsedense partitions and sub cube decompositions to reduce each problem instance to a sequence of problem instances in which the lists have a certain useful structure that restricts access to portions of M in which the interactions of 0s and 1s is controlled. We show how to solve the resulting restricted instances by converting them into particular counting constraint satisfaction problems (#CSPs) which we show how to solve using a constraint satisfaction technique known as "arcconsistency". For every matrix M for which our algorithm fails, we show that the problem of counting list Mpartitions is #Pcomplete. Furthermore, we give an explicit characterisation of the dichotomy theorem  counting list Mpartitions is tractable (in FP) if and only if the matrix M has a structure called a derectangularising sequence. Finally, we show that the metaproblem of determining whether a given matrix has a derectangularising sequence is NPcomplete.

Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David The complexity of counting homomorphisms to cactus graphs modulo 2. Transactions on Computation Theory 2014: 17:117:29
A homomorphism from a graph G to a graph H is a function from V(G) to V(H) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. In this article, we study the complexity of counting homomorphisms modulo 2. The complexity of modular counting was introduced by Papadimitriou and Zachos and it has been pioneered by Valiant who famously introduced a problem for which counting modulo 7 is easy but counting modulo 2 is intractable. Modular counting provides a rich setting in which to study the structure of homomorphism problems. In this case, the structure of the graph H has a big influence on the complexity of the problem. Thus, our approach is graphtheoretic. We give a complete solution for the class of cactus graphs, which are connected graphs in which every edge belongs to at most one cycle. Cactus graphs arise in many applications such as the modelling of wireless sensor networks and the comparison of genomes. We show that, for some cactus graphs H, counting homomorphisms to H modulo 2 can be done in polynomial time. For every other fixed cactus graph H, the problem is complete in the complexity class ⊕P, which is a wide complexity class to which every problem in the polynomial hierarchy can be reduced (using randomised reductions). Determining which H lead to tractable problems can be done in polynomial time. Our result builds upon the work of Faben and Jerrum, who gave a dichotomy for the case in which H is a tree.

Doerr, Benjamin; Doerr, Carola; Kötzing, Timo The unbiased blackbox complexity of partition is polynomial. Artificial Intelligence 2014: 275286
Unbiased blackbox complexity was introduced as a refined complexity model for randomized search heuristics (Lehre and Witt (2012) [24]). For several problems, this notion avoids the unrealistically low complexity results given by the classical model of Droste et al. (2006) [10]. We show that for some problems the unbiased blackbox complexity remains artificially small. More precisely, for two different formulations of an NP hard subclass of the wellknown Partition problem, we give mutationonly unbiased blackbox algorithms having complexity O(nlogn). This indicates that also the unary unbiased blackbox complexity does not give a complete picture of the true difficulty of this problem for randomized search heuristics.

Chicano, Francisco; Whitley, Darrell; Sutton, Andrew M. Efficient identification of improving moves in a ball for pseudoboolean problems. Genetic and Evolutionary Computation Conference (GECCO) 2014: 437444
Hill climbing algorithms are at the core of many approaches to solve optimization problems. Such algorithms usually require the complete enumeration of a neighborhood of the current solution. In the case of problems defined over binary strings of length n, we define the rball neighborhood as the set of solutions at Hamming distance r or less from the current solution. For r ll n this neighborhood contains Θ(n^r) solutions. In this paper efficient methods areintroduced to locate improving moves in the rball neighborhood for problems that can be written as a sum of a linear number of subfunctions depending on a bounded number of variables. NKlandscapes and MAXkSAT are examples of these problems. If the number of subfunctions depending on any given variable is also bounded, then we prove that the method can explore the neighborhood in constant time, despite the fact that the number of solutions in the neighborhood is polynomial in n. We develop a hill climber based on our exploration method and we analyze its efficiency and efficacy using experiments with NKqlandscapes instances.

Jain, Sanjay; Kötzing, Timo; Ma, Junqi; Stephan, Frank On the Role of Update Constraints and TextTypes in Iterative Learning. International Conference on Algorithmic Learning Theory (ALT) 2014: 5569
The present work investigates the relationship of iterative learning with other learning criteria such as decisiveness, caution, reliability, nonUshapedness, monotonicity, strong monotonicity and conservativeness. Building on the result of Case and Moelius that iterative learners can be made nonUshaped, we show that they also can be made cautious and decisive. Furthermore, we obtain various special results with respect to oneone texts, fat texts and oneone hypothesis spaces.

Kötzing, Timo Concentration of first hitting times under additive drift. Genetic and Evolutionary Computation Conference (GECCO) 2014: 13911398
Recent advances in drift analysis have given us better and better tools for understanding random processes, including the run time of randomized search heuristics. In the setting of multiplicative drift we do not only have excellent bounds on the expected run time, but also more general results showing the concentration of the run time. In this paper we investigate the setting of additive drift under the assumption of strong concentration of the "step size" of the process. Under sufficiently strong drift towards the goal we show a strong concentration of the hitting time. In contrast to this, we show that in the presence of small drift a Gambler'sRuinlike behavior of the process overrides the influence of the drift. Finally, in the presence of sufficiently strong negative drift the hitting time is superpolynomial with high probability; this corresponds to the socalled negative drift theorem, for which we give new variants.

Kötzing, Timo; Palenta, Raphaela A Map of Update Constraints in Inductive Inference. International Conference on Algorithmic Learning Theory (ALT) 2014: 4054
We investigate how different learning restrictions reduce learning power and how the different restrictions relate to one another. We give a complete map for nine different restrictions both for the cases of complete information learning and setdriven learning. This completes the picture for these wellstudied delayable learning restrictions. A further insight is gained by different characterizations of conservative learning in terms of variants of cautious learning. Our analyses greatly benefit from general theorems we give, for example showing that learners with exclusively delayable restrictions can always be assumed total.

Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David Counting Homomorphisms to Cactus Graphs Modulo 2. Symposium on Theoretical Aspects of Computer Science (STACS) 2014: 350361
A homomorphism from a graph G to a graph H is a function from V(G) to V(H) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. In this article, we study the complexity of counting homomorphisms modulo 2. The complexity of modular counting was introduced by Papadimitriou and Zachos and it has been pioneered by Valiant who famously introduced a problem for which counting modulo 7 is easy but counting modulo 2 is intractable. Modular counting provides a rich setting in which to study the structure of homomorphism problems. In this case, the structure of the graph H has a big influence on the complexity of the problem. Thus, our approach is graphtheoretic. We give a complete solution for the class of cactus graphs, which are connected graphs in which every edge belongs to at most one cycle. Cactus graphs arise in many applications such as the modelling of wireless sensor networks and the comparison of genomes. We show that, for some cactus graphs H, counting homomorphisms to H modulo 2 can be done in polynomial time. For every other fixed cactus graph H, the problem is complete in the complexity class ⊕P, which is a wide complexity class to which every problem in the polynomial hierarchy can be reduced (using randomised reductions). Determining which H lead to tractable problems can be done in polynomial time. Our result builds upon the work of Faben and Jerrum, who gave a dichotomy for the case in which H is a tree.

Whitley, Darrell; Sutton, Andrew M.; Ochoa, Gabriela; Chicano, Francisco The component model for elementary landscapes and partial neighborhoods. Theoretical Computer Science 2014: 5975
Local search algorithms exploit moves on an adjacency graph of the search space. An “elementary landscape” exists if the objective function f is an eigenfunction of the Laplacian of the graph induced by the neighborhood operator; this allows various statistics about the neighborhood to be computed in closed form. A new component based model makes it relatively simple to prove that certain types of landscapes are elementary. The traveling salesperson problem, weighted graph (vertex) coloring and the minimum graph bisection problem yield elementary landscapes under commonly used local search operators. The component model is then used to efficiently compute the mean objective function value over partial neighborhoods for these same problems. For a traveling salesperson problem over n cities, the 2opt neighborhood can be decomposed into ⌊n/2 − 1⌋ partial neighborhoods. For graph coloring and the minimum graph bisection problem, partial neighborhoods can be used to focus search on those moves that are capable of producing a solution with a strictly improving objective function value.

Kötzing, Timo; Sutton, Andrew M.; Neumann, Frank; O'Reilly, UnaMay The Max problem revisited: The importance of mutation in genetic programming. Theoretical Computer Science (TCS) 2014: 94107
This paper contributes to the rigorous understanding of genetic programming algorithms by providing runtime complexity analyses of the wellstudied Max problem. Several experimental studies have indicated that it is hard to solve the Max problem with crossoverbased algorithms. Our analyses show that different variants of the Max problem can provably be solved using simple mutationbased genetic programming algorithms. Our results advance the body of computational complexity analyses of genetic programming, indicate the importance of mutation in genetic programming, and reveal new insights into the behavior of mutationbased genetic programming algorithms.

Gießen, Christian; Kötzing, Timo Robustness of populations in stochastic environments. Genetic and Evolutionary Computation Conference (GECCO) 2014: 13831390
We consider stochastic versions of OneMax and LeadingOnes and analyze the performance of evolutionary algorithms with and without populations on these problems. It is known that the (1+1) EA on OneMax performs well in the presence of very small noise, but poorly for higher noise levels. We extend these results to LeadingOnes and to many different noise models, showing how the application of drift theory can significantly simplify and generalize previous analyses. Most surprisingly, even small populations (of size Θ(logn)) can make evolutionary algorithms perform well for high noise levels, well outside the abilities of the (1+1) EA. Larger population sizes are even more beneficial; we consider both parent and offspring populations. In this sense, populations are robust in these stochastic settings.

Bringmann, Karl; Friedrich, Tobias; Krohmer, Anton Deanonymization of Heterogeneous Random Graphs in Quasilinear Time. European Symposium on Algorithms (ESA) 2014: 197208
There are hundreds of online social networks with billions of users in total. Many such networks publicly release structural information, with all personal information removed. Empirical studies have shown, however, that this provides a false sense of privacy — it is possible to identify almost all users that appear in two such anonymized network as long as a few initial mappings are known. We analyze this problem theoretically by reconciling two versions of an artificial powerlaw network arising from independent subsampling of vertices and edges. We present a new algorithm that identifies most vertices and makes no wrong identifications with high probability. The number of vertices matched is shown to be asymptotically optimal. For an nvertex graph, our algorithm uses n^ε seed nodes (for an arbitrarily small ε) and runs in quasilinear time. This improves previous theoretical results which need Θ(n) seed nodes and have runtimes of order n^1 + Ω(1). Additionally, the applicability of our algorithm is studied experimentally on different networks.

Bläsius, Thomas; Brückner, Guido; Rutter, Ignaz Complexity of HigherDegree Orthogonal Graph Embedding in the Kandinsky Model. European Symposium on Algorithms (ESA) 2014: 161172
We show that finding orthogonal gridembeddings of plane graphs (planar with fixed combinatorial embedding) with the minimum number of bends in the socalled Kandinsky model (which allows vertices of degree >4) is NPcomplete, thus solving a longstanding open problem. On the positive side, we give an efficient algorithm for several restricted variants, such as graphs of bounded branch width and a subexponential exact algorithm for general plane graphs.

Bringmann, Karl; Friedrich, Tobias Convergence of HypervolumeBased Archiving Algorithms. Transactions on Evolutionary Computation 2014: 643657
Multiobjective evolutionary algorithms typically maintain a set of solutions. A crucial part of these algorithms is the archiving, which decides what solutions to keep. A (μ + λ) archiving algorithm defines how to choose in each generation μ children from μ parents and λ offspring together. We study mathematically the convergence behavior of hypervolumebased archiving algorithms. We distinguish two cases for the offspring generation. A bestcase view leads to a study of the effectiveness of archiving algorithms. It was known that all (μ + 1)archiving algorithms are ineffective, which means that a set with maximum hypervolume is not necessarily reached. We prove that for λ <; μ, all archiving algorithms are ineffective. We also present upper and lower bounds for the achievable hypervolume for different classes of archiving algorithms. On the other hand, a worstcase view on the offspring generation leads to a study of the competitive ratio of archiving algorithms. This measures how much smaller hypervolumes are achieved due to not knowing the future offspring in advance. We present upper and lower bounds on the competitive ratio of different archiving algorithms and present an archiving algorithm, which is the first known computationally efficient archiving algorithm with constant competitive ratio.

Bläsius, Thomas; Rutter, Ignaz A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem. Graph Drawing (GD) 2014: 440451
The clustered planarity problem (cplanarity) asks whether a hierarchically clustered graph admits a planar drawing such that the clusters can be nicely represented by regions. We introduce the cdtree data structure and give a new characterization of cplanarity. It leads to efficient algorithms for cplanarity testing in the following cases. (i) Every cluster and every cocluster has at most two connected components. (ii) Every cluster has at most five outgoing edges. Moreover, the cdtree reveals interesting connections between cplanarity and planarity with constraints on the order of edges around vertices. On one hand, this gives rise to a bunch of new open problems related to cplanarity, on the other hand it provides a new perspective on previous results.

Doerr, Benjamin; Doerr, Carola; Kötzing, Timo Unbiased blackbox complexities of jump functions: how to cross large plateaus. Genetic and Evolutionary Computation Conference (GECCO) 2014: 769776
We analyze the unbiased blackbox complexity of jump functions with large jump sizes. Among other results, we show that when the jump size is (1/2  epsilon)n, that is, only a small constant fraction of the fitness values is visible, then the unbiased blackbox complexities for arities 3 and higher are of the same order as those for the simple OneMax function. Even for the extreme jump function, in which all but the two fitness values n/2 and n are blanked out, polynomialtime mutationbased (i.e., unary unbiased) blackbox optimization algorithms exist. This is quite surprising given that for the extreme jump function almost the whole search space (all but a Θ(n^1/2) fraction) is a plateau of constant fitness.To prove these results, we introduce new tools for the analysis of unbiased blackbox complexities, for example, selecting the new parent individual not by comparing the fitnesses of the competing search points, but also by taking into account the (empirical) expected fitnesses of their offspring.

Sutton, Andrew M.; Neumann, Frank Runtime Analysis of Evolutionary Algorithms on Randomly Constructed HighDensity Satisfiable 3CNF Formulas. Parallel Problem Solving from Nature (PPSN) 2014: 942951
We show that simple mutationonly evolutionary algorithms find a satisfying assignment on two similar models of random planted 3CNF Boolean formulas in polynomial time with high probability in the high constraint density regime. We extend the analysis to random formulas conditioned on satisfiability (i.e., the socalled filtered distribution) and conclude that most highdensity satisfiable formulas are easy for simple evolutionary algorithms. With this paper, we contribute the first rigorous study of randomized search heuristics from the evolutionary computation community on wellstudied distributions of random satisfiability problems.

Bläsius, Thomas; Krug, Marcus; Rutter, Ignaz; Wagner, Dorothea Orthogonal Graph Drawing with Flexibility Constraints. Algorithmica 2014: 859885
Traditionally, the quality of orthogonal planar drawings is quantified by either the total number of bends, or the maximum number of bends per edge. However, this neglects that in typical applications, edges have varying importance. In this work, we investigate an approach that allows to specify the maximum number of bends for each edge individually, depending on its importance. We consider a new problem called FlexDraw that is defined as follows. Given a planar graph G=(V,E) on n vertices with maximum degree 4 and a function flex : E ⟶ ℕ_0 that assigns a flexibility to each edge, does G admit a planar embedding on the grid such that each edge e has at most flex(e) bends? Note that in our setting the combinatorial embedding of G is not fixed. FlexDraw directly extends the problem βembeddability asking whether G can be embedded with at most β bends per edge. We give an algorithm with runningtime O(n^2) solving FlexDraw when the flexibility of each edge is positive. This includes 1embeddability as a special case and thus closes the complexity gap between 0embeddability, which is NPhard to decide, and 2embeddability, which is efficiently solvable since every planar graph with maximum degree 4 admits a 2embedding except for the octahedron. In addition to the polynomialtime algorithm we show that FlexDraw is NPhard even if the edges with flexibility 0 induce a tree or a union of disjoint stars.

Bringmann, Karl; Friedrich, Tobias; Klitzke, Patrick Generic Postprocessing via Subset Selection for Hypervolume and EpsilonIndicator. Parallel Problem Solving from Nature (PPSN) 2014: 518527
Most biobjective evolutionary algorithms maintain a population of fixed size μ and return the final population at termination. During the optimization process many solutions are considered, but most are discarded. We present two generic postprocessing algorithms which utilize the archive of all nondominated solutions evaluated during the search. We choose the best μ solutions from the archive such that the hypervolume or εindicator is maximized. This postprocessing costs no additional fitness function evaluations and has negligible runtime compared to most EMOAs. We experimentally examine our postprocessing for four standard algorithms (NSGAII, SPEA2, SMSEMOA, IBEA) on ten standard test functions (DTLZ 1–2,7, ZDT 1–3, WFG 3–6) and measure the average quality improvement. The median decrease of the distance to the optimal εindicator is 95%, the median decrease of the distance to the optimal hypervolume value is 86%. We observe similar performance on a realworld problem (wind turbine placement).

Kötzing, Timo A Solution to Wiehagen's Thesis. Symposium on Theoretical Aspects of Computer Science (STACS) 2014: 494505
Wiehagen’s Thesis in Inductive Inference (1991) essentially states that, for each learning criterion, learning can be done in a normalized, enumerative way. The thesis was not a formal statement and thus did not allow for a formal proof, but support was given by examples of a number of different learning criteria that can be learned by enumeration. Building on recent formalizations of learning criteria, we are now able to formalize Wiehagen’s Thesis. We prove the thesis for a wide range of learning criteria, including many popular criteria from the literature. We also show the limitations of the thesis by giving four learning criteria for which the thesis does not hold (and, in two cases, was probably not meant to hold). Beyond the original formulation of the thesis, we also prove stronger versions which allow for many corollaries relating to strongly decisive and conservative learning.

Sutton, Andrew M.; Neumann, Frank; Nallaperuma, Samadhi Parameterized Runtime Analyses of Evolutionary Algorithms for the Planar Euclidean Traveling Salesperson Problem. Evolutionary Computation 2014: 595628
Parameterized runtime analysis seeks to understand the influence of problem structure on algorithmic runtime. In this paper, we contribute to the theoretical understanding of evolutionary algorithms and carry out a parameterized analysis of evolutionary algorithms for the Euclidean traveling salesperson problem (Euclidean TSP). We investigate the structural properties in TSP instances that influence the optimization process of evolutionary algorithms and use this information to bound their runtime. We analyze the runtime in dependence of the number of inner points k. In the first part of the paper, we study a (μ + λ) EA in a strictly black box setting and show that it can solve the Euclidean TSP in expected time O(n · A(ε) · max(μ/λ) · n^2 , 1 + (μ/λ) · n^4k(2k − 1)!) where A is a function of the minimum angle ε between any three points. Based on insights provided by the analysis, we improve this upper bound by introducing a mixed mutation strategy that incorporates both 2opt moves and permutation jumps. This strategy improves the upper bound to O(n · A(ε) · max(μ/λ) · n^2 , 1 + (μ/λ) · n^2k(k − 1)!). In the second part of the paper, we use the information gained in the analysis to incorporate domain knowledge to design two fixedparameter tractable (FPT) evolutionary algorithms for the planar Euclidean TSP. We first develop a (μ + λ) EA based on an analysis by M. Theile, 2009, ”Exact solutions to the traveling salesperson problem by a populationbased evolutionary algorithm,” Lecture notes in computer science, Vol. 5482 (pp. 145–155), that solves the TSP with k inner points in O(max2^kk^2n^2λ^1,n) generations with probability 1 − e^Ω(n). We then design a (μ + λ) EA that incorporates a dynamic programming step into the fitness evaluation. We prove that a variant of this evolutionary algorithm using 2opt mutation solves the problem after O(max(k − 2)!k^2k2λ^1, 1) steps in expectation with a cost of O(nk) for each fitness evaluation.

Kötzing, Timo Iterative learning from positive data and counters. Theoretical Computer Science (TCS) 2014: 155169
We analyze iterative learning in the limit from positive data with the additional information provided by a counter. The simplest type of counter provides the current iteration number (counting up from 0 to infinity), which is known to improve learning power over plain iterative learning. We introduce five other (weaker) counter types, for example only providing some unbounded and nondecreasing sequence of numbers. Analyzing these types allows for understanding what properties of a counter can benefit learning. For the iterative setting, we completely characterize the relative power of the learning criteria corresponding to the counter types. In particular, for our types, the only properties improving learning power are unboundedness and strict monotonicity. Furthermore, we show that each of our types of counter improves learning power over weaker ones in some settings, and that, for iterative learning criteria with one of these types of counter, separations of learning criteria are necessarily witnessed by classes containing only infinite languages.

Bringmann, Karl; Friedrich, Tobias Parameterized averagecase complexity of the hypervolume indicator. Genetic and Evolutionary Computation Conference (GECCO) 2013: 575582
The hypervolume indicator (HYP) is a popular measure for the quality of a set of n solutions in ℜRd. We discuss its asymptotic worstcase runtimes and several lower bounds depending on different complexitytheoretic assumptions. Assuming that P ≠ NP, there is no algorithm with runtime poly(n,d). Assuming the exponential time hypothesis, there is no algorithm with runtime n^o(d). In contrast to these worstcase lower bounds, we study the averagecase complexity of HYP for points distributed i.i.d. at random on a ddimensional simplex. We present a general framework which translates any algorithm for HYP with worstcase runtime n^f(d) to an algorithm with worstcase runtime n^f(d)+1 and fixedparametertractable (FPT) averagecase runtime. This can be used to show that HYP can be solved in expected time O(d^d2/2, n + d, n^2), which implies that HYP is FPT on average while it is W[1]hard in the worstcase. For constant dimension d this gives an algorithm for HYP with runtime O(n^2) on average. This is the first result proving that HYP is asymptotically easier in the average case. It gives a theoretical explanation why most HYP algorithms perform much better on average than their theoretical worstcase runtime predicts.

Friedrich, Tobias; Kroeger, Trent; Neumann, Frank Weighted preferences in evolutionary multiobjective optimization. Machine Learning and Cybernetics 2013: 139148
Evolutionary algorithms have been widely used to tackle multiobjective optimization problems. Incorporating preference information into the search of evolutionary algorithms for multiobjective optimization is of great importance as it allows one to focus on interesting regions in the objective space. Zitzler et al. have shown how to use a weight distribution function on the objective space to incorporate preference information into hypervolumebased algorithms. We show that this weighted information can easily be used in other popular EMO algorithms as well. Our results for NSGAII and SPEA2 show that this yields similar results to the hypervolume approach and requires less computational effort.

Fellows, Michael R.; Friedrich, Tobias; Hermelin, Danny; Narodytska, Nina; Rosamond, Frances A. Constraint satisfaction problems: Convexity makes AllDifferent constraints tractable. Theoretical Computer Science 2013: 8189
We examine the complexity of constraint satisfaction problems that consist of a set of AllDiff constraints. Such CSPs naturally model a wide range of realworld and combinatorial problems, like scheduling, frequency allocations, and graph coloring problems. As this problem is known to be NPcomplete, we investigate under which further assumptions it becomes tractable. We observe that a crucial property seems to be the convexity of the variable domains and constraints. Our main contribution is an extensive study of the complexity of Multiple AllDiff CSPs for a set of natural parameters, like maximum domain size and maximum size of the constraint scopes. We show that, depending on the parameter, convexity can make the problem tractable even though it is provably intractable in general. Interestingly, the convexity of constraints is the key property in achieving fixed parameter tractability, while the convexity of domains does not usually make the problem easier.

Nallaperuma, Samadhi; Sutton, Andrew M.; Neumann, Frank Parameterized complexity analysis and more effective construction methods for ACO algorithms and the euclidean traveling salesperson problem. Congress on Evolutionary Computation (CEC) 2013: 20452052
We propose a new construction procedure for ant colony optimization (ACO) algorithms working on the Euclidean traveling salesperson problem (TSP) that preserves the ordering on the convex hull of the points in the instance. The procedure is inspired by theoretical analyses for simple evolutionary algorithms that are provably more efficient on instances where the number of inner points of the instance is not too large. We integrate the construction procedure into the wellknown MaxMin Ant System (MMAS) and empirically show that it leads to more efficient optimization on instances where the number of inner points is not too high.

Anand, S.; Bringmann, Karl; Friedrich, Tobias; Garg, Naveen; Kumar, Amit Minimizing Maximum (Weighted) FlowTime on Related and Unrelated Machines. International Colloquium on Automata, Languages and Programming (ICALP) 2013: 1324
In this paper we initiate the study of job scheduling on related and unrelated machines so as to minimize the maximum flow time or the maximum weighted flow time (when each job has an associated weight). Previous work for these metrics considered only the setting of parallel machines, while previous work for scheduling on unrelated machines only considered L_p, p < ∞ norms. Our main results are: (1) we give an O(ε^−3)competitive algorithm to minimize maximum weighted flow time on related machines where we assume that the machines of the online algorithm can process 1+ε units of a job in 1 timeunit (ε speed augmentation). (2) For the objective of minimizing maximum flow time on unrelated machines we give a simple 2/εcompetitive algorithm when we augment the speed by ε. For m machines we show a lower bound of Ω(m) on the competitive ratio if speed augmentation is not permitted. Our algorithm does not assign jobs to machines as soon as they arrive. To justify this “drawback” we show a lower bound of Ω(logm) on the competitive ratio of immediate dispatch algorithms. In both these lower bound constructions we use jobs whose processing times are in 1,∞, and hence they apply to the more restrictive subset parallel setting. (3) For the objective of minimizing maximum weighted flow time on unrelated machines we establish a lower bound of Ω(logm)on the competitive ratio of any online algorithm which is permitted to use s = O(1) speed machines. In our lower bound construction, job j has a processing time of p_j on a subset of machines and infinity on others and has a weight 1/p_j. Hence this lower bound applies to the subset parallel setting for the special case of minimizing maximum stretch.

Case, John; Kötzing, Timo Topological Separations in Inductive Inference. International Conference on Algorithmic Learning Theory (ALT) 2013: 128142
Re learning in the limit from positive data, a major concern is which classes of languages are learnable with respect to a given learning criterion. We are particularly interested herein in the reasons for a class of languages to be unlearnable. We consider two types of reasons. One type is called topological where it does not help if the learners are allowed to be uncomputable (an example of Gold's is that no class containing an infinite language and all its finite sublanguages is learnable — even by an uncomputable learner). Another reason is called computational (where the learners are required to be algorithmic). In particular, two learning criteria might allow for learning different classes of languages from one another — but with dependence on whether the unlearnability is of type topological or computational. In this paper we formalize the idea of two learning criteria separating topologically in learning power. This allows us to study more closely why two learning criteria separate in learning power. For a variety of learning criteria, concerning vacillatory, monotone, (several kinds of) iterative and feedback learning, we show that certain learning criteria separate topologically, and certain others, which are known to separate, are shown not to separate topologically. Showing that learning criteria do not separate topologically implies that any known separation must necessarily exploit algorithmicity of the learner.

Bringmann, Karl; Friedrich, Tobias Exact and Efficient Generation of Geometric Random Variates and Random Graphs. International Colloquium on Automata, Languages, and Programming (ICALP) 2013: 267278
The standard algorithm for fast generation of ErdősRényi random graphs only works in the Real RAM model. The critical point is the generation of geometric random variates Geo(p), for which there is no algorithm that is both exact and efficient in any bounded precision machine model. For a RAM model with word size w=Ω(loglog(1/p)), we show that this is possible and present an exact algorithm for sampling Geo(p) in optimal expected time $\mathcalO(1 + \log(1/p) / w)$. We also give an exact algorithm for sampling minn, Geo(p) in optimal expected time $\mathcalO(1 + \log(\operatornamemin\1/p,n\)/w)$. This yields a new exact algorithm for sampling ErdősRényi and ChungLu random graphs of n vertices and m (expected) edges in optimal expected runtime $\mathcalO(n + m)$ on a RAM with word size w=Θ(logn).

Croitoru, Cosmina; Kötzing, Timo A Normal Form for Argumentation Frameworks. Theorie and Applications of Formal Argumentation (TAFA) 2013: 3245
We study formal argumentation frameworks as introduced by Dung (1995). We show that any such argumentation framework can be syntactically augmented into a normal form (having a simplified attack relation), preserving the semantic properties of original arguments. An argumentation framework is in normal form if no argument attacks a conflicting pair of arguments. An augmentation of an argumentation framework is obtained by adding new arguments and changing the attack relation such that the acceptability status of original arguments is maintained in the new framework. Furthermore, we define joinnormal semantics leading to augmentations of the joined argumentation frameworks. Also, a rewriting technique which transforms in cubic time a given argumentation framework into a normal form is devised.

Case, John; Kötzing, Timo Memorylimited nonUshaped learning with solved open problems. Theoretical Computer Science (TCS) 2013: 100123
In empirical cognitive science, for human learning, a semantic or behavioral Ushape occurs when a learner first learns, then unlearns, and, finally, relearns, some target concept. Within the formal framework of Inductive Inference, for learning from positive data, previous results have shown, for example, that such Ushapes are unnecessary for explanatory learning, but are necessary for behaviorally correct and nontrivial vacillatory learning. Herein we also distinguish between semantic and syntactic Ushapes. We answer a number of open questions in the prior literature as well as provide new results regarding syntactic Ushapes. Importantly for cognitive science, we see more of a previously noticed pattern that, for parameterized learning criteria, beyond very few initial parameter values, Ushapes are necessary for full learning power. We analyze the necessity of Ushapes in two memorylimited settings. The first setting is Bounded Memory State (BMS) learning, where a learner has an explicitlybounded state memory, and otherwise only knows its current datum. We show that there are classes learnable with three (or more) memory states that are not learnable nonUshapedly with any finite number of memory states. This result is surprising, since, for learning with one or two memory states, Ushapes are known to be unnecessary. This solves an open question from the literature. The second setting is that of Memoryless Feedback (MLF) learning, where a learner may ask a bounded number of questions about what data has been seen so far, and otherwise only knows its current datum. We show that there is a class learnable memorylessly with a single feedback query such that this class is not learnable nonUshapedly memorylessly with any finite number of feedback queries. We employ selflearning classes together with the Operator Recursion Theorem for many of our results, but we also introduce two new techniques for obtaining results. The first is for transferring inclusion results from one setting to another. The main part of the second is the Hybrid Operator Recursion Theorem, which enables us to separate some learning criteria featuring complexitybounded learners, employing selflearning classes. Both techniques are not specific to Ushaped learning, but applicable for a wide range of settings.

Wagner, Markus; Friedrich, Tobias Efficient parent selection for ApproximationGuided Evolutionary multiobjective optimization. Congress on Evolutionary Computation (CEC) 2013: 18461853
The Pareto front of a multiobjective optimization problem is typically very large and can only be approximated. ApproximationGuided Evolution (AGE) is a recently presented evolutionary multiobjective optimization algorithm that aims at minimizing iteratively the approximation factor, which measures how well the current population approximates the Pareto front. It outperforms stateoftheart algorithms for problems with many objectives. However, AGE's performance is not competitive on problems with very few objectives. We study the reason for this behavior and observe that AGE selects parents uniformly at random, which has a detrimental effect on its performance. We then investigate different algorithmspecific selection strategies for AGE. The main difficulty here is finding a computationally efficient selection scheme which does not harm AGEs linear runtime in the number of objectives. We present several improved selections schemes that are computationally efficient and substantially improve AGE on lowdimensional objective spaces, but have no negative effect in highdimensional objective spaces.

Kawald, Bernd; Lenzner, Pascal On dynamics in selfish network creation. Symposium on Parallelism in Algorithms and Architectures (SPAA) 2013: 8392
We consider the dynamic behavior of several variants of the Network Creation Game, introduced by Fabrikant et al. [PODC'03]. Equilibrium networks in these models have desirable properties like low social cost and small diameter, which makes them attractive for the decentralized creation of overlaynetworks. Unfortunately, due to the nonconstructiveness of the Nash equilibrium, no distributed algorithm for finding such networks is known. We treat these games as sequentialmove games and analyze if (uncoordinated) selfish play eventually converges to an equilibrium. Thus, we shed light on one of the most natural algorithms for this problem: distributed local search, where in each step some agent performs a myopic selfish improving move. We show that fast convergence is guaranteed for all versions of Swap Games, introduced by Alon et al. [SPAA'10], if the initial network is a tree. Furthermore, we prove that this process can be sped up to an almost optimal number of moves by employing a very natural move policy. Unfortunately, these positive results are no longer true if the initial network has cycles and we show the surprising result that even one nontree edge suffices to destroy the convergence guarantee. This answers an open problem from Ehsani et al. [SPAA'11] in the negative. Moreover, we show that on nontree networks no move policy can enforce convergence. We extend our negative results to the wellstudied original version, where agents are allowed to buy and delete edges as well. For this model we prove that there is no convergence guarantee  even if all agents play optimally. Even worse, if played on a noncomplete hostgraph, then there are instances where no sequence of improving moves leads to a stable network. Furthermore, we analyze whether costsharing has positive impact on the convergence behavior. For this we consider a version by Corbo and Parkes [PODC'05] where bilateral consent is needed for the creation of an edge and where edgecosts are shared among the involved agents. We show that employing such a costsharing rule yields even worse dynamic behavior..

Doerr, Benjamin; Johannsen, Daniel; Kötzing, Timo; Neumann, Frank; Theile, Madeleine More effective crossover operators for the allpairs shortest path problem. Theoretical Computer Science (TCS) 2013: 1226
The allpairs shortest path problem is the first nonartificial problem for which it was shown that adding crossover can significantly speed up a mutationonly evolutionary algorithm. Recently, the analysis of this algorithm was refined and it was shown to have an expected optimization time (w.r.t. the number of fitness evaluations) of Θ(n^3.25(logn)^0.25). In contrast to this simple algorithm, evolutionary algorithms used in practice usually employ refined recombination strategies in order to avoid the creation of infeasible offspring. We study extensions of the basic algorithm by two such concepts which are central in recombination, namely \emphrepair mechanisms and \emphparent selection. We show that repairing infeasible offspring leads to an improved expected optimization time of O(n^3.2(logn)^0.2). As a second part of our study we prove that choosing parents that guarantee feasible offspring results in an even better optimization time of O(n^3logn). Both results show that already simple adjustments of the recombination operator can asymptotically improve the runtime of evolutionary algorithms.

Biedl, Therese C.; Bläsius, Thomas; Niedermann, Benjamin; Nöllenburg, Martin; Prutkin, Roman; Rutter, Ignaz Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other GridBased Graph Drawings. Graph Drawing (GD) 2013: 460471
We present a simple and versatile formulation of gridbased graph representation problems as an integer linear program (ILP) and a corresponding SAT instance. In a gridbased representation vertices and edges correspond to axisparallel boxes on an underlying integer grid; boxes can be further constrained in their shapes and interactions by additional problemspecific constraints. We describe a general ddimensional model for grid representation problems. This model can be used to solve a variety of NPhard graph problems, including pathwidth, bandwidth, optimum storientation, areaminimal (bark) visibility representation, boxicityk graphs and others. We implemented SATmodels for all of the above problems and evaluated them on the Rome graphs collection. The experiments show that our model successfully solves NPhard problems within few minutes on small to mediumsize Rome graphs.

Bläsius, Thomas; Karrer, Annette; Rutter, Ignaz Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices. Graph Drawing (GD) 2013: 220231
A simultaneous embedding (with fixed edges) of two graphs G^1 and G^2 with common graph G = G^1 ∩ G^2 is a pair of planar drawings of G^1 and G^2 that coincide on G. It is an open question whether there is a polynomialtime algorithm that decides whether two graphs admit a simultaneous embedding (problem Sefe). In this paper, we present two results. First, a set of three lineartime preprocessing algorithms that remove certain substructures from a given Sefe instance, producing a set of equivalent Sefe instances without such substructures. The structures we can remove are (1) cutvertices of the union graph G^∪ = G ^1 ∪ G^2 , (2) most separating pairs of G^∪, and (3) connected components of G that are biconnected but not a cycle. Second, we give an O(n^3)time algorithm solving Sefe for instances with the following restriction. Let u be a pole of a Pnode μ in the SPQRtree of a block of G^1 or G^2 . Then at most three virtual edges of μ may contain common edges incident to u. All algorithms extend to the sunflower case, i.e., to the case of more than three graphs pairwise intersecting in the same common graph.

Doerr, Benjamin; Kötzing, Timo; Lengler, Johannes; Winzen, Carola Blackbox complexities of combinatorial problems. Theoretical Computer Science 2013: 84106
Blackbox complexity is a complexity theoretic measure for how difficult a problem is to be optimized by a general purpose optimization algorithm. It is thus one of the few means trying to understand which problems are tractable for genetic algorithms and other randomized search heuristics. Most previous work on blackbox complexity is on artificial test functions. In this paper, we move a step forward and give a detailed analysis for the two combinatorial problems minimum spanning tree and singlesource shortest paths. Besides giving interesting bounds for their blackbox complexities, our work reveals that the choice of how to model the optimization problem is nontrivial here. This in particular comes true where the search space does not consist of bit strings and where a reasonable definition of unbiasedness has to be agreed on.

Bläsius, Thomas; Kobourov, Stephen G.; Rutter, Ignaz Simultaneous Embedding of Planar Graphs. Handbook of Graph Drawing and Visualization 2013: 349381
Simultaneous embedding is concerned with simultaneously representing a series of graphs sharing some or all vertices. This forms the basis for the visualization of dynamic graphs and thus is an important field of research. Recently there has been a great deal of work investigating simultaneous embedding problems both from a theoretical and a practical point of view. We survey recent work on this topic.

Bläsius, Thomas; Rutter, Ignaz; Wagner, Dorothea Optimal Orthogonal Graph Drawing with Convex Bend Costs. International Colloquium on Automata, Languages, and Programming (ICALP) 2013: 184195
Traditionally, the quality of orthogonal planar drawings is quantified by the total number of bends or the maximum number of bends per edge. However, this neglects that, in typical applications, edges have varying importance. We consider the problem OptimalFlexDraw that is defined as follows. Given a planar graph G on n vertices with maximum degree 4 (4planar graph) and for each edge e a cost function cost_e : N_0 → R defining costs depending on the number of bends e has, compute a planar orthogonal drawing of G of minimum cost. In this generality OptimalFlexDraw is NPhard. We show that it can be solved efficiently if (1) the cost function of each edge is convex and (2) the first bend on each edge does not cause any cost. Our algorithm takes time O(n, ⋅, T_flow(n) and O(n^2, ⋅, T_flow(n)) for biconnected and connected graphs, respectively, where T_flow(n) denotes the time to compute a minimumcost flow in a planar network with multiple sources and sinks. Our result is the first polynomialtime bendoptimization algorithm for general 4planar graphs optimizing over all embeddings. Previous work considers restricted graph classes and unit costs.

Angelini, Patrizio; Bläsius, Thomas; Rutter, Ignaz Testing Mutual Duality of Planar Graphs. International Symposium on Algorithms and Computation (ISAAC) 2013: 350360
We introduce and study the problem Mutual Planar Duality, which asks for planar graphs G_1 and G_2 whether G_1 can be embedded such that its dual is isomorphic to G_2. We show NPcompleteness for general graphs and give a lineartime algorithm for biconnected graphs. We consider the common dual relation ~, where G_1 ~ G_2 if and only they admit embeddings that result in the same dual graph. We show that ~ is an equivalence relation on the set of biconnected graphs and devise a succinct, SPQRtreelike representation of its equivalence classes. To solve Mutual Planar Duality for biconnected graphs, we show how to do isomorphism testing for two such representations in linear time. A special case of Mutual Planar Duality is testing whether a graph is selfdual. Our algorithm can handle the case of biconnected graphs in linear time and our NPhardness proof extends to selfduality and also to map selfduality testing (which additionally requires to preserve the embedding).

Sutton, Andrew M.; Chicano, Francisco; Whitley, L. Darrell Fitness Function Distributions over Generalized Search Neighborhoods in the \emphqary Hypercube. Evolutionary Computation 2013: 561590
The frequency distribution of a fitness function over regions of its domain is an important quantity for understanding the behavior of algorithms that employ randomized sampling to search the function. In general, exactly characterizing this distribution is at least as hard as the search problem, since the solutions typically live in the tails of the distribution. However, in some cases it is possible to efficiently retrieve a collection of quantities called moments that describe the distribution. In this paper, we consider functions of bounded epistasis that are defined over lengthn strings from a finite alphabet of cardinality q. Many problems in combinatorial optimization can be specified as search problems over functions of this type. Employing Fourier analysis of functions over finite groups, we derive an efficient method for computing the exact moments of the frequency distribution of fitness functions over Hamming regions of the qary hypercube. We then use this approach to derive equations that describe the expected fitness of the offspring of any point undergoing uniform mutation. The results we present provide insight into the statistical structure of the fitness function for a number of combinatorial problems. For the graph coloring problem, we apply our results to efficiently compute the average number of constraint violations that lie within a certain number of steps of any coloring. We derive an expression for the mutation rate that maximizes the expected fitness of an offspring at each fitness level. We also apply the results to the slightly more complex frequency assignment problem, a relevant application in the domain of the telecommunications industry. As with the graph coloring problem, we provide formulas for the average value of the fitness function in Hamming regions around a solution and the expectationoptimal mutation rate.

Albers, Susanne; Lenzner, Pascal On Approximate Nash Equilibria in Network Design. Internet Mathematics 2013: 384405
We study a basic network design game where n selfinterested agents, each having individual connectivity requirements, wish to build a network by purchasing links from a given set of edges. A fundamental cost sharing mechanism is Shapley cost sharing that splits the cost of an edge in a fair manner among the agents using the edge. In this paper we investigate if an optimal minimumcost network represents an attractive, relatively stable state that agents might want to purchase. We resort to the concept of αapproximate Nash equilibria. We prove that for single source games in undirected graphs, any optimal network represents an H(n)approximate Nash equilibrium, where H(n) is the nth Harmonic number. We show that this bound is tight. We extend the results to cooperative games, where agents may form coalitions, and to weighted games. In both cases we give tight or nearly tight lower and upper bounds on the stability of optimal solutions. Finally we show that in general sourcesink games and in directed graphs, minimumcost networks do not represent good states.

Nallaperuma, Samadhi; Sutton, Andrew M.; Neumann, Frank Fixedparameter evolutionary algorithms for the Euclidean Traveling Salesperson problem. Congress on Evolutionary Computation (CEC) 2013: 20372044
We contribute to the theoretical understanding of evolutionary algorithms and carry out a parameterized analysis of evolutionary algorithms for the Euclidean traveling salesperson problem (Euclidean TSP).We exploit structural properties related to the optimization process of evolutionary algorithms for this problem and use them to bound the runtime of evolutionary algorithms. Our analysis studies the runtime in dependence of the number of inner points k and shows that simple evolutionary algorithms solve the Euclidean TSP in expected time O(n^4k(2k  1)!). Moreover, we show that, under reasonable geometric constraints, a locally optimal 2opt tour can be found by randomized local search in expected time O(n^2k!).

Feldmann, Matthias; Kötzing, Timo Optimizing expected path lengths with ant colony optimization using fitness proportional update. Foundations of Genetic Algorithms (FOGA) 2013: 6574
We study the behavior of a MaxMin Ant System (MMAS) on the stochastic singledestination shortest path (SDSP) problem. Two previous papers already analyzed this setting for two slightly different MMAS algorithms, where the pheromone update fitnessindependently rewards edges of the bestsofar solution. The first paper showed that, when the bestsofar solution is not reevaluated and the stochastic nature of the edge weights is due to noise, the MMAS will find a tree of edges successfully and efficiently identify a shortest path tree with minimal noisefree weights. The second paper used reevaluation of the bestsofar solution and showed that the MMAS finds paths which beat any other path in direct comparisons, if existent. For both results, for some random variables, this corresponds to a tree with minimal expected weights. In this work we analyze a variant of MMAS that works with fitnessproportional update on stochasticweight graphs with arbitrary random edge weights from [0,1]. For δ such that any suboptimal path is worse by at least δ than an optimal path, then, with suitable parameters, the graph will be optimized after O(n^3 ln n/δ over δ^3) iterations (in expectation). In order to prove the above result, the multiplicative and the variable drift theorem are adapted to continuous search spaces.

Freydenberger, Dominik D.; Kötzing, Timo Fast learning of restricted regular expressions and DTDs. International Conference on Database Theory (ICDT) 2013: 4556
We study the problem of generalizing from a finite sample to a language taken from a predefined language class. The two language classes we consider are subsets of the regular languages and have significance in the specification of XML documents (the classes corresponding to so called chain regular expressions, Chares, and to single occurrence regular expressions, Sores). The previous literature gave a number of algorithms for generalizing to Sores providing a trade off between quality of the solution and speed. Furthermore, a fast but nonoptimal algorithm for generalizing to Chares is known. For each of the two language classes we give an efficient algorithm returning a minimal generalization from the given finite sample to an element of the fixed language class; such generalizations are called descriptive. In this sense, both our algorithms are optimal.

Bringmann, Karl; Friedrich, Tobias Approximation quality of the hypervolume indicator. Artificial Intelligence 2013: 265290
In order to allow a comparison of (otherwise incomparable) sets, many evolutionary multiobjective optimizers use indicator functions to guide the search and to evaluate the performance of search algorithms. The most widely used indicator is the hypervolume indicator. It measures the volume of the dominated portion of the objective space bounded from below by a reference point. Though the hypervolume indicator is very popular, it has not been shown that maximizing the hypervolume indicator of sets of bounded size is indeed equivalent to the overall objective of finding a good approximation of the Pareto front. To address this question, we compare the optimal approximation ratio with the approximation ratio achieved by twodimensional sets maximizing the hypervolume indicator. We bound the optimal multiplicative approximation ratio of n points by 1+Θ(1/n) for arbitrary Pareto fronts. Furthermore, we prove that the same asymptotic approximation ratio is achieved by sets of n points that maximize the hypervolume indicator. However, there is a provable gap between the two approximation ratios which is even exponential in the ratio between the largest and the smallest value of the front. We also examine the additive approximation ratio of the hypervolume indicator in two dimensions and prove that it achieves the optimal additive approximation ratio apart from a small ratio.

Bailly, Gilles; Oulasvirta, Antti; Kötzing, Timo; Hoppe, Sabrina MenuOptimizer: interactive optimization of menu systems. Symposium on User Interface Software and Technology (UIST) 2013: 331342
Menu systems are challenging to design because design spaces are immense, and several human factors affect user behavior. This paper contributes to the design of menus with the goal of interactively assisting designers with an optimizer in the loop. To reach this goal, 1) we extend a predictive model of user performance to account for expectations as to item groupings; 2) we adapt an ant colony optimizer that has been proven efficient for this class of problems; and 3) we present MenuOptimizer, a set of interactions integrated into a real interface design tool (QtDesigner). MenuOptimizer supports designers' abilities to cope with uncertainty and recognize good solutions. It allows designers to delegate combinatorial problems to the optimizer, which should solve them quickly enough without disrupting the design process. We show evidence that satisfactory menu designs can be produced for complex problems in minutes.

Bringmann, Karl; Friedrich, Tobias; Igel, Christian; Voß, Thomas Speeding up manyobjective optimization by Monte Carlo approximations. Artificial Intelligence 2013: 2229
Many stateoftheart evolutionary vector optimization algorithms compute the contributing hypervolume for ranking candidate solutions. However, with an increasing number of objectives, calculating the volumes becomes intractable. Therefore, although hypervolumebased algorithms are often the method of choice for bicriteria optimization, they are regarded as not suitable for manyobjective optimization. Recently, Monte Carlo methods have been derived and analyzed for approximating the contributing hypervolume. Turning theory into practice, we employ these results in the ranking procedure of the multiobjective covariance matrix adaptation evolution strategy (MOCMAES) as an example of a stateoftheart method for vector optimization. It is empirically shown that the approximation does not impair the quality of the obtained solutions given a budget of objective function evaluations, while considerably reducing the computation time in the case of multiple objectives. These results are obtained on common benchmark functions as well as on two design optimization tasks. Thus, employing Monte Carlo approximations makes hypervolumebased algorithms applicable to manyobjective optimization.

Benz, Florian; Kötzing, Timo An effective heuristic for the smallest grammar problem. Genetic and Evolutionary Computation Conference (GECCO) 2013: 487494
The smallest grammar problem is the problem of finding the smallest contextfree grammar that generates exactly one given sequence. Approximating the problem with a ratio of less than 8569/8568 is known to be NPhard. Most work on this problem has focused on finding decent solutions fast (mostly in linear time), rather than on good heuristic algorithms. Inspired by a new perspective on the problem presented by Carrascosa et al.\ (2010), we investigate the performance of different heuristics on the problem. The aim is to find a good solution on large instances by allowing more than linear time. We propose a hybrid of a maxmin ant system and a genetic algorithm that in combination with a novel local search outperforms the state of the art on all files of the Canterbury corpus, a standard benchmark suite. Furthermore, this hybrid performs well on a standard DNA corpus.

Kötzing, Timo; Neumann, Frank; Röglin, Heiko; Witt, Carsten Theoretical analysis of two ACO approaches for the traveling salesman problem. Swarm Intelligence 2012: 121
Bioinspired algorithms, such as evolutionary algorithms and ant colony optimization, are widely used for different combinatorial optimization problems. These algorithms rely heavily on the use of randomness and are hard to understand from a theoretical point of view. This paper contributes to the theoretical analysis of ant colony optimization and studies this type of algorithm on one of the most prominent combinatorial optimization problems, namely the traveling salesperson problem (TSP). We present a new construction graph and show that it has a stronger local property than one commonly used for constructing solutions of the TSP. The rigorous runtime analysis for two ant colony optimization algorithms, based on these two construction procedures, shows that they lead to good approximation in expected polynomial time on random instances. Furthermore, we point out in which situations our algorithms get trapped in local optima and show where the use of the right amount of heuristic information is provably beneficial.

Case, John; Kötzing, Timo Learning secrets interactively. Dynamic modeling in inductive inference. Information and Computation 2012: 6073
Introduced is a new inductive inference paradigm, dynamic modeling. Within this learning paradigm, for example, function h learns function g iff, in the ith iteration, h and g both produce output, h gets the sequence of all outputs from g in prior iterations as input, g gets all the outputs from h in prior iterations as input, and, from some iteration on, the sequence of hʼs outputs will be programs for the output sequence of g. Dynamic modeling provides an idealization of, for example, a social interaction in which h seeks to discover program models of gʼs behavior it sees in interacting with g, and h openly discloses to g its sequence of candidate program models to see what g says back. Sample results: every g can be so learned by some h; there are g that can only be learned by an h if g can also learn that h back; there are extremely secretive h which cannot be learned back by any g they learn, but which, nonetheless, succeed in learning infinitely many g; quadratic time learnability is strictly more powerful than linear time learnability. This latter result, as well as others, follows immediately from general correspondence theorems obtained from a unified approach to the paradigms within inductive inference. Many proofs, some sophisticated, employ machine selfreference, a.k.a., recursion theorems.

Kötzing, Timo; Molter, Hendrik ACO Beats EA on a Dynamic PseudoBoolean Function. International Conference on Parallel Problem Solving from Nature (PPSN) 2012: 113122
In this paper, we contribute to the understanding of the behavior of bioinspired algorithms when tracking the optimum of a dynamically changing fitness function over time. In particular, we are interested in the difference between a simple evolutionary algorithm (EA) and a simple ant colony optimization (ACO) system on deterministically changing fitness functions, which we call dynamic fitness patterns. Of course, the algorithms have no prior knowledge about the patterns. We construct a bit string optimization problem where we can show that the ACO system is able to follow the optimum while the EA gets lost.

Whitley, Darrell; Sutton, Andrew M. Genetic Algorithms  A Survey of Models and Methods. Handbook of Natural Computing 2012: 637671
This chapter first reviews the simple genetic algorithm. Mathematical models of the genetic algorithm are also reviewed, including the schema theorem, exact infinite population models, and exact Markov models for finite populations. The use of bit representations, including Gray encodings and binary encodings, is discussed. Selection, including roulette wheel selection, rankbased selection, and tournament selection, is also described. This chapter then reviews other forms of genetic algorithms, including the steadystate Genitor algorithm and the CHC (crossgenerational elitist selection, heterogenous recombination, and cataclysmic mutation) algorithm. Finally, landscape structures that can cause genetic algorithms to fail are looked at, and an application of genetic algorithms in the domain of resource scheduling, where genetic algorithms have been highly successful, is also presented.

Friedrich, Tobias; Gairing, Martin; Sauerwald, Thomas Quasirandom Load Balancing. SIAM Journal of Computing 2012: 747771
We propose a simple distributed algorithm for balancing indivisible tokens on graphs. The algorithm is completely deterministic, though it tries to imitate (and enhance) a randomized algorithm by keeping the accumulated rounding errors as small as possible. Our new algorithm, surprisingly, closely approximates the idealized process (where the tokens are divisible) on important network topologies. On ddimensional torus graphs with n nodes it deviates from the idealized process only by an additive constant. In contrast, the randomized rounding approach of Friedrich and Sauerwald [Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 121–130] can deviate up to Ω(polylog(n)), and the deterministic algorithm of Rabani, Sinclair, and Wanka [Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 1998, pp. 694–705] has a deviation of Ω(n^1/d). This makes our quasirandom algorithm the first known algorithm for this setting, which is optimal both in time and achieved smoothness. We further show that on the hypercube as well, our algorithm has a smaller deviation from the idealized process than the previous algorithms. To prove these results, we derive several combinatorial and probabilistic results that we believe to be of independent interest. In particular, we show that firstpassage probabilities of a random walk on a path with arbitrary weights can be expressed as a convolution of independent geometric probability distributions.

Sutton, Andrew M.; Day, Jareth; Neumann, Frank A parameterized runtime analysis of evolutionary algorithms for MAX2SAT. Genetic and Evolutionary Computation Conference (GECCO) 2012: 433440
We investigate the MAX2SAT problem and study evolutionary algorithms by parameterized runtime analysis. The parameterized runtime analysis of evolutionary algorithms has been initiated recently and reveals new insights into which type of instances of NPhard combinatorial optimization problems are hard to solve by evolutionary computing methods. We show that a variant of the (1+1) EA is a fixedparameter evolutionary algorithm with respect to the standard parameterization for MAX2SAT. Furthermore, we study how the dependencies between the variables affect problem difficulty and present fixedparameter evolutionary algorithms for the MAX(2,3)SAT problem where the studied parameter is the diameter of the variable graph.

Doerr, Benjamin; Hota, Ashish; Kötzing, Timo Ants easily solve stochastic shortest path problems. Genetic and Evolutionary Computation Conference (GECCO) 2012: 1724
The first rigorous theoretical analysis (Horoba, Sudholt (GECCO 2010)) of an ant colony optimizer for the stochastic shortest path problem suggests that ant system experience significant difficulties when the input data is prone to noise. In this work, we propose a slightly different ant optimizer to deal with noise. We prove that under mild conditions, it finds the paths with shortest expected length efficiently, despite the fact that we do not have convergence in the classic sense. To prove our results, we introduce a stronger drift theorem that can also deal with the situation that the progress is faster when one is closer to the goal.

Sutton, Andrew M.; Neumann, Frank A Parameterized Runtime Analysis of Simple Evolutionary Algorithms for Makespan Scheduling. Parallel Problem Solving from Nature (PPSN) 2012: 5261
We consider simple multistart evolutionary algorithms applied to the classical NPhard combinatorial optimization problem of Makespan Scheduling on two machines. We study the dependence of the runtime of this type of algorithm on three different key hardness parameters. By doing this, we provide further structural insights into the behavior of evolutionary algorithms for this classical problem.

Lenzner, Pascal Greedy Selfish Network Creation. Conference on Web and Internet Economics (WINE) 2012: 142155
We introduce and analyze greedy equilibria (GE) for the wellknown model of selfish network creation by Fabrikant et al.[PODC'03]. GE are interesting for two reasons: (1) they model outcomes found by agents which prefer smooth adaptations over radical strategychanges, (2) GE are outcomes found by agents which do not have enough computational resources to play optimally. In the model of Fabrikant et al. agents correspond to Internet Service Providers which buy network links to improve their quality of network usage. It is known that computing a best response in this model is NPhard. Hence, polytime agents are likely not to play optimally. But how good are networks created by such agents? We answer this question for very simple agents. Quite surprisingly, naive greedy play suffices to create remarkably stable networks. Specifically, we show that in the SUM version, where agents attempt to minimize their average distance to all other agents, GE capture Nash equilibria (NE) on trees and that any GE is in 3approximate NE on general networks. For the latter we also provide a lower bound of 3/2 on the approximation ratio. For the MAX version, where agents attempt to minimize their maximum distance, we show that any GEstar is in 2approximate NE and any GEtree having larger diameter is in 6/5approximate NE. Both bounds are tight. We contrast these positive results by providing a linear lower bound on the approximation ratio for the MAX version on general networks in GE. This result implies a locality gap of Ω(n) for the metric minmax facility location problem, where n is the number of clients.

Sutton, Andrew M.; Neumann, Frank A Parameterized Runtime Analysis of Evolutionary Algorithms for the Euclidean Traveling Salesperson Problem. Association for the Advancement of Artificial Intelligence (AAAI) 2012
Parameterized runtime analysis seeks to understand the influence of problem structure on algorithmic runtime. In this paper, we contribute to the theoretical understanding of evolutionary algorithms and carry out a parameterized analysis of evolutionary algorithms for the Euclidean traveling salesperson problem (Euclidean TSP). We investigate the structural properties in TSP instances that influence the optimization process of evolutionary algorithms and use this information to bound the runtime of simple evolutionary algorithms. Our analysis studies the runtime in dependence of the number of inner points k and shows that (μ+λ) evolutionary algorithms solve the Euclidean TSP in expected time O((μ/λ)⋅n^3 γ(ϵ)+nγ(ϵ)+(μ/λ)⋅n^4k(2k−1)!) where γ is a function of the minimum angle ϵ between any three points. Finally, our analysis provides insights into designing a mutation operator that improves the upper bound on expected runtime. We show that a mixed mutation strategy that incorporates both 2opt moves and permutation jumps results in an upper bound of O((μ/λ)⋅n^3γ(ϵ)+nγ(ϵ)+(μ/λ)⋅n^2k(k−1)!) for the (μ+λ) EA.

Doerr, Benjamin; Fouz, Mahmoud; Friedrich, Tobias Experimental Analysis of Rumor Spreading in Social Networks. Mediterranean Conference on Algorithms (MedAlg) 2012: 159173
Randomized rumor spreading was recently shown to be a very efficient mechanism to spread information in preferential attachment networks. Most interesting from the algorithm design point of view was the observation that the asymptotic runtime drops when memory is used to avoid recontacting neighbors within a small number of rounds. In this experimental investigation, we confirm that a small amount of memory indeed reduces the runtime of the protocol even for small network sizes. We observe that one memory cell per node suffices to reduce the runtime significantly; more memory helps comparably little. Aside from extremely sparse graphs, preferential attachment graphs perform faster than all other graph classes examined. This holds independent of the amount of memory, but preferential attachment graphs benefit the most from the use of memory. We also analyze the influence of the network density and the size of the memory. For the asynchronous version of the rumor spreading protocol, we observe that the theoretically predicted asymptotic advantage of preferential attachment graphs is smaller than expected. There are other topologies which benefit even more from asynchrony. We complement our findings on artificial network models by the corresponding experiments on crawls of popular online social networks, where again we observe extremely rapid information dissemination and a sizable benefit from using memory and asynchrony.

Sutton, Andrew M.; Whitley, L. Darrell; Howe, Adele E. Computing the moments of kbounded pseudoBoolean functions over Hamming spheres of arbitrary radius in polynomial time. Theoretical Computer Science 2012: 5874
We show that given a kbounded pseudoBoolean function f, one can always compute the cth moment of f over regions of arbitrary radius in Hamming space in polynomial time using algebraic information from the adjacency structure (where k and c are constants). This result has implications for evolutionary algorithms and local search algorithms because information about promising regions of the search space can be efficiently retrieved, even if the cardinality of the region is exponential in the problem size. Finally, we use our results to introduce a method of efficiently calculating the expected fitness of mutations for evolutionary algorithms.

Kötzing, Timo; Sutton, Andrew M.; Neumann, Frank; O'Reilly, UnaMay The max problem revisited: the importance of mutation in genetic programming. Genetic and Evolutionary Computation Conference (GECCO) 2012: 13331340
This paper contributes to the rigorous understanding of genetic programming algorithms by providing runtime complexity analyses of the wellstudied Max problem. Several experimental studies have indicated that it is hard to solve the Max problem with crossoverbased algorithms. Our analyses show that different variants of the Max problem can provably be solved using simple mutationbased genetic programming algorithms. Our results advance the body of computational complexity analyses of genetic programming, indicate the importance of mutation in genetic programming, and reveal new insights into the behavior of mutationbased genetic programming algorithms.

Jain, Sanjay; Kötzing, Timo; Stephan, Frank Enlarging Learnable Classes. International Conference on Algorithmic Learning Theory (ALT) 2012: 3650
An early result in inductive inference shows that the class of Exlearnable sets is not closed under unions. In this paper we are interested in the following question: For what classes of functions is the union with an arbitrary Exlearnable class again Exlearnable, either effectively (in an index for a learner of an Exlearnable class) or noneffectively? We show that the effective case and the noneffective case separate, and we give a sufficient criterion for the effective case. Furthermore, we extend our notions to considering unions with classes of single functions, as well as to other learning criteria, such as finite learning and behaviorally correct learning. Furthermore, we consider the possibility of (effectively) extending learners to learn (infinitely) more functions. It is known that all Exlearners learning a dense set of functions can be effectively extended to learn infinitely more. It was open whether the learners learning a nondense set of functions can be similarly extended. We show that this is not possible, but we give an alternative split of all possible learners into two sets such that, for each of the sets, all learners from that set can be effectively extended. We analyze similar concepts also for other learning criteria.

Baumbach, Jan; Friedrich, Tobias; Kötzing, Timo; Krohmer, Anton; Müller, Joachim; Pauling, Josch Efficient algorithms for extracting biological key pathways with global constraints. Genetic and Evolutionary Computation Conference (GECCO) 2012: 169176
The integrated analysis of data of different types and with various interdependencies is one of the major challenges in computational biology. Recently, we developed KeyPathwayMiner, a method that combines biological networks modeled as graphs with diseasespecific genetic expression data gained from a set of cases (patients, cell lines, tissues, etc.). We aimed for finding all maximal connected subgraphs where all nodes but $K$ are expressed in all cases but at most $L$, i.e. key pathways. Thereby, we combined biological networks with OMICS data, instead of analyzing these data sets in isolation. Here we present an alternative approach that avoids a certain bias towards hub nodes: We now aim for extracting all maximal connected subnetworks where all but at most $K$ nodes are expressed in all cases but in total (!) at most $L$, i.e. accumulated over all cases and all nodes in a solution. We call this strategy GLONE (global node exceptions); the previous problem we call INES (individual node exceptions). Since finding GLONEcomponents is computationally hard, we developed an Ant Colony Optimization algorithm and implemented it with the KeyPathwayMiner Cytoscape framework as an alternative to the INES algorithms. KeyPathwayMiner 3.0 now offers both the INES and the GLONE algorithms. It is available as plugin from Cytoscape and online at http://keypathwayminer.mpiinf.mpg.de.

Doerr, Benjamin; Fouz, Mahmoud; Friedrich, Tobias Why rumors spread so quickly in social networks. Communications of the ACM 2012: 7075
Understanding structural and algorithmic properties of complex networks is an important task, not least because of the huge impact of the internet. Our focus is to analyze how news spreads in social networks. We simulate a simple information spreading process in different network topologies and demonstrate that news spreads much faster in existing social network topologies. We support this finding by analyzing information spreading in the mathematically defined preferential attachment network topology, which is a common model for realworld networks. We prove that here a sublogarithmic time suffices to spread a news to all nodes of the network. All previously studied network topologies need at least a logarithmic time. Surprisingly, we observe that nodes with few neighbors are crucial for the fast dissemination. Social networks like Facebook and Twitter are reshaping the way people take collective actions. They have played a crucial role in the recent uprisings of the ‘Arab Spring’ and the ‘London riots’. It has been argued that the ‘instantaneous nature’ of these networks influenced the speed at which the events were unfolding [4]. It is quite remarkable that social networks spread news so fast. Both the structure of social networks and the process that distributes the news are not designed with this purpose in mind. On the contrary, they are not designed at all, but have evolved in a random and decentralized manner. So is our view correct that social networks ease the spread of information (“rumors”), and if so, what particular properties of social networks are the reason for this? To answer these questions, we simulate a simple rumor spreading process on several graphs having the structure of existing large social networks. We see, for example, that a rumor started at a random node of the Twitter network in average reaches 45.6 million of the total of 51.2 million members within only eight rounds of communication. We also analyze this process on an abstract model of social networks, the socalled preferential attachment graphs introduced by Baraba ́si and Albert [3]. In [17], we obtain a mathematical proof that rumors in such networks spread much faster than in many other network topologies—even faster than in networks having a communication link between any two nodes (complete graphs). As an explanation, we observe that nodes of small degree build a shortcut between those having large degree (hubs), which due to their large number of possible communication partners less often talk to each other directly.

Bringmann, Karl; Friedrich, Tobias Approximating the least hypervolume contributor: NPhard in general, but fast in practice. Theoretical Computer Science (TCS) 2012: 104116
The hypervolume indicator is an increasingly popular set measure to compare the quality of two Pareto sets. The basic ingredient of most hypervolume indicator based optimization algorithms is the calculation of the hypervolume contribution of single solutions regarding a Pareto set. We show that exact calculation of the hypervolume contribution is #Phard while its approximation is NPhard. The same holds for the calculation of the minimal contribution. We also prove that it is NPhard to decide whether a solution has the least hypervolume contribution. Even deciding whether the contribution of a solution is at most (1 + ε) times the minimal contribution is NPhard. This implies that it is neither possible to efficiently find the least contributing solution (unless P = NP) nor to approximate it (unless NP = BPP). Nevertheless, in the second part of the paper we present a very fast approximation algorithm for this problem. We prove that for arbitrarily given ε,δ> 0 it calculates a solution with contribution at most (1 + ε) times the minimal contribution with probability at least (1 − δ). Though it cannot run in polynomial time for all instances, it performs extremely fast on various benchmark datasets. The algorithm solves very large problem instances which are intractable for exact algorithms (e.g., 10000 solutions in 100 dimensions) within a few seconds.

Bringmann, Karl; Friedrich, Tobias Convergence of hypervolumebased archiving algorithms ii: competitiveness. Genetic and Evolutionary Computation Conference (GECCO) 2012: 457464
We study the convergence behavior of (μ+λ)archiving algorithms. A (μ+λ)archiving algorithm defines how to choose in each generation μ children from μ parents and λ offspring together. Archiving algorithms have to choose individuals online without knowing future offspring. Previous studies assumed the offspring generation to be bestcase. We assume the initial population and the offspring generation to be worstcase and use the competitive ratio to measure how much smaller hypervolumes an archiving algorithm finds due to not knowing the future in advance. We prove that all archiving algorithms which increase the hypervolume in each step (if they can) are only μcompetitive. We also present a new archiving algorithm which is (4+2/μ)competitive. This algorithm not only achieves a constant competitive ratio, but is also efficiently computable. Both properties provably do not hold for the commonly used greedy archiving algorithms, for example those used in SIBEA, SMSEMOA, or the generational MOCMAES.

Friedrich, Tobias; Krohmer, Anton Parameterized Clique on ScaleFree Networks. International Symposium on Algorithms and Computation (ISAAC) 2012: 659668
Finding cliques in graphs is a classical problem which is in general NPhard and parameterized intractable. However, in typical applications like social networks or proteinprotein interaction networks, the considered graphs are scalefree, i.e., their degree sequence follows a power law. Their specific structure can be algorithmically exploited and makes it possible to solve clique much more efficiently. We prove that on inhomogeneous random graphs with n nodes and power law exponent γ, cliques of size k can be found in time O(n^2) for γ ≥ 3 and in time O(n exp(k^4)) for 2 < γ < 3.

Heinz, Jeffrey; Kasprzik, Anna; Kötzing, Timo Learning in the limit with latticestructured hypothesis spaces. Theoretical Computer Science (TCS) 2012: 111127
We define a collection of language classes which are TxtExlearnable (learnable in the limit from positive data). The learners map any data input to an element of a fixed lattice, and keep the least upper bound of all lattice elements thus obtained as the current hypothesis. Each element of the lattice is a grammar for a language, and the learner climbs the lattice searching for the right element. We call these classes in our collection lattice classes. We provide several characterizations of lattice classes and their learners, which suggests they are very natural. In particular, we show that any class of languages is a lattice class iff it is TxtExlearnable consistently, conservatively, setdrivenly, and strongly monotonically. We show several language classes previously discussed in the literature to be lattice classes, including the locally ktestable classes, the piecewise ktestable classes, the kreversible languages and the pattern languages. We also show that lattice classes contain three previously known collections of language classes: string extension language classes, functiondistinguishable language classes, and closedset systems. Finally, the lattice perspective helps analyze the learning of these classes. Illustrations include querylearning results in dependence on the lattice structure, characterizations of closure properties and the VCdimension of lattice classes in terms of lattice properties.

Berghammer, Rudolf; Friedrich, Tobias; Neumann, Frank Convergence of setbased multiobjective optimization, indicators and deteriorative cycles. Theoretical Computer Science 2012: 217
Multiobjective optimization deals with the task of computing a set of solutions that represents possible tradeoffs with respect to a given set of objective functions. Setbased approaches such as evolutionary algorithms are very popular for solving multiobjective optimization problems. Convergence of setbased approaches for multiobjective optimization is essential for their success. We take an ordertheoretic view on the convergence of setbased multiobjective optimization and examine how the use of indicator functions can help to direct the search towards Pareto optimal sets. In doing so, we point out that setbased multiobjective optimization working on the dominance relation of search points has to deal with a cyclic behavior that may lead to worsening with respect to the Paretodominance relation defined on sets. Later on, we show in which situations wellknown binary and unary indicators can help to avoid this cyclic behavior and therefore guarantee convergence of the algorithm. We also study the impact of deteriorative cycles on the runtime behavior and give an example in which they provably slow down the optimization process.

Alcaraz, Nicolas; Friedrich, Tobias; Kötzing, Timo; Krohmer, Anton; Müller, Joachim; Pauling, Josch; Baumbach, Jan Efficient Key Pathway Mining: Combining Networks and OMICS Data. Integrative Biology 2012: 756764
Systems biology has emerged over the last decade. Driven by the advances in sophisticated measurement technology the research community generated huge molecular biology data sets. This comprises rather static data on the interplay of biological entities, for instance proteinprotein interaction network data, as well as quite dynamic data collected for studying the behavior of individual cells or tissues in accordance to changing environmental conditions, such as DNA microarrays or RNA sequencing. Here we bring the two different data types together in order to gain higher level knowledge. We introduce a significantly improved version of the KeyPathwayMiner software framework. Given a biological network modelled as graph and a set of expression studies, KeyPathwayMiner efficiently finds and visualizes connected subnetworks where most components are expressed in most cases. It finds all maximal connected subnetworks where all nodes but k exceptions are expressed in all experimental studies but at least l exceptions. We demonstrate the power of the new approach by comparing it to similar approaches with gene expression data previously used to study Huntington’s disease. In addition, we demonstrate KeyPathwayMiner’s flexibility and applicability to nonarray data by analyzing genomescale DNA methylation profiles from colorectal tumor cancer patients. KeyPathwayMiner release 2 is available as a Cytoscape plugin and online at http://keypathwayminer.mpiinf.mpg.de.

Baumbach, Jan; Friedrich, Tobias; Kötzing, Timo; Krohmer, Anton; Müller, Joachim; Pauling, Josch Efficient Algorithms for Extracting Biological Key Pathways with Global Constraints. Genetic and Evolutionary Computation Conference (GECCO) 2012: 169176
The integrated analysis of data of different types and with various interdependencies is one of the major challenges in computational biology. Recently, we developed KeyPathwayMiner, a method that combines biological networks modeled as graphs with diseasespecific genetic expression data gained from a set of cases (patients, cell lines, tis sues, etc.). We aimed for finding all maximal connected subgraphs where all nodes but K are expressed in all cases but at most L, i.e. key pathways. Thereby, we combined biological networks with OMICS data, instead of analyzing these data sets in isolation. Here we present an alternative approach that avoids a certain bias towards hub nodes: We now aim for extracting all maximal connected subnetworks where all but at most K nodes are expressed in all cases but in total (!) at most L, i.e. accumulated over all cases and all nodes in a solution. We call this strategy GLONE (global node exceptions); the previous problem we call INES (individual node exceptions). Since finding GLONEcomponents is computationally hard, we developed an Ant Colony Optimization algorithm and implemented it with the KeyPathwayMiner Cytoscape framework as an alternative to the INES algorithms. KeyPathwayMiner 3.0 now offers both the INES and the GLONE algorithms. It is available as plugin from Cytoscape and online at http://keypathwayminer.mpiinf.mpg.de.

Doerr, Benjamin; Fouz, Mahmoud; Friedrich, Tobias Asynchronous Rumor Spreading in Preferential Attachment Graphs. Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) 2012: 307315
We show that the asynchronous pushpull protocol spreads rumors in preferential attachment graphs (as defined by Barabási and Albert) in time O(√logn) to all but a lower order fraction of the nodes with high probability. This is significantly faster than what synchronized protocols can achieve; an obvious lower bound for these is the average distance, which is known to be Θ(logn/loglogn).

Croitoru, Cosmina; Kötzing, Timo Deliberative Acceptability of Arguments. Starting AI Researcher Symposium (STAIRS) 2012: 7182
State of the art extension based argument acceptance is currently biased toward attacks: while the defending extension of an argument a is internally coherent, no such requirement is imposed on its attacking set. On the other hand, if we restrict ourselves only to conflictfree sets of attacking arguments, then we could have different attacking sets for a specified argument a (any two conflicting attackers of a must belong to different a's attacking sets). Having only one defending extension for all these attacking sets would contradict the deliberative nature of argumentation in the real world, where only the coherent sets of attacks matter and the defending sets of arguments depend on the former. In this paper we introduce a new type of acceptability of an argument, in which its attacking and defending sets of arguments are uniformly treated. We call it deliberative acceptance, discuss how this and the classical acceptance notions interrelate and analyze its computational properties. In particular, we prove that the corresponding decision problem is Π^P_2complete, but its restrictions on bipartite or cochordal argumentation frameworks are in P.

Case, John; Kötzing, Timo Measuring Learning Complexity with Criteria Epitomizers. Symposium on Theoretical Aspects of Computer Science (STACS) 2011: 320331
In prior papers, beginning with the seminal work by Freivalds et al. 1995, the notion of intrinsic complexity is used to analyze the learning complexity of sets of functions in a Goldstyle learning setting. Herein are pointed out some weaknesses of this notion. Offered is an alternative based on epitomizing sets of functions  sets, which are learnable under a given learning criterion, but not under other criteria which are not at least as powerful. To capture the idea of epitomizing sets, new reducibility notions are given based on robust learning (closure of learning under certain classes of operators). Various degrees of epitomizing sets are characterized as the sets complete with respect to corresponding reducibility notions! These characterizations also provide an easy method for showing sets to be epitomizers, and they are, then, employed to prove several sets to be epitomizing. Furthermore, a scheme is provided to generate easily very strong epitomizers for a multitude of learning criteria. These strong epitomizers are socalled selflearning sets, previously applied by Case & Koetzing, 2010. These strong epitomizers can be generated and employed in a myriad of settings to witness the strict separation in learning power between the criteria so epitomized and other not as powerful criteria!

Bringmann, Karl; Friedrich, Tobias Convergence of hypervolumebased archiving algorithms I: effectiveness. GECCO 2011: 745752
The core of hypervolumebased multiobjective evolutionary algorithms is an archiving algorithm which performs the environmental selection. A (μ+λ)archiving algorithm defines how to choose μ children from μ parents and λ offspring together. We study theoretically (μ+λ)archiving algorithms which never decrease the hypervolume from one generation to the next. Zitzler, Thiele, and Bader (IEEE Trans. Evolutionary Computation, 14:5879, 2010) proved that all (μ+1)archiving algorithms are ineffective, which means there is an initial population such that independent of the used reproduction rule, a set with maximum hypervolume cannot be reached. We extend this and prove that for λ<μ all archiving algorithms are ineffective. On the other hand, locally optimal algorithms, which maximize the hypervolume in each step, are effective for λ=μ and can always find a population with hypervolume at least half the optimum for λ < μ. We also prove that there is no hypervolumebased archiving algorithm which can always find a population with hypervolume greater than 1 / (1 + 0.1338, ( 1/λ  1/μ) ) times the optimum.

Sutton, Andrew M.; Whitley, Darrell; Howe, Adele E. Mutation rates of the (1+1)EA on pseudoboolean functions of bounded epistasis. Genetic and Evolutionary Computation Conference (GECCO) 2011: 973980
When the epistasis of the fitness function is bounded by a constant, we show that the expected fitness of an offspring of the (1+1)EA can be efficiently computed for any point. Moreover, we show that, for any point, it is always possible to efficiently retrieve the "best" mutation rate at that point in the sense that the expected fitness of the resulting offspring is maximized. On linear functions, it has been shown that a mutation rate of 1/n is provably optimal. On functions where epistasis is bounded by a constant k, we show that for sufficiently high fitness, the commonly used mutation rate of 1/n is also best, at least in terms of maximizing the expected fitness of the offspring. However, we find for certain ranges of the fitness function, a better mutation rate can be considerably higher, and can be found by solving for the real roots of a degreek polynomial whose coefficients contain the nonzero Walsh coefficients of the fitness function. Simulation results on maximum ksatisfiability problems and NKlandscapes show that this expectationmaximized mutation rate can cause significant gains early in search.

Kötzing, Timo; Neumann, Frank; Spöhel, Reto PAC learning and genetic programming. Genetic and Evolutionary Computation Conference (GECCO) 2011: 20912096
Genetic programming (GP) is a very successful type of learning algorithm that is hard to understand from a theoretical point of view. With this paper we contribute to the computational complexity analysis of genetic programming that has been started recently. We analyze GP in the wellknown PAC learning framework and point out how it can observe quality changes in the the evolution of functions by random sampling. This leads to computational complexity bounds for a linear GP algorithm for perfectly learning any member of a simple class of linear pseudoBoolean functions. Furthermore, we show that the same algorithm on the functions from the same class finds good approximations of the target function in less time.

Friedrich, Tobias; Hebbinghaus, Nils Average update times for fullydynamic allpairs shortest paths. Discrete Applied Mathematics 2011: 17511758
We study the fullydynamic all pairs shortest path problem for graphs with arbitrary nonnegative edge weights. It is known for digraphs that an update of the distance matrix costs O(n^2.75) worstcase time [Thorup, STOC ’05] and O(n^2)amortized time [Demetrescu and Italiano, J.ACM ’04] where n is the number of vertices. We present the first averagecase analysis of the undirected problem. For a random update we show that the expected time per update is bounded by O(n^4/3 + ε) for all ε> 0.

Lenzner, Pascal On Dynamics in Basic Network Creation Games. International Symposium on Algorithmic Game Theory (SAGT) 2011: 254265
We initiate the study of game dynamics in the Sum Basic Network Creation Game, which was recently introduced by Alon et al.[SPAA’10]. In this game players are associated to vertices in a graph and are allowed to “swap” edges, that is to remove an incident edge and insert a new incident edge. By performing such moves, every player tries to minimize her connection cost, which is the sum of distances to all other vertices. When played on a tree, we prove that this game admits an ordinal potential function, which implies guaranteed convergence to a pure Nash Equilibrium. We show a cubic upper bound on the number of steps needed for any improving response dynamic to converge to a stable tree and propose and analyse a best response dynamic, where the players having the highest cost are allowed to move. For this dynamic we show an almost tight linear upper bound for the convergence speed. Furthermore, we contrast these positive results by showing that, when played on general graphs, this game allows best response cycles. This implies that there cannot exist an ordinal potential function and that fundamentally different techniques are required for analysing this case. For computing a best response we show a similar contrast: On the one hand we give a lineartime algorithm for computing a best response on trees even if players are allowed to swap multiple edges at a time. On the other hand we prove that this task is NPhard even on simple general graphs, if more than one edge can be swapped at a time. The latter addresses a proposal by Alon et al..

Friedrich, Tobias; Sauerwald, Thomas; Stauffer, Alexandre Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions. International Symposium on Algorithms and Computation (ISAAC) 2011: 190199
A random geometric graph (RGG) is defined by placing n points uniformly at random in [0,n^1/d]^d, and joining two points by an edge whenever their Euclidean distance is at most some fixed r. We assume that r is larger than the critical value for the emergence of a connected component with Ω(n) nodes. We show that, with high probability (w.h.p.), for any two connected nodes with a Euclidean distance of ω(logn/r^d−1), their graph distance is only a constant factor larger than their Euclidean distance. This implies that the diameter of the largest connected component is Θ(n^1/d/r) w.h.p. We also prove that the condition on the Euclidean distance above is essentially tight. We also analyze the following randomized broadcast algorithm on RGGs. At the beginning, only one node from the largest connected component of the RGG is informed. Then, in each round, each informed node chooses a neighbor independently and uniformly at random and informs it. We prove that w.h.p. this algorithm informs every node in the largest connected component of an RGG within Θ(n^1/d/r+logn) rounds.

Friedrich, Tobias; Kroeger, Trent; Neumann, Frank Weighted Preferences in Evolutionary Multiobjective Optimization. Australasian Conference on Artificial Intelligence (AUSAI) 2011: 291300
Evolutionary algorithms have been widely used to tackle multiobjective optimization problems. Incorporating preference information into the search of evolutionary algorithms for multiobjective optimization is of great importance as it allows one to focus on interesting regions in the objective space. Zitzler et al. have shown how to use a weight distribution function on the objective space to incorporate preference information into hypervolumebased algorithms. We show that this weighted information can easily be used in other popular EMO algorithms as well. Our results for NSGAII and SPEA2 show that this yields similar results to the hypervolume approach and requires less computational effort.

Doerr, Benjamin; Fouz, Mahmoud; Friedrich, Tobias Social networks spread rumors in sublogarithmic time. Symposium on Theory of Computing (STOC) 2011: 2130
With the prevalence of social networks, it has become increasingly important to understand their features and limitations. It has been observed that information spreads extremely fast in social networks. We study the performance of randomized rumor spreading protocols on graphs in the preferential attachment model. The wellknown random phone call model of Karp et al. (FOCS 2000) is a pushpull strategy where in each round, each vertex chooses a random neighbor and exchanges information with it. We prove the following.  The pushpull strategy delivers a message to all nodes within Θ(log n) rounds with high probability. The best known bound so far was O(log^2 n).  If we slightly modify the protocol so that contacts are chosen uniformly from all neighbors but the one contacted in the previous round, then this time reduces to Θ(log n / log log n), which is the diameter of the graph. This is the first time that a sublogarithmic broadcast time is proven for a natural setting. Also, this is the first time that avoiding doublecontacts reduces the runtime to a smaller order of magnitude.

Friedrich, Tobias; Sauerwald, Thomas; Vilenchik, Dan Smoothed analysis of balancing networks. Random Structures and Algorithms 2011: 115138
In a balancing network each processor has an initial collection of unitsize jobs (tokens) and in each round, pairs of processors connected by balancers split their load as evenly as possible. An excess token (if any) is placed according to some predefined rule. As it turns out, this rule crucially affects the performance of the network. In this work we propose a model that studies this effect. We suggest a model bridging the uniformlyrandom assignment rule, and the arbitrary one (in the spirit of smoothedanalysis). We start with an arbitrary assignment of balancer directions and then flip each assignment with probability α independently. For a large class of balancing networks our result implies that after O(log n) rounds the discrepancy is O((1/2 − α) log n + log log n) with high probability. This matches and generalizes known upper bounds for α = 0 and α = 1/2. We also show that a natural network matches the upper bound for any α.

Bringmann, Karl; Friedrich, Tobias; Neumann, Frank; Wagner, Markus ApproximationGuided Evolutionary MultiObjective Optimization. International Joint Conference on Artificial Intelligence (IJCAI) 2011: 11981203
Multiobjective optimization problems arise frequently in applications but can often only be solved approximately by heuristic approaches. Evolutionary algorithms have been widely used to tackle multiobjective problems. These algorithms use different measures to ensure diversity in the objective space but are not guided by a formal notion of approximation. We present a new framework of an evolutionary algorithm for multiobjective optimization that allows to work with a formal notion of approximation. Our experimental results show that our approach outperforms stateoftheart evolutionary algorithms in terms of the quality of the approximation that is obtained in particular for problems with many objectives.

Doerr, Benjamin; Lengler, Johannes; Kötzing, Timo; Winzen, Carola Blackbox complexities of combinatorial problems. Genetic and Evolutionary Computation Conference (GECCO) 2011: 981988
Blackbox complexity is a complexity theoretic measure for how difficult a problem is to be optimized by a general purpose optimization algorithm. It is thus one of the few means trying to understand which problems are tractable for genetic algorithms and other randomized search heuristics. Most previous work on blackbox complexity is on artificial test functions. In this paper, we move a step forward and give a detailed analysis for the two combinatorial problems minimum spanning tree and singlesource shortest paths. Besides giving interesting bounds for their blackbox complexities, our work reveals that the choice of how to model the optimization problem is nontrivial here. This in particular comes true where the search space does not consist of bit strings and where a reasonable definition of unbiasedness has to be agreed on.

Fellows, Michael R.; Friedrich, Tobias; Hermelin, Danny; Narodytska, Nina; Rosamond, Frances A. Constraint Satisfaction Problems: Convexity Makes AllDifferent Constraints Tractable. International Joint Conference on Artificial Intelligence (IJCAI) 2011: 522527
We examine the complexity of constraint satisfaction problems that consist of a set of AllDiff constraints. Such CSPs naturally model a wide range of realworld and combinatorial problems, like scheduling, frequency allocations, and graph coloring problems. As this problem is known to be NPcomplete, we investigate under which further assumptions it becomes tractable. We observe that a crucial property seems to be the convexity of the variable domains and constraints. Our main contribution is an extensive study of the complexity of Multiple AllDiff CSPs for a set of natural parameters, like maximum domain size and maximum size of the constraint scopes. We show that, depending on the parameter, convexity can make the problem tractable even though it is provably intractable in general. Interestingly, the convexity of constraints is the key property in achieving fixed parameter tractability, while the convexity of domains does not usually make the problem easier.

Kötzing, Timo; Sudholt, Dirk; Theile, Madeleine How crossover helps in pseudoboolean optimization. Genetic and Evolutionary Computation Conference (GECCO) 2011: 989996
Understanding the impact of crossover on performance is a major problem in the theory of genetic algorithms (GAs). We present new insight on working principles of crossover by analyzing the performance of crossoverbased GAs on the simple functions OneMax and Jump. First, we assess the potential speedup by crossover when combined with a fitnessinvariant bit shuffling operator that simulates a lineage of independent evolution on a function of unitation. Theoretical and empirical results show drastic speedups for both functions. Second, we consider a simple GA without shuffling and investigate the interplay of mutation and crossover on Jump. If the crossover probability is small, subsequent mutations create sufficient diversity, even for very small populations. Contrarily, with high crossover probabilities crossover tends to lose diversity more quickly than mutation can create it. This has a drastic impact on the performance on Jump. We complement our theoretical findings by Monte Carlo simulations on the population diversity.

Doerr, Benjamin; Johannsen, Daniel; Kötzing, Timo; Lehre, Per Kristian; Wagner, Markus; Winzen, Carola Faster blackbox algorithms through higher arity operators. Foundations of Genetic Algorithms (FOGA) 2011: 163172
We extend the work of Lehre and Witt (GECCO 2010) on the unbiased blackbox model by considering higher arity variation operators. In particular, we show that already for binary operators the blackbox complexity of LeadingOnes drops from Θ(n2) for unary operators to O(n log n). For OneMax, the Ω(n log n) unary blackbox complexity drops to O(n) in the binary case. For kary operators, k ≤ n, the OneMaxcomplexity further decreases to O(n / log k).

Friedrich, Tobias; Bringmann, Karl; Voß, Thomas; Igel, Christian The logarithmic hypervolume indicator. Foundations of Genetic Algorithms (FOGA) 2011: 8192
It was recently proven that sets of points maximizing the hypervolume indicator do not give a good multiplicative approximation of the Pareto front. We introduce a new "logarithmic hypervolume indicator" and prove that it achieves a closetooptimal multiplicative approximation ratio. This is experimentally verified on several benchmark functions by comparing the approximation quality of the multiobjective covariance matrix evolution strategy (MOCMAES) with the classic hypervolume indicator and the MOCMAES with the logarithmic hypervolume indicator.

Sutton, Andrew M.; Whitley, Darrell; Howe, Adele E. Approximating the distribution of fitness over hamming regions. Foundations of Genetic Algorithms (FOGA) 2011: 93104
The distribution of fitness values across a set of states sharply influences the dynamics of evolutionary processes and heuristic search in combinatorial optimization. In this paper we present a method for approximating the distribution of fitness values over Hamming regions by solving a linear programming problem that incorporates low order moments of the target function. These moments can be retrieved in polynomial time for select problems such as MAXkSAT using Walsh analysis. The method is applicable to any real function on binary strings that is epistatically bounded and discrete with asymptotic bounds on the cardinality of its codomain. We perform several studies on the ONEMAX and MAXkSAT domains to assess the accuracy of the approximation and its dependence on various factors. We show that the approximation can accurately predict the number of states within a Hamming region that have an improving fitness value.

Doerr, Benjamin; Kötzing, Timo; Winzen, Carola Too fast unbiased blackbox algorithms. Genetic and Evolutionary Computation Conference (GECCO) 2011: 20432050
Unbiased blackbox complexity was recently introduced as a refined complexity model for randomized search heuristics (Lehre and Witt, GECCO 2010). For several problems, this notion avoids the unrealistically low complexity results given by the classical model of Droste, Jansen, and Wegener (Theor. Comput. Sci. 2006). In this work, we show that for two natural problems the unbiased blackbox complexity remains artificially small. For the classical JumpK test function class and for a subclass of the wellknown Partition problem, we give mutationonly unbiased blackbox algorithms having complexity O(n log n). Since the first problem usually needs Θ(n^k) function evaluations to be optimized by standard heuristics and the second is even NPcomplete, these blackbox complexities seem not to indicate the true difficulty of the two problems for randomized search heuristics.

Friedrich, Tobias; Levine, Lionel Fast Simulation of LargeScale Growth Models. Approximation Algorithms for Combinatorial Optimization (APPROX) 2011: 555566
We give an algorithm that computes the final state of certain growth models without computing all intermediate states. Our technique is based on a “least action principle” which characterizes the odometer function of the growth process. Starting from an approximation for the odometer, we successively correct under and overestimates and provably arrive at the correct final state. The degree of speedup depends on the accuracy of the initial guess. Determining the size of the boundary fluctuations in growth models like internal diffusionlimited aggregation (IDLA) is a longstanding open problem in statistical physics. As an application of our method, we calculate the size of fluctuations over two orders of magnitude beyond previous simulations.

Kötzing, Timo; Neumann, Frank; Sudholt, Dirk; Wagner, Markus Simple maxmin ant systems and the optimization of linear pseudoboolean functions. Foundations of Genetic Algorithms (FOGA) 2011: 209218
With this paper, we contribute to the understanding of ant colony optimization (ACO) algorithms by formally analyzing their runtime behavior. We study simple MAXMIN ant systems on the class of linear pseudoBoolean functions defined on binary strings of length n. Our investigations point out how the progress according to function values is stored in the pheromones. We provide a general upper bound of O((n^3 log n)ρ) on the running time for two ACO variants on all linear functions, where ρ determines the pheromone update strength. Furthermore, we show improved bounds for two wellknown linear pseudoBoolean functions called ONEMAX and BINVAL and give additional insights using an experimental study.

Antoniadis, Antonios; Hüffner, Falk; Lenzner, Pascal; Moldenhauer, Carsten; Souza, Alexander Balanced Interval Coloring. International Symposium on Theoretical Aspects of Computer Science (STACS) 2011: 531542
We consider the discrepancy problem of coloring n intervals with k colors such that at each point on the line, the maximal difference between the number of intervals of any two colors is minimal. Somewhat surprisingly, a coloring with maximal difference at most one always exists. Furthermore, we give an algorithm with running time O(n log n + kn log k) for its construction. This is in particular interesting because many known results for discrepancy problems are nonconstructive. This problem naturally models a load balancing scenario, where $n$~tasks with given start and endtimes have to be distributed among $k$~servers. Our results imply that this can be done ideally balanced. When generalizing to $d$dimensional boxes (instead of intervals), a solution with difference at most one is not always possible. We show that for any d >= 2 and any k >= 2 it is NPcomplete to decide if such a solution exists, which implies also NPhardness of the respective minimization problem. In an online scenario, where intervals arrive over time and the color has to be decided upon arrival, the maximal difference in the size of color classes can become arbitrarily high for any online algorithm.

Berenbrink, Petra; Cooper, Colin; Friedetzky, Tom; Friedrich, Tobias; Sauerwald, Thomas Randomized Diffusion for Indivisible Loads. Symposium on Discrete Algorithms (SODA) 2011: 429439
We present a new randomized diffusionbased algorithm for balancing indivisible tasks (tokens) on a network. Our aim is to minimize the discrepancy between the maximum and minimum load. The algorithm works as follows. Every vertex distributes its tokens as evenly as possible among its neighbors and itself. If this is not possible without splitting some tokens, the vertex redistributes its excess tokens among all its neighbors randomly (without replacement). In this paper we prove several upper bounds on the load discrepancy for general networks. These bounds depend on some expansion properties of the network, that is, the second largest eigenvalue, and a novel measure which we refer to as refined local divergence. We then apply these general bounds to obtain results for some specific networks. For constantdegree expanders and torus graphs, these yield exponential improvements on the discrepancy bounds compared to the algorithm of Rabani, Sinclair, and Wanka [14]. For hypercubes we obtain a polynomial improvement. In contrast to previous papers, our algorithm is vertexbased and not edgebased. This means excess tokens are assigned to vertices instead to edges, and the vertex reallocates all of its excess tokens by itself. This approach avoids nodes having "negative loads" (like in [8, 10]), but causes additional dependencies for the analysis.

Doerr, Benjamin; Johannsen, Daniel; Kötzing, Timo; Neumann, Frank; Theile, Madeleine More Effective Crossover Operators for the AllPairs Shortest Path Problem. International Conference on Parallel Problem Solving from Nature (PPSN) 2010: 184193
The allpairs shortest path problem is the first nonartificial problem for which it was shown that adding crossover can significantly speed up a mutationonly evolutionary algorithm. Recently, the analysis of this algorithm was refined and it was shown to have an expected optimization time (w.r.t. the number of fitness evaluations) of Θ(n^3.25(logn)^0.25). In contrast to this simple algorithm, evolutionary algorithms used in practice usually employ refined recombination strategies in order to avoid the creation of infeasible offspring. We study extensions of the basic algorithm by two such concepts which are central in recombination, namely \emphrepair mechanisms and \emphparent selection. We show that repairing infeasible offspring leads to an improved expected optimization time of O(n^3.2(logn)^0.2). As a second part of our study we prove that choosing parents that guarantee feasible offspring results in an even better optimization time of O(n^3logn). Both results show that already simple adjustments of the recombination operator can asymptotically improve the runtime of evolutionary algorithms.

Case, John; Kötzing, Timo Solutions to Open Questions for NonUShaped Learning with Memory Limitations. Algorithmic Learning Theory (ALT) 2010: 285299
A Ushape occurs when a learner first learns, then unlearns, and, finally, relearns, some target concept. Within the framework of Inductive Inference, previous results have shown, for example, that Ushapes are unnecessary for explanatory learning, but are necessary for behaviorally correct learning. This paper solves the following two problems regarding nonUshaped learning posed in the prior literature. First, it is shown that there are classes learnable with three memory states that are not learnable nonUshapedly with any finite number of memory states. This result is surprising, as for learning with one or two memory states, Ushapes are known to be unnecessary. Secondly, it is shown that there is a class learnable memorylessly with a single feedback query such that this class is not learnable nonUshapedly memorylessly with any finite number of feedback queries. This result is complemented by the result that any class of infinite languages learnable memorylessly with finitely many feedback queries is so learnable without Ushapes – in fact, all classes of infinite languages learnable with complete memory are learnable memorylessly with finitely many feedback queries and without Ushapes. On the other hand, we show that there is a class of infinite languages learnable memorylessly with a single feedback query, which is not learnable without Ushapes by any particular bounded number of feedback queries.

Backes, Michael; Ciobotaru, Oana; Krohmer, Anton RatFish: A File Sharing Protocol Provably Secure against Rational Users. European Symposium on Research in Computer Security (ESORICS) 2010: 607625
The proliferation of P2P computing has recently been propelled by popular applications, most notably file sharing protocols such as BitTorrent. These protocols provide remarkable efficiency and scalability, as well as adaptivity to dynamic situations. However, none of them is secure against attacks from rational users, i.e., users that misuse the protocol if doing so increases their benefits (e.g., reduces download time or amount of upload capacity). We propose a rigorous model of rational file sharing for both seeders and leechers, building upon the concept of rational cryptography. We design a novel file sharing protocol called RatFish, and we formally prove that no rational party has an incentive to deviate from RatFish; i.e., RatFish constitutes a Nash equilibrium. Compared to existing file sharing protocols such as BitTorrent, the tracker in RatFish is assigned additional tasks while the communication overhead of a RatFish client is kept to a minimum. We demonstrate by means of a prototype implementation that RatFish is practical and efficient.

Friedrich, Tobias; Gairing, Martin; Sauerwald, Thomas Quasirandom Load Balancing. Symposium on Discrete Algorithms (SODA) 2010: 16201629
We propose a simple distributed algorithm for balancing indivisible tokens on graphs. The algorithm is completely deterministic, though it tries to imitate (and enhance) a randomized algorithm by keeping the accumulated rounding errors as small as possible. Our new algorithm, surprisingly, closely approximates the idealized process (where the tokens are divisible) on important network topologies. On ddimensional torus graphs with n nodes it deviates from the idealized process only by an additive constant. In contrast, the randomized rounding approach of Friedrich and Sauerwald [Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 121–130] can deviate up to Ω(polylog(n)), and the deterministic algorithm of Rabani, Sinclair, and Wanka [Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 1998, pp. 694–705] has a deviation of Ω(n^1/d). This makes our quasirandom algorithm the first known algorithm for this setting, which is optimal both in time and achieved smoothness. We further show that on the hypercube as well, our algorithm has a smaller deviation from the idealized process than the previous algorithms. To prove these results, we derive several combinatorial and probabilistic results that we believe to be of independent interest. In particular, we show that firstpassage probabilities of a random walk on a path with arbitrary weights can be expressed as a convolution of independent geometric probability distributions.

Bringmann, Karl; Friedrich, Tobias An Efficient Algorithm for Computing Hypervolume Contributions. Evolutionary Computation 2010: 383402
The hypervolume indicator serves as a sorting criterion in many recent multiobjective evolutionary algorithms (MOEAs). Typical algorithms remove the solution with the smallest loss with respect to the dominated hypervolume from the population. We present a new algorithm which determines for a population of size n with d objectives, a solution with minimal hypervolume contribution in time O(n^d/2 log n) for d > 2. This improves all previously published algorithms by a factor of n for all d > 3 and by a factor of √n for d = 3. We also analyze hypervolume indicator based optimization algorithms which remove λ > 1 solutions from a population of size n = μ + λ. We show that there are populations such that the hypervolume contribution of iteratively chosen λ solutions is much larger than the hypervolume contribution of an optimal set of λ solutions. Selecting the optimal set of λ solutions implies calculating (n over μ) conventional hypervolume contributions, which is considered to be computationally too expensive. We present the first hypervolume algorithm which directly calculates the contribution of every set of λ solutions. This gives an additive term of (n over μ) in the runtime of the calculation instead of a multiplicative factor of (n over μ). More precisely, for a population of size n with d objectives, our algorithm can calculate a set of λ solutions with minimal hypervolume contribution in time O(n^d/2 log n + n^λ) for d > 2. This improves all previously published algorithms by a factor of n^minλ,d/2 for d > 3 and by a factor of n for d = 3.

Friedrich, Tobias; He, Jun; Hebbinghaus, Nils; Neumann, Frank; Witt, Carsten Approximating Covering Problems by Randomized Search Heuristics Using MultiObjective Models. Evolutionary Computation 2010: 617633
The main aim of randomized search heuristics is to produce good approximations of optimal solutions within a small amount of time. In contrast to numerous experimental results, there are only a few theoretical explorations on this subject. We consider the approximation ability of randomized search heuristics for the class of covering problems and compare singleobjective and multiobjective models for such problems. For the VertexCover problem, we point out situations where the multiobjective model leads to a fast construction of optimal solutions while in the singleobjective case, no good approximation can be achieved within the expected polynomial time. Examining the more general SetCover problem, we show that optimal solutions can be approximated within a logarithmic factor of the size of the ground set, using the multiobjective approach, while the approximation quality obtainable by the singleobjective approach in expected polynomial time may be arbitrarily bad.

Case, John; Kötzing, Timo Strongly NonUShaped Learning Results by General Techniques. Conference On Learning Theory (COLT) 2010: 181193
In learning, a semantic or behavioral Ushape occurs when a learner first learns, then unlearns, and, finally, relearns, some target concept (on the way to success). Within the framework of Inductive Inference, previous results have shown, for example, that such Ushapes are unnecessary for explanatory learning, but are necessary for behaviorally correct and nontrivial vacillatory learning. Herein we focus more on syntactic Ushapes. This paper introduces two general techniques and applies them especially to syntactic Ushapes in learning: one technique to show when they are necessary and one to show when they are unnecessary. The technique for the former is very general and applicable to a much wider range of learning criteria. It employs socalled selflearning classes of languages which are shown to characterize completely one criterion learning more than another. We apply these techniques to show that, for setdriven and partially setdriven learning, any kind of Ushapes are unnecessary. Furthermore, we show that Ushapes are not unnecessary in a strong way for iterative learning, contrasting an earlier result by Case and Moelius that semantic Ushapes are unnecessary for iterative learning.