2012

Sutton, Andrew M.; Neumann, Frank A Parameterized Runtime Analysis of Evolutionary Algorithms for the Euclidean Traveling Salesperson ProblemConference on Artificial Intelligence (AAAI) 2012
[ Abstract ] [ BibTeX ] [ Download ]
 
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(2k-1)!)\) 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 2-opt 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(k-1)!)\) for the \((\mu + \lambda)\) EA.
@inproceedings{DBLP:conf/aaai/SuttonN12, abstract = {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}(2k-1)!)\) 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 2-opt 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}(k-1)!)\) for the \((\mu + \lambda)\) EA.}, author = {Sutton, Andrew M. and Neumann, Frank}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {aaai andrewmsutton frankneumann imported year2012}, publisher = {{AAAI} Press}, title = {A Parameterized Runtime Analysis of Evolutionary Algorithms for the Euclidean Traveling Salesperson Problem}, year = 2012 }

Jain, Sanjay; Kötzing, Timo; Stephan, Frank Enlarging Learnable ClassesAlgorithmic Learning Theory (ALT) 2012: 36–50
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
An early result in inductive inference shows that the class of Ex-learnable 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 Ex-learnable class again Ex-learnable, either effectively (in an index for a learner of an Ex-learnable class) or non-effectively? We show that the effective case and the non-effective 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 Ex-learners learning a dense set of functions can be effectively extended to learn infinitely more. It was open whether the learners learning a non-dense 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.
@inproceedings{DBLP:conf/alt/JainKS12, abstract = {An early result in inductive inference shows that the class of Ex-learnable 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 Ex-learnable class again Ex-learnable, either effectively (in an index for a learner of an Ex-learnable class) or non-effectively? We show that the effective case and the non-effective 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 Ex-learners learning a dense set of functions can be effectively extended to learn infinitely more. It was open whether the learners learning a non-dense 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.}, author = {Jain, Sanjay and Kötzing, Timo and Stephan, Frank}, booktitle = {Algorithmic Learning Theory (ALT)}, keywords = {imported timokoetzing year2012}, pages = {36-50}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Enlarging Learnable Classes}, volume = 7568, year = 2012 }

Bläsius, Thomas; Rutter, Ignaz Disconnectivity and Relative Positions in Simultaneous EmbeddingsGraph Drawing (GD) 2012: 31–42
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
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 CC-tree which represents all embeddings of \(G\) that extend to planar embeddings of \(G^1\). We show that CC-trees can be computed in linear time, and that their intersection is again a CC-tree. This yields a linear-time algorithm for SEFE if all k input graphs (possibly \(k > 2\)) pairwise share the same set of disjoint cycles. These results, including the CC-tree, 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)\) .
@inproceedings{DBLP:conf/gd/BlasiusR12, abstract = {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 CC-tree which represents all embeddings of \(G\) that extend to planar embeddings of \(G^1\). We show that CC-trees can be computed in linear time, and that their intersection is again a CC-tree. This yields a linear-time algorithm for SEFE if all k input graphs (possibly \(k > 2\)) pairwise share the same set of disjoint cycles. These results, including the CC-tree, 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)\) .}, author = {Bläsius, Thomas and Rutter, Ignaz}, booktitle = {Graph Drawing (GD)}, keywords = {gd thomasblaesius year2012}, pages = {31-42}, title = {Disconnectivity and Relative Positions in Simultaneous Embeddings}, year = 2012 }

Doerr, Benjamin; Hota, Ashish; Kötzing, Timo Ants easily solve stochastic shortest path problemsGenetic and Evolutionary Computation Conference (GECCO) 2012: 17–24
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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.
@inproceedings{DBLP:conf/gecco/DoerrHK12, abstract = {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.}, author = {Doerr, Benjamin and Hota, Ashish and Kötzing, Timo}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {gecco imported timokoetzing year2012}, pages = {17-24}, title = {Ants easily solve stochastic shortest path problems}, year = 2012 }

