
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.

Kötzing, Timo; Molter, Hendrik ACO Beats EA on a Dynamic PseudoBoolean Function. 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.

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 Barabasi and Albert) in time \(O(\sqrt\log n})\) 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 \(\Theta(\log n / \log\log n)\).

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.

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.

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.

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.

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 \((\mu+\lambda)\)archiving algorithms. A \((\mu+\lambda)\)archiving algorithm defines how to choose in each generation \(\mu\) children from \(\mu\) parents and \(\lambda\) 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 \(\mu\)competitive. We also present a new archiving algorithm which is \((4+2/\mu)\)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.

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. 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.

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 \(\gamma\), cliques of size \(k\) can be found in time \(O(n^2)\) for \(\gamma \ge 3\) and in time \(O(n, exp(k^4))\) for \(2<\gamma <3\).

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 \(\Omega(n)\) for the metric minmax facility location problem, where \(n\) is the number of clients.

Bläsius, Thomas; Rutter, Ignaz Disconnectivity and Relative Positions in Simultaneous Embeddings. Graph Drawing (GD) 2012: 3142
For two planar graphs \(G^1 = (V^1, E^1)\) and \(G^2 = ( V^2, E^2) \) sharing a common subgraph \(G = G^1 \cap 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)\) .

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 \(\Pi^P_2\)complete, but its restrictions on bipartite or cochordal argumentation frameworks are in \(P\).

Sutton, Andrew M.; Neumann, Frank A Parameterized Runtime Analysis of Evolutionary Algorithms for the Euclidean Traveling Salesperson Problem. Conference on 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 \((\mu + \lambda)\) evolutionary algorithms solve the Euclidean TSP in expected time \(O((\mu / \lambda) cdot n^3 \gamma(\epsilon) + n \gamma(\epsilon)+(\mu / \lambda) cdot n^4k(2k1)!)\) where \(\gamma\) is a function of the minimum angle \(epsilon\) 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((\mu / \lambda) cdot n^3 \gamma(\epsilon) + n \gamma(\epsilon) + (\mu / \lambda) cdot n^2k(k1)!)\) for the \((\mu + \lambda)\) EA.