Baumbach, Jan; Friedrich, Tobias; Kötzing, Timo; Krohmer, Anton; Müller, Joachim; Pauling, Josch Efficient Algorithms for Extracting Biological Key Pathways with Global ConstraintsGenetic and Evolutionary Computation Conference (GECCO) 2012: 169–176
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
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 disease-specific genetic expression data gained from a set of cases (patients, cell lines, tissues, etc.). We aimed for finding all maximal connected sub-graphs 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 sub-networks 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 GLONE-components 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.mpi-inf.mpg.de.
@inproceedings{DBLP:conf/gecco/BaumbachFKKMP12, abstract = {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 disease-specific genetic expression data gained from a set of cases (patients, cell lines, tissues, etc.). We aimed for finding all maximal connected sub-graphs 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 sub-networks 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 GLONE-components 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.mpi-inf.mpg.de.}, author = {Baumbach, Jan and Friedrich, Tobias and Kötzing, Timo and Krohmer, Anton and Müller, Joachim and Pauling, Josch}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {ACO antonkrohmer gecco timokoetzing tobiasfriedrich year2012}, pages = {169-176}, title = {Efficient Algorithms for Extracting Biological Key Pathways with Global Constraints}, year = 2012 }

Sutton, Andrew M.; Day, Jareth; Neumann, Frank A parameterized runtime analysis of evolutionary algorithms for MAX-2-SATGenetic and Evolutionary Computation Conference (GECCO) 2012: 433–440
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We investigate the MAX-2-SAT 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 NP-hard combinatorial optimization problems are hard to solve by evolutionary computing methods. We show that a variant of the (1+1) EA is a fixed-parameter evolutionary algorithm with respect to the standard parameterization for MAX-2-SAT. Furthermore, we study how the dependencies between the variables affect problem difficulty and present fixed-parameter evolutionary algorithms for the MAX-(2,3)-SAT problem where the studied parameter is the diameter of the variable graph.
@inproceedings{DBLP:conf/gecco/SuttonDN12, abstract = {We investigate the MAX-2-SAT 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 NP-hard combinatorial optimization problems are hard to solve by evolutionary computing methods. We show that a variant of the (1+1) EA is a fixed-parameter evolutionary algorithm with respect to the standard parameterization for MAX-2-SAT. Furthermore, we study how the dependencies between the variables affect problem difficulty and present fixed-parameter evolutionary algorithms for the MAX-(2,3)-SAT problem where the studied parameter is the diameter of the variable graph.}, author = {Sutton, Andrew M. and Day, Jareth and Neumann, Frank}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {andrewmsutton frankneumann gecco imported jarethday year2012}, pages = {433-440}, publisher = {{ACM}}, title = {A parameterized runtime analysis of evolutionary algorithms for MAX-2-SAT}, year = 2012 }

Bringmann, Karl; Friedrich, Tobias Convergence of hypervolume-based archiving algorithms ii: competitivenessGenetic and Evolutionary Computation Conference (GECCO) 2012: 457–464
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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 best-case. We assume the initial population and the offspring generation to be worst-case 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, SMS-EMOA, or the generational MO-CMA-ES.
@inproceedings{DBLP:conf/gecco/BringmannF12, abstract = {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 best-case. We assume the initial population and the offspring generation to be worst-case 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, SMS-EMOA, or the generational MO-CMA-ES.}, author = {Bringmann, Karl and Friedrich, Tobias}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {gecco imported tobiasfriedrich year2012}, pages = {457-464}, title = {Convergence of hypervolume-based archiving algorithms ii: competitiveness}, year = 2012 }

Kötzing, Timo; Sutton, Andrew M.; Neumann, Frank; O’Reilly, Una-May The max problem revisited: the importance of mutation in genetic programmingGenetic and Evolutionary Computation Conference (GECCO) 2012: 1333–1340
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
This paper contributes to the rigorous understanding of genetic programming algorithms by providing runtime complexity analyses of the well-studied Max problem. Several experimental studies have indicated that it is hard to solve the Max problem with crossover-based algorithms. Our analyses show that different variants of the Max problem can provably be solved using simple mutation-based 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 mutation-based genetic programming algorithms.
@inproceedings{DBLP:conf/gecco/KotzingSNO12, abstract = {This paper contributes to the rigorous understanding of genetic programming algorithms by providing runtime complexity analyses of the well-studied Max problem. Several experimental studies have indicated that it is hard to solve the Max problem with crossover-based algorithms. Our analyses show that different variants of the Max problem can provably be solved using simple mutation-based 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 mutation-based genetic programming algorithms.}, author = {Kötzing, Timo and Sutton, Andrew M. and Neumann, Frank and O'Reilly, Una-May}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {andrewmsutton frankneumann gecco imported timokoetzing unamayoreilly year2012}, pages = {1333-1340}, title = {The max problem revisited: the importance of mutation in genetic programming}, year = 2012 }

Friedrich, Tobias; Krohmer, Anton Parameterized Clique on Scale-Free NetworksInternational Symposium on Algorithms and Computation (ISAAC) 2012: 659–668
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Finding cliques in graphs is a classical problem which is in general NP-hard and parameterized intractable. However, in typical applications like social networks or protein-protein interaction networks, the considered graphs are scale-free, 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\).
@inproceedings{DBLP:conf/isaac/FriedrichK12, abstract = {Finding cliques in graphs is a classical problem which is in general NP-hard and parameterized intractable. However, in typical applications like social networks or protein-protein interaction networks, the considered graphs are scale-free, 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\).}, author = {Friedrich, Tobias and Krohmer, Anton}, booktitle = {International Symposium on Algorithms and Computation (ISAAC)}, keywords = {antonkrohmer imported isaac tobiasfriedrich year2012}, pages = {659-668}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Parameterized Clique on Scale-Free Networks}, volume = 7676, year = 2012 }

Doerr, Benjamin; Fouz, Mahmoud; Friedrich, Tobias Experimental Analysis of Rumor Spreading in Social NetworksMediterranean Conference on Algorithms (MedAlg) 2012: 159–173
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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 run-time drops when memory is used to avoid re-contacting neighbors within a small number of rounds. In this experimental investigation, we confirm that a small amount of memory indeed reduces the run-time of the protocol even for small network sizes. We observe that one memory cell per node suffices to reduce the run-time 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.
@inproceedings{DBLP:conf/medalg/DoerrFF12, abstract = {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 run-time drops when memory is used to avoid re-contacting neighbors within a small number of rounds. In this experimental investigation, we confirm that a small amount of memory indeed reduces the run-time of the protocol even for small network sizes. We observe that one memory cell per node suffices to reduce the run-time 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.}, author = {Doerr, Benjamin and Fouz, Mahmoud and Friedrich, Tobias}, booktitle = {Mediterranean Conference on Algorithms (MedAlg)}, keywords = {imported medalg tobiasfriedrich year2012}, pages = {159-173}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Experimental Analysis of Rumor Spreading in Social Networks}, volume = 7659, year = 2012 }

Sutton, Andrew M.; Neumann, Frank A Parameterized Runtime Analysis of Simple Evolutionary Algorithms for Makespan SchedulingParallel Problem Solving from Nature (PPSN) 2012: 52–61
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We consider simple multi-start evolutionary algorithms applied to the classical NP-hard 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.
@inproceedings{DBLP:conf/ppsn/SuttonN12, abstract = {We consider simple multi-start evolutionary algorithms applied to the classical NP-hard 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.}, author = {Sutton, Andrew M. and Neumann, Frank}, booktitle = {Parallel Problem Solving from Nature (PPSN)}, keywords = {andrewmsutton frankneumann imported ppsn year2012}, pages = {52-61}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {A Parameterized Runtime Analysis of Simple Evolutionary Algorithms for Makespan Scheduling}, volume = 7491, year = 2012 }

Kötzing, Timo; Molter, Hendrik ACO Beats EA on a Dynamic Pseudo-Boolean FunctionParallel Problem Solving from Nature (PPSN) 2012: 113–122
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
In this paper, we contribute to the understanding of the behavior of bio-inspired 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.
@inproceedings{DBLP:conf/ppsn/KotzingM12, abstract = {In this paper, we contribute to the understanding of the behavior of bio-inspired 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.}, author = {Kötzing, Timo and Molter, Hendrik}, booktitle = {Parallel Problem Solving from Nature (PPSN)}, keywords = {imported timokoetzing year2012}, pages = {113-122}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {ACO Beats EA on a Dynamic Pseudo-Boolean Function}, volume = 7491, year = 2012 }

Croitoru, Cosmina; Kötzing, Timo Deliberative Acceptability of ArgumentsStarting AI Researcher Symposium (STAIRS) 2012: 71–82
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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 conflict-free 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 co-chordal argumentation frameworks are in \(P\).
@inproceedings{DBLP:conf/stairs/Croitoruo12, abstract = {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 conflict-free 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 co-chordal argumentation frameworks are in \(P\).}, author = {Croitoru, Cosmina and Kötzing, Timo}, booktitle = {Starting AI Researcher Symposium (STAIRS)}, keywords = {imported timokoetzing year2012}, pages = {71-82}, publisher = {{IOS} Press}, series = {Frontiers in Artificial Intelligence and Applications}, title = {Deliberative Acceptability of Arguments}, volume = 241, year = 2012 }

Doerr, Benjamin; Fouz, Mahmoud; Friedrich, Tobias Asynchronous Rumor Spreading in Preferential Attachment GraphsScandinavian Symposium and Workshops on Algorithm Theory (SWAT) 2012: 307–315
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We show that the asynchronous push-pull 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)\).
@inproceedings{DBLP:conf/swat/DoerrFF12, abstract = {We show that the asynchronous push-pull 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)\).}, author = {Doerr, Benjamin and Fouz, Mahmoud and Friedrich, Tobias}, booktitle = {Scandinavian Symposium and Workshops on Algorithm Theory (SWAT)}, keywords = {imported swat tobiasfriedrich year2012}, pages = {307-315}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Asynchronous Rumor Spreading in Preferential Attachment Graphs}, volume = 7357, year = 2012 }

Lenzner, Pascal Greedy Selfish Network CreationWeb and Internet Economics (WINE) 2012: 142–155
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We introduce and analyze greedy equilibria (GE) for the well-known 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 strategy-changes, (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 NP-hard. Hence, poly-time 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 3-approximate 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 GE-star is in 2-approximate NE and any GE-tree having larger diameter is in 6/5-approximate 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 min-max facility location problem, where \(n\) is the number of clients.
@inproceedings{DBLP:conf/wine/Lenzner12, abstract = {We introduce and analyze greedy equilibria (GE) for the well-known 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 strategy-changes, (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 NP-hard. Hence, poly-time 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 3-approximate 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 GE-star is in 2-approximate NE and any GE-tree having larger diameter is in 6/5-approximate 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 min-max facility location problem, where \(n\) is the number of clients.}, author = {Lenzner, Pascal}, booktitle = {Web and Internet Economics (WINE)}, keywords = {imported pascallenzner wine year2012}, pages = {142-155}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Greedy Selfish Network Creation}, volume = 7695, year = 2012 }

2012

Doerr, Benjamin; Fouz, Mahmoud; Friedrich, Tobias Why rumors spread so quickly in social networksCommunications of the ACM 2012: 70–75
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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 real-world 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 so-called 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 short-cut between those having large degree (hubs), which due to their large number of possible communication partners less often talk to each other directly.
@article{DBLP:journals/cacm/DoerrFF12, abstract = {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 real-world 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 so-called 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 short-cut between those having large degree (hubs), which due to their large number of possible communication partners less often talk to each other directly.}, author = {Doerr, Benjamin and Fouz, Mahmoud and Friedrich, Tobias}, journal = {Communications of the ACM}, keywords = {cacm imported tobiasfriedrich year2012}, number = 6, pages = {70-75}, title = {Why rumors spread so quickly in social networks}, volume = 55, year = 2012 }

Case, John; Kötzing, Timo Learning secrets interactively. Dynamic modeling in inductive inferenceInformation and Computation 2012: 60–73
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Introduced is a new inductive inference paradigm, dynamic modeling. Within this learning paradigm, for example, function \(h\) learns function \(g\) iff, in the \(i\)-th 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 self-reference, a.k.a., recursion theorems.
@article{DBLP:journals/iandc/CaseK12, abstract = {Introduced is a new inductive inference paradigm, dynamic modeling. Within this learning paradigm, for example, function \(h\) learns function \(g\) iff, in the \(i\)-th 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 self-reference, a.k.a., recursion theorems.}, author = {Case, John and Kötzing, Timo}, journal = {Information and Computation}, keywords = {iandc imported timokoetzing year2012}, pages = {60-73}, title = {Learning secrets interactively. Dynamic modeling in inductive inference}, volume = 220, year = 2012 }

Alcaraz, Nicolas; Friedrich, Tobias; Kötzing, Timo; Krohmer, Anton; Müller, Joachim; Pauling, Josch; Baumbach, Jan Efficient Key Pathway Mining: Combining Networks and OMICS DataIntegrative Biology 2012: 756–764
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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 protein-protein 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 sub-networks where most components are expressed in most cases. It finds all maximal connected sub-networks 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 non-array data by analyzing genome-scale DNA methylation profiles from colorectal tumor cancer patients. KeyPathwayMiner release 2 is available as a Cytoscape plugin and online at http://keypathwayminer.mpi-inf.mpg.de.
@article{alcaraz2012efficient, abstract = {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 protein-protein 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 sub-networks where most components are expressed in most cases. It finds all maximal connected sub-networks 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 non-array data by analyzing genome-scale DNA methylation profiles from colorectal tumor cancer patients. KeyPathwayMiner release 2 is available as a Cytoscape plugin and online at http://keypathwayminer.mpi-inf.mpg.de.}, author = {Alcaraz, Nicolas and Friedrich, Tobias and Kötzing, Timo and Krohmer, Anton and Müller, Joachim and Pauling, Josch and Baumbach, Jan}, journal = {Integrative Biology}, keywords = {ACO antonkrohmer timokoetzing tobiasfriedrich year2012}, number = 7, pages = {756-764}, title = {Efficient Key Pathway Mining: Combining Networks and OMICS Data}, volume = 4, year = 2012 }

Case, John; Kötzing, Timo Computability-Theoretic Learning ComplexityPhilosophical Transactions of the Royal Society A 2012: 3570–3596
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Initially discussed are some of Alan Turing's wonderfully profound and influential ideas about mind and mechanism-including regarding their connection to the main topic of the present study, which is within the field of computability-theoretic learning theory. Herein is investigated the part of this field concerned with the algorithmic, trial-and-error inference of eventually correct programs for functions from their data points. As to the main content of this study: in prior papers, beginning with the seminal work by Freivalds et al. in 1995, the notion of intrinsic complexity is used to analyse the learning complexity of sets of functions in a Gold-style learning setting. Herein are pointed out some weaknesses of this notion. Offered is an alternative based on epitomizing sets of functions-sets that are learnable under a given learning criterion, but not under other criteria that 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 sets of computable 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 the so-called self-learning sets, previously applied by Case & Kötzing in 2010. These strong epitomizers can be easily generated and employed in a myriad of settings to witness with certainty the strict separation in learning power between the criteria so epitomized and other not as powerful criteria!
@article{Cas-Koe:j:12:royal, abstract = {Initially discussed are some of Alan Turing's wonderfully profound and influential ideas about mind and mechanism-including regarding their connection to the main topic of the present study, which is within the field of computability-theoretic learning theory. Herein is investigated the part of this field concerned with the algorithmic, trial-and-error inference of eventually correct programs for functions from their data points. As to the main content of this study: in prior papers, beginning with the seminal work by Freivalds et al. in 1995, the notion of intrinsic complexity is used to analyse the learning complexity of sets of functions in a Gold-style learning setting. Herein are pointed out some weaknesses of this notion. Offered is an alternative based on epitomizing sets of functions-sets that are learnable under a given learning criterion, but not under other criteria that 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 sets of computable 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 the so-called self-learning sets, previously applied by Case \& Kötzing in 2010. These strong epitomizers can be easily generated and employed in a myriad of settings to witness with certainty the strict separation in learning power between the criteria so epitomized and other not as powerful criteria!}, author = {Case, John and Kötzing, Timo}, journal = {Philosophical Transactions of the Royal Society A}, keywords = {timokoetzing year2012}, pages = {3570-3596}, title = {Computability-Theoretic Learning Complexity}, volume = 370, year = 2012 }

Friedrich, Tobias; Gairing, Martin; Sauerwald, Thomas Quasirandom Load BalancingSIAM Journal on Computing 2012: 747–771
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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 \(d\)-dimensional 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 \(\Omega(\text{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 \(\Omega(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 first-passage probabilities of a random walk on a path with arbitrary weights can be expressed as a convolution of independent geometric probability distributions.
@article{DBLP:journals/siamcomp/FriedrichGS12, abstract = {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 \(d\)-dimensional 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 \(\Omega(\text{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 \(\Omega(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 first-passage probabilities of a random walk on a path with arbitrary weights can be expressed as a convolution of independent geometric probability distributions.}, author = {Friedrich, Tobias and Gairing, Martin and Sauerwald, Thomas}, journal = {SIAM Journal on Computing}, keywords = {imported sicomp tobiasfriedrich year2012}, number = 4, pages = {747-771}, publisher = {SIAM}, title = {Quasirandom Load Balancing}, volume = 41, year = 2012 }

Kötzing, Timo; Neumann, Frank; Röglin, Heiko; Witt, Carsten Theoretical analysis of two ACO approaches for the traveling salesman problemSwarm Intelligence 2012: 1–21
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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.
@article{DBLP:journals/swarm/KotzingNRW12, abstract = {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.}, author = {Kötzing, Timo and Neumann, Frank and Röglin, Heiko and Witt, Carsten}, journal = {Swarm Intelligence}, keywords = {carstenwitt frankneumann heikoroeglin imported swarm timokoetzing year2012}, number = 1, pages = {1-21}, title = {Theoretical analysis of two ACO approaches for the traveling salesman problem}, volume = 6, year = 2012 }

Berghammer, Rudolf; Friedrich, Tobias; Neumann, Frank Convergence of Set-Based Multi-Objective Optimization, Indicators and Deteriorative CyclesTheoretical Computer Science 2012: 2–17
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Multi-objective optimization deals with the task of computing a set of solutions that represents possible trade-offs with respect to a given set of objective functions. Set-based approaches such as evolutionary algorithms are very popular for solving multi-objective optimization problems. Convergence of set-based approaches for multi-objective optimization is essential for their success. We take an order-theoretic view on the convergence of set-based multi-objective 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 set-based multi-objective 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 Pareto-dominance relation defined on sets. Later on, we show in which situations well-known 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.
@article{DBLP:journals/tcs/BerghammerFN12, abstract = {Multi-objective optimization deals with the task of computing a set of solutions that represents possible trade-offs with respect to a given set of objective functions. Set-based approaches such as evolutionary algorithms are very popular for solving multi-objective optimization problems. Convergence of set-based approaches for multi-objective optimization is essential for their success. We take an order-theoretic view on the convergence of set-based multi-objective 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 set-based multi-objective 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 Pareto-dominance relation defined on sets. Later on, we show in which situations well-known 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.}, author = {Berghammer, Rudolf and Friedrich, Tobias and Neumann, Frank}, journal = {Theoretical Computer Science}, keywords = {frankneumann imported rudolfberghammer tcs tobiasfriedrich year2012}, pages = {2-17}, title = {Convergence of Set-Based Multi-Objective Optimization, Indicators and Deteriorative Cycles}, volume = 456, year = 2012 }

Sutton, Andrew M.; Whitley, L. Darrell; Howe, Adele E. Computing the moments of k-bounded pseudo-Boolean functions over Hamming spheres of arbitrary radius in polynomial timeTheoretical Computer Science 2012: 58–74
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We show that given a \(k\)-bounded pseudo-Boolean function \(f\), one can always compute the \(c\)th 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.
@article{DBLP:journals/tcs/SuttonWH12, abstract = {We show that given a \(k\)-bounded pseudo-Boolean function \(f\), one can always compute the \(c\)th 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.}, author = {Sutton, Andrew M. and Whitley, L. Darrell and Howe, Adele E.}, journal = {Theoretical Computer Science}, keywords = {andrewmsutton imported tcs year2012}, pages = {58-74}, title = {Computing the moments of k-bounded pseudo-Boolean functions over Hamming spheres of arbitrary radius in polynomial time}, volume = 425, year = 2012 }

Bringmann, Karl; Friedrich, Tobias Approximating the least hypervolume contributor: NP-hard in general, but fast in practiceTheoretical Computer Science 2012: 104–116
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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 \(\#P\)-hard while its approximation is NP-hard. The same holds for the calculation of the minimal contribution. We also prove that it is NP-hard to decide whether a solution has the least hypervolume contribution. Even deciding whether the contribution of a solution is at most \((1 +\epsilon)\) times the minimal contribution is NP-hard. 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 \(\epsilon, \delta > 0\) it calculates a solution with contribution at most \((1+\epsilon)\) times the minimal contribution with probability at least \((1 -\delta)\). 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.
@article{DBLP:journals/tcs/BringmannF12, abstract = {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 \(\#P\)-hard while its approximation is NP-hard. The same holds for the calculation of the minimal contribution. We also prove that it is NP-hard to decide whether a solution has the least hypervolume contribution. Even deciding whether the contribution of a solution is at most \((1 +\epsilon)\) times the minimal contribution is NP-hard. 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 \(\epsilon, \delta > 0\) it calculates a solution with contribution at most \((1+\epsilon)\) times the minimal contribution with probability at least \((1 -\delta)\). 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.}, author = {Bringmann, Karl and Friedrich, Tobias}, journal = {Theoretical Computer Science}, keywords = {imported tcs tobiasfriedrich year2012}, pages = {104-116}, title = {Approximating the least hypervolume contributor: NP-hard in general, but fast in practice}, volume = 425, year = 2012 }

Heinz, Jeffrey; Kasprzik, Anna; Kötzing, Timo Learning in the limit with lattice-structured hypothesis spacesTheoretical Computer Science 2012: 111–127
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We define a collection of language classes which are TxtEx-learnable (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 TxtEx-learnable consistently, conservatively, set-drivenly, and strongly monotonically. We show several language classes previously discussed in the literature to be lattice classes, including the locally k-testable classes, the piecewise k-testable classes, the k-reversible languages and the pattern languages. We also show that lattice classes contain three previously known collections of language classes: string extension language classes, function-distinguishable language classes, and closed-set systems. Finally, the lattice perspective helps analyze the learning of these classes. Illustrations include query-learning results in dependence on the lattice structure, characterizations of closure properties and the VC-dimension of lattice classes in terms of lattice properties.
@article{DBLP:journals/tcs/HeinzKK12, abstract = {We define a collection of language classes which are TxtEx-learnable (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 TxtEx-learnable consistently, conservatively, set-drivenly, and strongly monotonically. We show several language classes previously discussed in the literature to be lattice classes, including the locally k-testable classes, the piecewise k-testable classes, the k-reversible languages and the pattern languages. We also show that lattice classes contain three previously known collections of language classes: string extension language classes, function-distinguishable language classes, and closed-set systems. Finally, the lattice perspective helps analyze the learning of these classes. Illustrations include query-learning results in dependence on the lattice structure, characterizations of closure properties and the VC-dimension of lattice classes in terms of lattice properties.}, author = {Heinz, Jeffrey and Kasprzik, Anna and Kötzing, Timo}, journal = {Theoretical Computer Science}, keywords = {imported timokoetzing year2012}, pages = {111-127}, title = {Learning in the limit with lattice-structured hypothesis spaces}, volume = 457, year = 2012 }