All Publications

2017

• 
  Friedrich, Tobias; Neumann, Frank What’s Hot in Evolutionary Computation. Association for the Advancement of Artificial Intelligence (AAAI) 2017: 5064-5066
  [ Abstract ] [ BibTeX ] [ URL ] [ Download ]
   
  We provide a brief overview on some hot topics in the area of evolutionary computation. Our main focus is on recent developments in the areas of combinatorial optimization and real-world applications. Furthermore, we highlight recent progress on the theoretical understanding of evolutionary computing methods.
  @inproceedings{friedrich2017whats, abstract = {We provide a brief overview on some hot topics in the area of evolutionary computation. Our main focus is on recent developments in the areas of combinatorial optimization and real-world applications. Furthermore, we highlight recent progress on the theoretical understanding of evolutionary computing methods.}, author = {Friedrich, Tobias and Neumann, Frank}, booktitle = {Association for the Advancement of Artificial Intelligence (AAAI)}, crossref = {DBLP:conf/aaai/2017}, pages = {5064-5066}, title = {What’s Hot in Evolutionary Computation}, year = 2017 }
• 
  Doerr, Benjamin; Doerr, Carola; Kötzing, Timo Unknown Solution Length Problems With No Asymptotically Optimal Run Time. Genetic and Evolutionary Computation Conference (GECCO) 2017
  [ Abstract ] [ BibTeX ] [ Download ]
   
  We revisit the problem of optimizing a fitness function of unknown dimension; that is, we face a function defined over bit-strings of large length (N\), but only (n << N\) of them have an influence on the fitness. Neither the position of these relevant bits nor their number is known. In previous work, variants of the ((1 + 1)\) evolutionary algorithm (EA) have been developed that solve, for arbitrary s ∈ N, such OneMax and LeadingOnes instances, simultaneously for all n ∈ N, in expected time (O(n(log(n))^2 log log(n) dots log^(s−1) (n)(log^(s) (n))^1+ε )\)and (O(n^2 log(n) log log(n) dots log^(s−1) (n)(log^(s) (n))^1+ε )\), respectively; that is, in almost the same time as if n and the relevant bit positions were known. In this work, we prove the first, almost matching, lower bounds for this setting. For LeadingOnes, we show that, for every (s in N\), the ((1 + 1)\) EA with any mutation operator treating zeros and ones equally has an expected run time of (omega(n^2 log(n) log log(n) dots log^(s) (n)) when facing problem size (n\). Aiming at closing the small remaining gap, we realize that, quite surprisingly, there is no asymptotically best performance. For any algorithm solving, for all (n\), all instances of size (n\) in expected time at most (T (n)\), there is an algorithm doing the same in time (T'(n)\) with (T' = o(T )\). For OneMax we show results of similar flavor.
  @inproceedings{doerr2017unknown, abstract = {We revisit the problem of optimizing a fitness function of unknown dimension; that is, we face a function defined over bit-strings of large length (N\), but only (n << N\) of them have an influence on the fitness. Neither the position of these relevant bits nor their number is known. In previous work, variants of the ((1 + 1)\) evolutionary algorithm (EA) have been developed that solve, for arbitrary s ∈ N, such OneMax and LeadingOnes instances, simultaneously for all n ∈ N, in expected time (O(n(log(n))^2 log log(n) dots log^(s−1) (n)(log^(s) (n))^1+ε )\)and (O(n^2 log(n) log log(n) dots log^(s−1) (n)(log^(s) (n))^1+ε )\), respectively; that is, in almost the same time as if n and the relevant bit positions were known. In this work, we prove the first, almost matching, lower bounds for this setting. For LeadingOnes, we show that, for every (s in N\), the ((1 + 1)\) EA with any mutation operator treating zeros and ones equally has an expected run time of (omega(n^2 log(n) log log(n) dots log^(s) (n)) when facing problem size (n\). Aiming at closing the small remaining gap, we realize that, quite surprisingly, there is no asymptotically best performance. For any algorithm solving, for all (n\), all instances of size (n\) in expected time at most (T (n)\), there is an algorithm doing the same in time (T'(n)\) with (T' = o(T )\). For OneMax we show results of similar flavor.}, author = {Doerr, Benjamin and Doerr, Carola and Kötzing, Timo}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, title = {Unknown Solution Length Problems With No Asymptotically Optimal Run Time}, year = 2017 }
• 
  Kovacs, Robert; Seufert, Anna; Wall, Ludwig; Chen, Hsiang-Ting; Meinel, Florian; Müller, Willi; You, Sijing; Brehm, Maximilian; Striebel, Jonathan; Kommana, Yannis; Popiak, Alexander; Bläsius, Thomas; Baudisch, Patrick TrussFab: Fabricating Sturdy Large-Scale Structures on Desktop 3D Printers. Human Factors in Computing Systems (CHI) 2017: 2606-2616
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  We present TrussFab, an integrated end-to-end system that allows users to fabricate large scale structures that are sturdy enough to carry human weight. TrussFab achieves the large scale by complementing 3D print with plastic bottles. It does not use these bottles as “bricks” though, but as beams that form structurally sound node-link structures, also known as trusses, allowing it to handle the forces resulting from scale and load. TrussFab embodies the required engineering knowledge, allowing non-engineers to design such structures and to validate their design using integrated structural analysis. We have used TrussFab to design and fabricate tables and chairs, a 2.5 m long bridge strong enough to carry a human, a functional boat that seats two, and a 5 m diameter dome.
  @inproceedings{DBLP:conf/chi/KovacsSWCMMYBSK17, abstract = {We present TrussFab, an integrated end-to-end system that allows users to fabricate large scale structures that are sturdy enough to carry human weight. TrussFab achieves the large scale by complementing 3D print with plastic bottles. It does not use these bottles as “bricks” though, but as beams that form structurally sound node-link structures, also known as trusses, allowing it to handle the forces resulting from scale and load. TrussFab embodies the required engineering knowledge, allowing non-engineers to design such structures and to validate their design using integrated structural analysis. We have used TrussFab to design and fabricate tables and chairs, a 2.5 m long bridge strong enough to carry a human, a functional boat that seats two, and a 5 m diameter dome.}, author = {Kovacs, Robert and Seufert, Anna and Wall, Ludwig and Chen, Hsiang-Ting and Meinel, Florian and Müller, Willi and You, Sijing and Brehm, Maximilian and Striebel, Jonathan and Kommana, Yannis and Popiak, Alexander and Bläsius, Thomas and Baudisch, Patrick}, booktitle = {Human Factors in Computing Systems (CHI)}, crossref = {DBLP:conf/chi/2017}, pages = {2606-2616}, title = {TrussFab: Fabricating Sturdy Large-Scale Structures on Desktop 3D Printers}, year = 2017 }
• 
  Doerr, Benjamin; Neumann, Frank; Sutton, Andrew M. Time Complexity Analysis of Evolutionary Algorithms on Random Satisfiable k-CNF Formulas. Algorithmica 2017: 561-586
  [ Abstract ] [ BibTeX ] [ URL ] [DOI]
   
  We contribute to the theoretical understanding of randomized search heuristics by investigating their optimization behavior on satisfiable random k-satisfiability instances both in the planted solution model and the uniform model conditional on satisfiability. Denoting the number of variables by n, our main technical result is that the simple (1+1) evolutionary algorithm with high probability finds a satisfying assignment in time (O(n log n)\) when the clause-variable density is at least logarithmic. For low density instances, evolutionary algorithms seem to be less effective, and all we can show is a subexponential upper bound on the runtime for densities below (1/(k(k−1))\). We complement these mathematical results with numerical experiments on a broader density spectrum. They indicate that, indeed, the (1+1) EA is less efficient on lower densities. Our experiments also suggest that the implicit constants hidden in our main runtime guarantee are low. Our main result extends and considerably improves the result obtained by Sutton and Neumann (Lect Notes Comput Sci 8672:942–951, 2014) in terms of runtime, minimum density, and clause length. These improvements are made possible by establishing a close fitness-distance correlation in certain parts of the search space. This approach might be of independent interest and could be useful for other average-case analyses of randomized search heuristics. While the notion of a fitness-distance correlation has been around for a long time, to the best of our knowledge, this is the first time that fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.
  @article{DBLP:journals/algorithmica/DoerrNS17, abstract = {We contribute to the theoretical understanding of randomized search heuristics by investigating their optimization behavior on satisfiable random k-satisfiability instances both in the planted solution model and the uniform model conditional on satisfiability. Denoting the number of variables by n, our main technical result is that the simple (1+1) evolutionary algorithm with high probability finds a satisfying assignment in time (O(n log n)\) when the clause-variable density is at least logarithmic. For low density instances, evolutionary algorithms seem to be less effective, and all we can show is a subexponential upper bound on the runtime for densities below (1/(k(k−1))\). We complement these mathematical results with numerical experiments on a broader density spectrum. They indicate that, indeed, the (1+1) EA is less efficient on lower densities. Our experiments also suggest that the implicit constants hidden in our main runtime guarantee are low. Our main result extends and considerably improves the result obtained by Sutton and Neumann (Lect Notes Comput Sci 8672:942–951, 2014) in terms of runtime, minimum density, and clause length. These improvements are made possible by establishing a close fitness-distance correlation in certain parts of the search space. This approach might be of independent interest and could be useful for other average-case analyses of randomized search heuristics. While the notion of a fitness-distance correlation has been around for a long time, to the best of our knowledge, this is the first time that fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.}, author = {Doerr, Benjamin and Neumann, Frank and Sutton, Andrew M.}, journal = {Algorithmica}, number = 2, pages = {561-586}, title = {Time Complexity Analysis of Evolutionary Algorithms on Random Satisfiable k-CNF Formulas}, volume = 78, year = 2017 }
• 
  Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. The Compact Genetic Algorithm is Efficient under Extreme Gaussian Noise. IEEE Transactions on Evolutionary Computation 2017
  [ Abstract ] [ BibTeX ] [ Download ]
   
  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, randomized search heuristics such as evolutionary algorithms are a popular choice because they are often assumed to exhibit some kind of resistance to noise. Empirical evidence suggests that some algorithms, such as estimation of distribution algorithms (EDAs) are robust against a scaling of the noise intensity, even without resorting to explicit noise-handling techniques such as resampling. In this paper, we want to support such claims with mathematical rigor. We introduce the concept of graceful scaling in which the run time of an algorithm scales polynomially with noise intensity. We study a monotone fitness function over binary strings with additive noise taken from a Gaussian distribution. We show that myopic heuristics cannot efficiently optimize the function under arbitrarily intense noise without any explicit noise-handling. Furthermore, we prove that using a population does not help. Finally we show that a simple EDA called the compact Genetic Algorithm can overcome the shortsightedness of mutation-only heuristics to scale gracefully with noise. We conjecture that recombinative genetic algorithms also have this property.
  @article{friedrich2016compact, abstract = {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, randomized search heuristics such as evolutionary algorithms are a popular choice because they are often assumed to exhibit some kind of resistance to noise. Empirical evidence suggests that some algorithms, such as estimation of distribution algorithms (EDAs) are robust against a scaling of the noise intensity, even without resorting to explicit noise-handling techniques such as resampling. In this paper, we want to support such claims with mathematical rigor. We introduce the concept of graceful scaling in which the run time of an algorithm scales polynomially with noise intensity. We study a monotone fitness function over binary strings with additive noise taken from a Gaussian distribution. We show that myopic heuristics cannot efficiently optimize the function under arbitrarily intense noise without any explicit noise-handling. Furthermore, we prove that using a population does not help. Finally we show that a simple EDA called the compact Genetic Algorithm can overcome the shortsightedness of mutation-only heuristics to scale gracefully with noise. We conjecture that recombinative genetic algorithms also have this property.}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Sutton, Andrew M.}, howpublished = {in press}, journal = {IEEE Transactions on Evolutionary Computation}, title = {The Compact Genetic Algorithm is Efficient under Extreme Gaussian Noise}, year = 2017 }
• 
  Katzmann, Maximilian; Komusiewicz, Christian Systematic Exploration of Larger Local Search Neighborhoods for the Minimum Vertex Cover Problem. Association for the Advancement of Artificial Intelligence (AAAI) 2017: 846-852
  [ Abstract ] [ BibTeX ] [ URL ] [ Download ]
   
  We investigate the potential of exhaustively exploring larger neighborhoods in local search algorithms for Minimum Vertex Cover. More precisely, we study whether, for moderate values of (k\), it is feasible and worthwhile to determine, given a graph (G\) with vertex cover (C\), if there is a (k\)-swap (S\) such that ((C setminus S) cup (S setminus C)\) is a smaller vertex cover of (G\). First, we describe an algorithm running in (Delta^O(k) cdot n\) time for searching the (k\)-swap neighborhood on (n\)-vertex graphs with maximum degree (\Delta\). Then, we demonstrate that, by devising additional pruning rules that decrease the size of the search space, this algorithm can be implemented so that it solves the problem quickly for (k approx 20\). Finally, we show that it is worthwhile to consider moderately-sized (k\)-swap neighborhoods. For our benchmark data set, we show that when combining our algorithm with a hill-climbing approach, the solution quality improves quickly with the radius (k\) of the local search neighborhood and that in most cases optimal solutions can be found by setting (k = 21\).
  @inproceedings{DBLP:conf/aaai/KatzmannK17, abstract = {We investigate the potential of exhaustively exploring larger neighborhoods in local search algorithms for Minimum Vertex Cover. More precisely, we study whether, for moderate values of (k\), it is feasible and worthwhile to determine, given a graph (G\) with vertex cover (C\), if there is a (k\)-swap (S\) such that ((C setminus S) cup (S setminus C)\) is a smaller vertex cover of (G\). First, we describe an algorithm running in (Delta^O(k) cdot n\) time for searching the (k\)-swap neighborhood on (n\)-vertex graphs with maximum degree (\Delta\). Then, we demonstrate that, by devising additional pruning rules that decrease the size of the search space, this algorithm can be implemented so that it solves the problem quickly for (k approx 20\). Finally, we show that it is worthwhile to consider moderately-sized (k\)-swap neighborhoods. For our benchmark data set, we show that when combining our algorithm with a hill-climbing approach, the solution quality improves quickly with the radius (k\) of the local search neighborhood and that in most cases optimal solutions can be found by setting (k = 21\).}, author = {Katzmann, Maximilian and Komusiewicz, Christian}, booktitle = {Association for the Advancement of Artificial Intelligence (AAAI)}, crossref = {DBLP:conf/aaai/2017}, pages = {846-852}, title = {Systematic Exploration of Larger Local Search Neighborhoods for the Minimum Vertex Cover Problem}, year = 2017 }
• 
  Gao, Wanru; Friedrich, Tobias; Kötzing, Timo; Neumann, Frank Scaling up Local Search for Minimum Vertex Cover in Large Graphs by Parallel Kernelization. Australasian Conference on Artificial Intelligence (AUSAI) 2017
  [ Abstract ] [ BibTeX ] [ Download ]
   
  We investigate how well-performing local search algorithms for small or medium size instances can be scaled up to perform well for large inputs. We introduce a parallel kernelization technique that is motivated by the assumption that graphs in medium to large scale are composed of components which are on their own easy for state-of-the-art solvers but when hidden in large graphs are hard to solve. To show the effectiveness of our kernelization technique, we consider the well-known minimum vertex cover problem and two state-of-the-art solvers called NuMVC and FastVC. Our kernelization approach reduces an existing large problem instance significantly and produces better quality results on a wide range of benchmark instances and real world graphs.
  @inproceedings{gao2017scaling, abstract = {We investigate how well-performing local search algorithms for small or medium size instances can be scaled up to perform well for large inputs. We introduce a parallel kernelization technique that is motivated by the assumption that graphs in medium to large scale are composed of components which are on their own easy for state-of-the-art solvers but when hidden in large graphs are hard to solve. To show the effectiveness of our kernelization technique, we consider the well-known minimum vertex cover problem and two state-of-the-art solvers called NuMVC and FastVC. Our kernelization approach reduces an existing large problem instance significantly and produces better quality results on a wide range of benchmark instances and real world graphs.}, author = {Gao, Wanru and Friedrich, Tobias and Kötzing, Timo and Neumann, Frank}, booktitle = {Australasian Conference on Artificial Intelligence (AUSAI)}, title = {Scaling up Local Search for Minimum Vertex Cover in Large Graphs by Parallel Kernelization}, year = 2017 }
• 
  Friedrich, Tobias; Kötzing, Timo; Quinzan, Francesco; Sutton, Andrew Michael Resampling vs Recombination: a Statistical Run Time Estimation. Foundations of Genetic Algorithms (FOGA) 2017: 25-36
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  Noise is pervasive in real-world optimization, but there is still little understanding of the interplay between the operators of randomized search heuristics and explicit noise-handling techniques, such as statistical resampling. In this paper, we report on several statistical models and theoretical results that help to clarify this reciprocal relationship for a collection of randomized search heuristics on noisy functions. We consider the optimization of pseudo-Boolean functions under additive posterior Gaussian noise and explore the trade-o between noise reduction and the computational cost of resampling. We first perform experiments to find the optimal parameters at a given noise intensity for a mutation-only evolutionary algorithm, a genetic algorithm employing recombination, an estimation of distribution algorithm (EDA), and an ant colony optimization algorithm. We then observe how the optimal parameter depends on the noise intensity for the different algorithms. Finally, we locate the point where statistical resampling costs more than it is worth in terms of run time. We find that the EA requires the highest number of resamples to obtain the best speed-up, whereas crossover reduces both the run time and the number of resamples required. Most surprisingly, we find that EDA-like algorithms require no resampling, and can handle noise implicitly.
  @inproceedings{DBLP:conf/foga/0001KQS17, abstract = {Noise is pervasive in real-world optimization, but there is still little understanding of the interplay between the operators of randomized search heuristics and explicit noise-handling techniques, such as statistical resampling. In this paper, we report on several statistical models and theoretical results that help to clarify this reciprocal relationship for a collection of randomized search heuristics on noisy functions. We consider the optimization of pseudo-Boolean functions under additive posterior Gaussian noise and explore the trade-o between noise reduction and the computational cost of resampling. We first perform experiments to find the optimal parameters at a given noise intensity for a mutation-only evolutionary algorithm, a genetic algorithm employing recombination, an estimation of distribution algorithm (EDA), and an ant colony optimization algorithm. We then observe how the optimal parameter depends on the noise intensity for the different algorithms. Finally, we locate the point where statistical resampling costs more than it is worth in terms of run time. We find that the EA requires the highest number of resamples to obtain the best speed-up, whereas crossover reduces both the run time and the number of resamples required. Most surprisingly, we find that EDA-like algorithms require no resampling, and can handle noise implicitly.}, author = {Friedrich, Tobias and Kötzing, Timo and Quinzan, Francesco and Sutton, Andrew Michael}, booktitle = {Foundations of Genetic Algorithms (FOGA)}, pages = {25-36}, publisher = {ACM Press}, title = {Resampling vs Recombination: a Statistical Run Time Estimation}, year = 2017 }
• 
  Shi, Feng; Schirneck, Martin; Friedrich, Tobias; Kötzing, Timo; Neumann, Frank Reoptimization Times of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints. Genetic and Evolutionary Computation Conference (GECCO) 2017
  [ Abstract ] [ BibTeX ] [ Download ]
   
  Thee investigations of linear pseudo-Boolean functions play a central role in the area of runtime analysis of evolutionary computing techniques. Having an additional linear constraint on a linear function is equivalent to the NP-hard knapsack problem and special problem classes thereof have been investigated in recent works. In this paper, we extend these studies to problems with dynamic constraints and investigate the runtime of different evolutionary algorithms to recompute an optimal solution when the constraint bound changes by a certain amount. We study the classical ((1+1)\) EA and population-based algorithms and show that they recompute an optimal solution very efficiently. Furthermore, we show that a variant of the ((1+(lambda, \lambda))\) GA can recompute the optimal solution more eciently in some cases.
  @inproceedings{shi2017reoptimization, abstract = {Thee investigations of linear pseudo-Boolean functions play a central role in the area of runtime analysis of evolutionary computing techniques. Having an additional linear constraint on a linear function is equivalent to the NP-hard knapsack problem and special problem classes thereof have been investigated in recent works. In this paper, we extend these studies to problems with dynamic constraints and investigate the runtime of different evolutionary algorithms to recompute an optimal solution when the constraint bound changes by a certain amount. We study the classical ((1+1)\) EA and population-based algorithms and show that they recompute an optimal solution very efficiently. Furthermore, we show that a variant of the ((1+(lambda, \lambda))\) GA can recompute the optimal solution more eciently in some cases.}, author = {Shi, Feng and Schirneck, Martin and Friedrich, Tobias and Kötzing, Timo and Neumann, Frank}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, title = {Reoptimization Times of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints}, year = 2017 }
• 
  Friedrich, Tobias; Krohmer, Anton; Rothenberger, Ralf; Sutton, Andrew M. Phase Transitions for Scale-Free SAT Formulas. Association for the Advancement of Artificial Intelligence (AAAI) 2017: 3893-3899
  [ Abstract ] [ BibTeX ] [ URL ] [ Download ]
   
  Recently, a number of non-uniform random satisfiability models have been proposed that are closer to practical satisfiability problems in some characteristics. In contrast to uniform random Boolean formulas, scale-free formulas have a variable occurrence distribution that follows a power law. It has been conjectured that such a distribution is a more accurate model for some industrial instances than the uniform random model. Though it seems that there is already an awareness of a threshold phenomenon in such models, there is still a complete picture lacking. In contrast to the uniform model, the critical density threshold does not lie at a single point, but instead exhibits a functional dependency on the power-law exponent. For scale-free formulas with clauses of length (k = 2\), we give a lower bound on the phase transition threshold as a function of the scaling parameter. We also perform computational studies that suggest our bound is tight and investigate the critical density for formulas with higher clause lengths. Similar to the uniform model, on formulas with (k ge 3\), we find that the phase transition regime corresponds to a set of formulas that are difficult to solve by backtracking search.
  @inproceedings{DBLP:conf/aaai/0001KRS17, abstract = {Recently, a number of non-uniform random satisfiability models have been proposed that are closer to practical satisfiability problems in some characteristics. In contrast to uniform random Boolean formulas, scale-free formulas have a variable occurrence distribution that follows a power law. It has been conjectured that such a distribution is a more accurate model for some industrial instances than the uniform random model. Though it seems that there is already an awareness of a threshold phenomenon in such models, there is still a complete picture lacking. In contrast to the uniform model, the critical density threshold does not lie at a single point, but instead exhibits a functional dependency on the power-law exponent. For scale-free formulas with clauses of length (k = 2\), we give a lower bound on the phase transition threshold as a function of the scaling parameter. We also perform computational studies that suggest our bound is tight and investigate the critical density for formulas with higher clause lengths. Similar to the uniform model, on formulas with (k ge 3\), we find that the phase transition regime corresponds to a set of formulas that are difficult to solve by backtracking search.}, author = {Friedrich, Tobias and Krohmer, Anton and Rothenberger, Ralf and Sutton, Andrew M.}, booktitle = {Association for the Advancement of Artificial Intelligence (AAAI)}, crossref = {DBLP:conf/aaai/2017}, pages = {3893-3899}, publisher = {AAAI Press}, title = {Phase Transitions for Scale-Free SAT Formulas}, year = 2017 }
• 
  Pourhassan, Mojgan; Friedrich, Tobias; Neumann, Frank On the Use of the Dual Formulation for Minimum Weighted Vertex Cover in Evolutionary Algorithms. Foundations of Genetic Algorithms (FOGA) 2017: 37-44
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  We consider the weighted minimum vertex cover problem and investigate how its dual formulation can be exploited to design evolutionary algorithms that provably obtain a 2-approximation. Investigating multi-valued representations, we show that variants of randomized local search and the (1+1) EA achieve this goal in expected pseudo-polynomial time. In order to speed up the process, we consider the use of step size adaptation in both algorithms and show that RLS obtains a 2-approximation in expected polynomial time while the (1+1) EA still encounters a pseudo-polynomial lower bound.
  @inproceedings{DBLP:conf/foga/Pourhassan0N17, abstract = {We consider the weighted minimum vertex cover problem and investigate how its dual formulation can be exploited to design evolutionary algorithms that provably obtain a 2-approximation. Investigating multi-valued representations, we show that variants of randomized local search and the (1+1) EA achieve this goal in expected pseudo-polynomial time. In order to speed up the process, we consider the use of step size adaptation in both algorithms and show that RLS obtains a 2-approximation in expected polynomial time while the (1+1) EA still encounters a pseudo-polynomial lower bound.}, author = {Pourhassan, Mojgan and Friedrich, Tobias and Neumann, Frank}, booktitle = {Foundations of Genetic Algorithms (FOGA)}, pages = {37-44}, publisher = {ACM Press}, title = {On the Use of the Dual Formulation for Minimum Weighted Vertex Cover in Evolutionary Algorithms}, year = 2017 }
• 
  Bampas, Evangelos; Göbel, Andreas-Nikolas; Pagourtzis, Aris; Tentes, Aris On the connection between interval size functions and path counting. Computational Complexity 2017: 421-467
  [ BibTeX ] [ URL ] [DOI]
   
  @article{DBLP:journals/cc/BampasGPT17, author = {Bampas, Evangelos and Göbel, Andreas-Nikolas and Pagourtzis, Aris and Tentes, Aris}, journal = {Computational Complexity}, number = 2, pages = {421-467}, title = {On the connection between interval size functions and path counting}, volume = 26, year = 2017 }
• 
  Anand, S.; Bringmann, Karl; Friedrich, Tobias; Garg, Naveen; Kumar, Amit Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines. Algorithmica 2017: 515-536
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  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 < \infty\) norms. Our main results are: (1) we give an (O(\epsilon^{−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+\epsilon\) units of a job in 1 time-unit ((\epsilon\) speed augmentation). (2) For the objective of minimizing maximum flow time on unrelated machines we give a simple (2/\epsilon\)-competitive algorithm when we augment the speed by (\epsilon\). For (m\) machines we show a lower bound of (Omega(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 (Omega(log m)\) on the competitive ratio of immediate dispatch algorithms. In both these lower bound constructions we use jobs whose processing times are in (\{1,\infty\}\), 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 (Omega(log m)\)-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.
  @article{DBLP:journals/algorithmica/0002B0G017, abstract = {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 < \infty\) norms. Our main results are: (1) we give an (O(\epsilon^{−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+\epsilon\) units of a job in 1 time-unit ((\epsilon\) speed augmentation). (2) For the objective of minimizing maximum flow time on unrelated machines we give a simple (2/\epsilon\)-competitive algorithm when we augment the speed by (\epsilon\). For (m\) machines we show a lower bound of (Omega(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 (Omega(log m)\) on the competitive ratio of immediate dispatch algorithms. In both these lower bound constructions we use jobs whose processing times are in (\{1,\infty\}\), 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 (Omega(log m)\)-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.}, author = {Anand, S. and Bringmann, Karl and Friedrich, Tobias and Garg, Naveen and Kumar, Amit}, journal = {Algorithmica}, number = 2, pages = {515-536}, title = {Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines}, volume = 77, year = 2017 }
• 
  Krejca, Martin S.; Witt, Carsten Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMax. Foundations of Genetic Algorithms (FOGA) 2017: 65-80
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  The Univariate Marginal Distribution Algorithm (UMDA), a popular estimation of distribution algorithm, is studied from a run time perspective. On the classical OneMax benchmark function, a lower bound of (Omega(mu sqrt n + n log n)\), where (\mu\) is the population size, on its expected run time is proved. This is the first direct lower bound on the run time of the UMDA. It is stronger than the bounds that follow from general black-box complexity theory and is matched by the run time of many evolutionary algorithms. The results are obtained through advanced analyses of the stochastic change of the frequencies of bit values maintained by the algorithm, including carefully designed potential functions. These techniques may prove useful in advancing the field of run time analysis for estimation of distribution algorithms in general.
  @inproceedings{DBLP:conf/foga/KrejcaW17, abstract = {The Univariate Marginal Distribution Algorithm (UMDA), a popular estimation of distribution algorithm, is studied from a run time perspective. On the classical OneMax benchmark function, a lower bound of (Omega(mu sqrt n + n log n)\), where (\mu\) is the population size, on its expected run time is proved. This is the first direct lower bound on the run time of the UMDA. It is stronger than the bounds that follow from general black-box complexity theory and is matched by the run time of many evolutionary algorithms. The results are obtained through advanced analyses of the stochastic change of the frequencies of bit values maintained by the algorithm, including carefully designed potential functions. These techniques may prove useful in advancing the field of run time analysis for estimation of distribution algorithms in general.}, author = {Krejca, Martin S. and Witt, Carsten}, booktitle = {Foundations of Genetic Algorithms (FOGA)}, pages = {65-80}, publisher = {ACM Press}, title = {Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMax}, year = 2017 }
• 
  Doerr, Benjamin; Fischbeck, Philipp; Frahnow, Clemens; Friedrich, Tobias; Kötzing, Timo; Schirneck, Martin Island Models Meet Rumor Spreading. Genetic and Evolutionary Computation Conference (GECCO) 2017
  [ Abstract ] [ BibTeX ] [ Download ]
   
  Island models in evolutionary computation solve problems by a careful interplay of independently running evolutionary algorithms on the island and an exchange of good solutions between the islands. In this work, we conduct rigorous run time analyses for such island models trying to simultaneously obtain good run times and low communication effort. We improve the existing upper bounds for the communication effort (i) by improving the run time bounds via a careful analysis, (ii) by setting the balance between individual computation and communication in a more appropriate manner, and (iii) by replacing the usual communicate-with-all-neighbors approach with randomized rumor spreading, where each island contacts a randomly chosen neighbor. This epidemic communication paradigm is known to lead to very fast and robust information dissemination in many applications. Our results concern islands running simple (1+1) evolutionary algorithms, we regard d-dimensional tori and complete graphs as communication topologies, and optimize the classic test functions OneMax and LeadingOnes.
  @inproceedings{doerr2017island, abstract = {Island models in evolutionary computation solve problems by a careful interplay of independently running evolutionary algorithms on the island and an exchange of good solutions between the islands. In this work, we conduct rigorous run time analyses for such island models trying to simultaneously obtain good run times and low communication effort. We improve the existing upper bounds for the communication effort (i) by improving the run time bounds via a careful analysis, (ii) by setting the balance between individual computation and communication in a more appropriate manner, and (iii) by replacing the usual communicate-with-all-neighbors approach with randomized rumor spreading, where each island contacts a randomly chosen neighbor. This epidemic communication paradigm is known to lead to very fast and robust information dissemination in many applications. Our results concern islands running simple (1+1) evolutionary algorithms, we regard d-dimensional tori and complete graphs as communication topologies, and optimize the classic test functions OneMax and LeadingOnes.}, author = {Doerr, Benjamin and Fischbeck, Philipp and Frahnow, Clemens and Friedrich, Tobias and Kötzing, Timo and Schirneck, Martin}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, title = {Island Models Meet Rumor Spreading}, year = 2017 }
• 
  Wagner, Markus; Friedrich, Tobias; Lindauer, Marius Improving local search in a minimum vertex cover solver for classes of networks. Congress on Evolutionary Computation (CEC) 2017
  [ Abstract ] [ BibTeX ] [ Download ]
   
  For the minimum vertex cover problem, a wide range of solvers has been proposed over the years. Most classical exact approaches are encountering run time issues on massive graphs that are considered nowadays. A straightforward alternative approach is then to use heuristics, which make assumptions about the structure of the studied graphs. These assumptions are typically hard-coded and are hoped to work well for a wide range of networks - which is in conflict with the nature of broad benchmark sets. With this article, we contribute in two ways. First, we identify a component in an existing solver that influences its performance depending on the class of graphs, and we then customize instances of this solver for different classes of graphs. Second, we create the first algorithm portfolio for the minimum vertex cover to further improve the performance of a single integrated approach to the minimum vertex cover problem.
  @inproceedings{wagner2017improving, abstract = {For the minimum vertex cover problem, a wide range of solvers has been proposed over the years. Most classical exact approaches are encountering run time issues on massive graphs that are considered nowadays. A straightforward alternative approach is then to use heuristics, which make assumptions about the structure of the studied graphs. These assumptions are typically hard-coded and are hoped to work well for a wide range of networks - which is in conflict with the nature of broad benchmark sets. With this article, we contribute in two ways. First, we identify a component in an existing solver that influences its performance depending on the class of graphs, and we then customize instances of this solver for different classes of graphs. Second, we create the first algorithm portfolio for the minimum vertex cover to further improve the performance of a single integrated approach to the minimum vertex cover problem.}, author = {Wagner, Markus and Friedrich, Tobias and Lindauer, Marius}, booktitle = {Congress on Evolutionary Computation (CEC)}, publisher = {IEEE}, title = {Improving local search in a minimum vertex cover solver for classes of networks}, year = 2017 }
• 
  Bläsius, Thomas; Radermacher, Marcel; Rutter, Ignaz How to Draw a Planarization. Software Seminar (SOFSEM) 2017: 295-308
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  We study the problem of computing straight-line drawings of non-planar graphs with few crossings. We assume that a crossingminimization algorithm is applied first, yielding a planarization, i.e., a planar graph with a dummy vertex for each crossing, that fixes the topology of the resulting drawing. We present and evaluate two different approaches for drawing a planarization in such a way that the edges of the input graph are as straight as possible. The first approach is based on the planarity-preserving force-directed algorithm ImPrEd, the second approach, which we call Geometric Planarization Drawing, iteratively moves vertices to their locally optimal positions in the given initial drawing.
  @inproceedings{DBLP:conf/sofsem/BlasiusRR17, abstract = {We study the problem of computing straight-line drawings of non-planar graphs with few crossings. We assume that a crossingminimization algorithm is applied first, yielding a planarization, i.e., a planar graph with a dummy vertex for each crossing, that fixes the topology of the resulting drawing. We present and evaluate two different approaches for drawing a planarization in such a way that the edges of the input graph are as straight as possible. The first approach is based on the planarity-preserving force-directed algorithm ImPrEd, the second approach, which we call Geometric Planarization Drawing, iteratively moves vertices to their locally optimal positions in the given initial drawing.}, author = {Bläsius, Thomas and Radermacher, Marcel and Rutter, Ignaz}, booktitle = {Software Seminar (SOFSEM)}, crossref = {DBLP:conf/sofsem/2017}, pages = {295-308}, title = {How to Draw a Planarization}, year = 2017 }
• 
  Göbel, Andreas Counting, Modular Counting and Graph Homomorphisms. 2017
  [ BibTeX ] [ Download ]
   
  @phdthesis{gobel2017counting, author = {Göbel, Andreas}, title = {Counting, Modular Counting and Graph Homomorphisms}, year = 2017 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton Cliques in Hyperbolic Random Graphs. Algorithmica 2017
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  Most complex real world networks display scale-free features. This characteristic motivated the study of numerous random graph models with a power-law 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 hyprg and has shown theoretically and empirically to fulfill all typical properties of real world networks, including power-law degree distribution and high clustering. We study cliques in hyperbolic random graphs (G\) and present new results on the expected number of (k\)-cliques (E(K_k)\) and the size of the largest clique (omega(G)\). We observe that there is a phase transition at power-law exponent (beta = 3\). More precisely, for (beta in (2,3)\) we prove (E(K_k)=n^k (3-\beta)/2 Theta(k)^{-k}\) and (omega(G)=Theta(n^(3-\beta)/2})\), while for (\beta\geq3\) we prove (E(K_k)=n Theta(k)^{-k}\) and (omega(G)=Theta(log(n)/ log log n)\). Furthermore, we show that for (beta geq 3\), cliques in hyperbolic random graphs can be computed in time (O(n)\). If the underlying geometry is known, cliques can be found with worst-case runtime (O(m cdot n^{2.5})\) for all values of (\beta\).
  @article{blasius2017cliques, abstract = {Most complex real world networks display scale-free features. This characteristic motivated the study of numerous random graph models with a power-law 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 hyprg and has shown theoretically and empirically to fulfill all typical properties of real world networks, including power-law degree distribution and high clustering. We study cliques in hyperbolic random graphs (G\) and present new results on the expected number of (k\)-cliques (E(K_k)\) and the size of the largest clique (omega(G)\). We observe that there is a phase transition at power-law exponent (beta = 3\). More precisely, for (beta in (2,3)\) we prove (E(K_k)=n^k (3-\beta)/2 Theta(k)^{-k}\) and (omega(G)=Theta(n^(3-\beta)/2})\), while for (\beta\geq3\) we prove (E(K_k)=n Theta(k)^{-k}\) and (omega(G)=Theta(log(n)/ log log n)\). Furthermore, we show that for (beta geq 3\), cliques in hyperbolic random graphs can be computed in time (O(n)\). If the underlying geometry is known, cliques can be found with worst-case runtime (O(m cdot n^{2.5})\) for all values of (\beta\).}, author = {Bläsius, Thomas and Friedrich, Tobias and Krohmer, Anton}, journal = {Algorithmica}, title = {Cliques in Hyperbolic Random Graphs}, year = 2017 }
• 
  Friedrich, Tobias; Ihde, Sven; Keßler, Christoph; Lenzner, Pascal; Neubert, Stefan; Schumann, David Brief Announcement: Efficient Best Response Computation for Strategic Network Formation under Attack. Symposium on Parallelism in Algorithms and Architectures (SPAA) 2017
  [ BibTeX ]
   
  @inproceedings{friedrich2017brief, author = {Friedrich, Tobias and Ihde, Sven and Keßler, Christoph and Lenzner, Pascal and Neubert, Stefan and Schumann, David}, booktitle = {Symposium on Parallelism in Algorithms and Architectures (SPAA)}, publisher = {ACM}, title = {Brief Announcement: Efficient Best Response Computation for Strategic Network Formation under Attack}, year = 2017 }
• 
  Doerr, Benjamin; Kötzing, Timo; Lagodzinski, J. A. Gregor; Lengler, Johannes Bounding Bloat in Genetic Programming. Genetic and Evolutionary Computation Conference (GECCO) 2017
  [ Abstract ] [ BibTeX ] [ Download ]
   
  While many optimization problems work with a fixed number of decision variables and thus a fixed-length representation of possible solutions, genetic programming (GP) works on variable-length representations. A naturally occurring problem is that of bloat (unnecessary growth of solutions) slowing down optimization. Theoretical analyses could so far not bound bloat and required explicit assumptions on the magnitude of bloat. In this paper we analyze bloat in mutation-based genetic programming for the two test functions ORDER and MAJORITY. We overcome previous assumptions on the magnitude of bloat and give matching or close-to-matching upper and lower bounds for the expected optimization time. In particular, we show that the ((1+1)\) GP takes (i) (Theta(T_init + n log n)\) iterations with bloat control on ORDER as well as MAJORITY; and (ii) (O(T_init log T_init + n(log n)^3)\) and (Omega(T_init + n log n)\) (and (Omega(T_init log T_init)\) for (n = 1\)) iterations without bloat control on MAJORITY.
  @inproceedings{doerr2017bounding, abstract = {While many optimization problems work with a fixed number of decision variables and thus a fixed-length representation of possible solutions, genetic programming (GP) works on variable-length representations. A naturally occurring problem is that of bloat (unnecessary growth of solutions) slowing down optimization. Theoretical analyses could so far not bound bloat and required explicit assumptions on the magnitude of bloat. In this paper we analyze bloat in mutation-based genetic programming for the two test functions ORDER and MAJORITY. We overcome previous assumptions on the magnitude of bloat and give matching or close-to-matching upper and lower bounds for the expected optimization time. In particular, we show that the ((1+1)\) GP takes (i) (Theta(T_init + n log n)\) iterations with bloat control on ORDER as well as MAJORITY; and (ii) (O(T_init log T_init + n(log n)^3)\) and (Omega(T_init + n log n)\) (and (Omega(T_init log T_init)\) for (n = 1\)) iterations without bloat control on MAJORITY.}, author = {Doerr, Benjamin and Kötzing, Timo and Lagodzinski, J. A. Gregor and Lengler, Johannes}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, title = {Bounding Bloat in Genetic Programming}, year = 2017 }
• 
  Chauhan, Ankit; Friedrich, Tobias; Quinzan, Francesco Approximating Optimization Problems using EAs on Scale-Free Networks. Genetic and Evolutionary Computation Conference (GECCO) 2017
  [ Abstract ] [ BibTeX ] [ Download ]
   
  It has been experimentally observed that real-world networks follow certain topologicalproperties, such as small-world, power-law etc. To study these networks, many random graph models, such as Preferential Attachment, have been proposed. In this paper, we consider the deterministic properties which capture power-law degree distribution and degeneracy. Networks with these properties are known as scale-free networks in the literature. Many interesting problems remain NP-hard on scale-free networks. We study the relationship between scale-free properties and the approximation-ratio of some commonly used evolutionary algorithms. For the Vertex Cover, we observe experimentally that the ((1+1)\) EA always gives the better result than a greedy local search, even when it runs for only (O(n log(n))\) steps. We give the construction of a scale-free network in which a multi-objective algorithm and a greedy algorithm obtain optimal solutions, while the ((1+1)\) EA obtains the worst possible solution with constant probability. We prove that for the Dominating Set, Vertex Cover, Connected Dominating Set and Independent Set, the ((1+1)\) EA obtains constant-factor approximation in expected run time (O(n log(n))\) and (O(n^4)\) respectively. Whereas, GSEMO gives even better approximation than ((1+1)\) EA in expected run time (O(n3)\) for Dominating Set, Vertex Cover and Connected Dominating Set on such networks.
  @inproceedings{chauhan2017approximating, abstract = {It has been experimentally observed that real-world networks follow certain topologicalproperties, such as small-world, power-law etc. To study these networks, many random graph models, such as Preferential Attachment, have been proposed. In this paper, we consider the deterministic properties which capture power-law degree distribution and degeneracy. Networks with these properties are known as scale-free networks in the literature. Many interesting problems remain NP-hard on scale-free networks. We study the relationship between scale-free properties and the approximation-ratio of some commonly used evolutionary algorithms. For the Vertex Cover, we observe experimentally that the ((1+1)\) EA always gives the better result than a greedy local search, even when it runs for only (O(n log(n))\) steps. We give the construction of a scale-free network in which a multi-objective algorithm and a greedy algorithm obtain optimal solutions, while the ((1+1)\) EA obtains the worst possible solution with constant probability. We prove that for the Dominating Set, Vertex Cover, Connected Dominating Set and Independent Set, the ((1+1)\) EA obtains constant-factor approximation in expected run time (O(n log(n))\) and (O(n^4)\) respectively. Whereas, GSEMO gives even better approximation than ((1+1)\) EA in expected run time (O(n3)\) for Dominating Set, Vertex Cover and Connected Dominating Set on such networks.}, author = {Chauhan, Ankit and Friedrich, Tobias and Quinzan, Francesco}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, title = {Approximating Optimization Problems using EAs on Scale-Free Networks}, year = 2017 }
• 
  Friedrich, Tobias; Kötzing, Timo; Melnichenko, Anna Analyzing Search Heuristics with Differential Equations. Genetic and Evolutionary Computation Conference (GECCO) 2017
  [ Abstract ] [ BibTeX ] [ Download ]
   
  Drift Theory is currently the most common technique for the analysis of randomized search heuristics because of its broad applicability and the resulting tight first hitting time bounds. The biggest problem when applying a drift theorem is to find a suitable potential function which maps a complex space into a single number, capturing the essence of the state of the search in just one value. We discuss another method for the analysis of randomized search heuristics based on the Theory of Differential Equations. This method considers the deterministic counterpart of the randomized process by replacing probabilistic outcomes by their expectation, and then bounding the error with good probability. We illustrate this by analyzing an Ant Colony Optimization algorithm (ACO) for the Minimum Spanning Tree problem (MST).
  @inproceedings{friedrich2017analyzing, abstract = {Drift Theory is currently the most common technique for the analysis of randomized search heuristics because of its broad applicability and the resulting tight first hitting time bounds. The biggest problem when applying a drift theorem is to find a suitable potential function which maps a complex space into a single number, capturing the essence of the state of the search in just one value. We discuss another method for the analysis of randomized search heuristics based on the Theory of Differential Equations. This method considers the deterministic counterpart of the randomized process by replacing probabilistic outcomes by their expectation, and then bounding the error with good probability. We illustrate this by analyzing an Ant Colony Optimization algorithm (ACO) for the Minimum Spanning Tree problem (MST).}, author = {Friedrich, Tobias and Kötzing, Timo and Melnichenko, Anna}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, title = {Analyzing Search Heuristics with Differential Equations}, year = 2017 }
• 
  Friedrich, Tobias; Kötzing, Timo; Lagodzinski, J. A. Gregor; Neumann, Frank; Schirneck, Martin Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints. Foundations of Genetic Algorithms (FOGA) 2017: 45-54
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  Linear functions have gained a lot of attention in the area of run time analysis of evolutionary computation methods and the corresponding analyses have provided many effective tools for analyzing more complex problems. In this paper, we consider the behavior of the classical (1+1) Evolutionary Algorithm for linear functions under linear constraint. We show tight bounds in the case where both the objective function and the constraint is given by the OneMax function and present upper bounds as well as lower bounds for the general case. Furthermore, we also consider the LeadingOnes fitness function.
  @inproceedings{DBLP:conf/foga/0001KLNS17, abstract = {Linear functions have gained a lot of attention in the area of run time analysis of evolutionary computation methods and the corresponding analyses have provided many effective tools for analyzing more complex problems. In this paper, we consider the behavior of the classical (1+1) Evolutionary Algorithm for linear functions under linear constraint. We show tight bounds in the case where both the objective function and the constraint is given by the OneMax function and present upper bounds as well as lower bounds for the general case. Furthermore, we also consider the LeadingOnes fitness function.}, author = {Friedrich, Tobias and Kötzing, Timo and Lagodzinski, J. A. Gregor and Neumann, Frank and Schirneck, Martin}, booktitle = {Foundations of Genetic Algorithms (FOGA)}, pages = {45-54}, publisher = {ACM Press}, title = {Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints}, year = 2017 }
• 
  Galanis, Andreas; Göbel, Andreas; Goldberg, Leslie Ann; Lapinskas, John; Richerby, David Amplifiers for the Moran Process. Journal of the ACM 2017: 5:1-5:90
  [ Abstract ] [ BibTeX ] [ URL ] [DOI]
   
  The Moran process, as studied by Lieberman, Hauert, and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlying graph where individuals correspond to vertices. Initially, one vertex (chosen uniformly at random) possesses a mutation, with fitness (r > 1\). All other individuals have fitness 1. During each step of the algorithm, an individual is chosen with probability proportional to its fitness, and its state (mutant or nonmutant) is passed on to an out-neighbour which is chosen uniformly at random. If the underlying graph is strongly connected, then the algorithm will eventually reach fixation, in which all individuals are mutants, or extinction, in which no individuals are mutants. An infinite family of directed graphs is said to be strongly amplifying if, for every (r > 1\), the extinction probability tends to 0 as the number of vertices increases. A formal definition is provided in the article. Strong amplification is a rather surprising property—it means that in such graphs, the fixation probability of a uniformly placed initial mutant tends to 1 even though the initial mutant only has a fixed selective advantage of (r > 1\) (independently of (n\)). The name “strongly amplifying” comes from the fact that this selective advantage is “amplified.” Strong amplifiers have received quite a bit of attention, and Lieberman et al. proposed two potentially strongly amplifying families—superstars and metafunnels. Heuristic arguments have been published, arguing that there are infinite families of superstars that are strongly amplifying. The same has been claimed for metafunnels. In this article, we give the first rigorous proof that there is an infinite family of directed graphs that is strongly amplifying. We call the graphs in the family “megastars.” When the algorithm is run on an (n\)-vertex graph in this family, starting with a uniformly chosen mutant, the extinction probability is roughly (n − 1/2\) (up to logarithmic factors). We prove that all infinite families of superstars and metafunnels have larger extinction probabilities (as a function of (n\)). Finally, we prove that our analysis of megastars is fairly tight—there is no infinite family of megastars such that the Moran algorithm gives a smaller extinction probability (up to logarithmic factors). Also, we provide a counterexample which clarifies the literature concerning the isothermal theorem of Lieberman et al.
  @article{DBLP:journals/jacm/Galanis0GLR17, abstract = {The Moran process, as studied by Lieberman, Hauert, and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlying graph where individuals correspond to vertices. Initially, one vertex (chosen uniformly at random) possesses a mutation, with fitness (r > 1\). All other individuals have fitness 1. During each step of the algorithm, an individual is chosen with probability proportional to its fitness, and its state (mutant or nonmutant) is passed on to an out-neighbour which is chosen uniformly at random. If the underlying graph is strongly connected, then the algorithm will eventually reach fixation, in which all individuals are mutants, or extinction, in which no individuals are mutants. An infinite family of directed graphs is said to be strongly amplifying if, for every (r > 1\), the extinction probability tends to 0 as the number of vertices increases. A formal definition is provided in the article. Strong amplification is a rather surprising property—it means that in such graphs, the fixation probability of a uniformly placed initial mutant tends to 1 even though the initial mutant only has a fixed selective advantage of (r > 1\) (independently of (n\)). The name “strongly amplifying” comes from the fact that this selective advantage is “amplified.” Strong amplifiers have received quite a bit of attention, and Lieberman et al. proposed two potentially strongly amplifying families—superstars and metafunnels. Heuristic arguments have been published, arguing that there are infinite families of superstars that are strongly amplifying. The same has been claimed for metafunnels. In this article, we give the first rigorous proof that there is an infinite family of directed graphs that is strongly amplifying. We call the graphs in the family “megastars.” When the algorithm is run on an (n\)-vertex graph in this family, starting with a uniformly chosen mutant, the extinction probability is roughly (n − 1/2\) (up to logarithmic factors). We prove that all infinite families of superstars and metafunnels have larger extinction probabilities (as a function of (n\)). Finally, we prove that our analysis of megastars is fairly tight—there is no infinite family of megastars such that the Moran algorithm gives a smaller extinction probability (up to logarithmic factors). Also, we provide a counterexample which clarifies the literature concerning the isothermal theorem of Lieberman et al.}, author = {Galanis, Andreas and Göbel, Andreas and Goldberg, Leslie Ann and Lapinskas, John and Richerby, David}, journal = {Journal of the ACM}, number = 1, pages = {5:1-5:90}, title = {Amplifiers for the Moran Process}, volume = 64, year = 2017 }
• 
  Friedrich, Tobias; Kötzing, Timo; Wagner, Markus A Generic Bet-and-Run Strategy for Speeding Up Stochastic Local Search. Association for the Advancement of Artificial Intelligence (AAAI) 2017: 801-807
  [ Abstract ] [ BibTeX ] [ URL ] [ Download ]
   
  A common strategy for improving optimization algorithms is to restart the algorithm when it is believed to be trapped in an inferior part of the search space. However, while specific restart strategies have been developed for specific problems (and specific algorithms), restarts are typically not regarded as a general tool to speed up an optimization algorithm. In fact, many optimization algorithms do not employ restarts at all. Recently, "bet-and-run" was introduced in the context of mixed-integer programming, where first a number of short runs with randomized initial conditions is made, and then the most promising run of these is continued. In this article, we consider two classical NP-complete combinatorial optimization problems, traveling salesperson and minimum vertex cover, and study the effectiveness of different bet-and-run strategies. In particular, our restart strategies do not take any problem knowledge into account, nor are tailored to the optimization algorithm. Therefore, they can be used off-the-shelf. We observe that state-of-the-art solvers for these problems can benefit significantly from restarts on standard benchmark instances.
  @inproceedings{DBLP:conf/aaai/0001K017, abstract = {A common strategy for improving optimization algorithms is to restart the algorithm when it is believed to be trapped in an inferior part of the search space. However, while specific restart strategies have been developed for specific problems (and specific algorithms), restarts are typically not regarded as a general tool to speed up an optimization algorithm. In fact, many optimization algorithms do not employ restarts at all. Recently, "bet-and-run" was introduced in the context of mixed-integer programming, where first a number of short runs with randomized initial conditions is made, and then the most promising run of these is continued. In this article, we consider two classical NP-complete combinatorial optimization problems, traveling salesperson and minimum vertex cover, and study the effectiveness of different bet-and-run strategies. In particular, our restart strategies do not take any problem knowledge into account, nor are tailored to the optimization algorithm. Therefore, they can be used off-the-shelf. We observe that state-of-the-art solvers for these problems can benefit significantly from restarts on standard benchmark instances.}, author = {Friedrich, Tobias and Kötzing, Timo and Wagner, Markus}, booktitle = {Association for the Advancement of Artificial Intelligence (AAAI)}, crossref = {DBLP:conf/aaai/2017}, pages = {801-807}, title = {A Generic Bet-and-Run Strategy for Speeding Up Stochastic Local Search}, year = 2017 }

2016

• 
  Kötzing, Timo; Schirneck, Martin Towards an Atlas of Computational Learning Theory. Symposium on Theoretical Aspects of Computer Science (STACS) 2016: 47:1-47:13
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  A major part of our knowledge about Computational Learning stems from comparisons of the learning power of different learning criteria. These comparisons inform about trade-offs 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 set-driven learning, and two pertaining to strongly monotone learning. These maps can serve as blueprints for future maps of similar base structure.
  @inproceedings{DBLP:conf/stacs/KotzingS16, abstract = {A major part of our knowledge about Computational Learning stems from comparisons of the learning power of different learning criteria. These comparisons inform about trade-offs 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 set-driven learning, and two pertaining to strongly monotone learning. These maps can serve as blueprints for future maps of similar base structure.}, address = {Dagstuhl, Germany}, annote = {Keywords: computational learning, language learning, partially set-driven learning, strongly monotone learning}, author = {Kötzing, Timo and Schirneck, Martin}, booktitle = {Symposium on Theoretical Aspects of Computer Science (STACS)}, pages = {47:1-47:13}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, title = {Towards an Atlas of Computational Learning Theory}, volume = 47, year = 2016 }
• 
  Case, John; Kötzing, Timo Topological Separations in Inductive Inference. Theoretical Computer Science 2016: 33-45
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  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 sub-languages 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.
  @article{DBLP:journals/tcs/CaseK16, abstract = {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 sub-languages 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.}, author = {Case, John and Kötzing, Timo}, journal = {Theoretical Computer Science}, pages = {33-45}, title = {Topological Separations in Inductive Inference}, volume = 620, year = 2016 }
• 
  Doerr, Benjamin; Doerr, Carola; Kötzing, Timo The Right Mutation Strength for Multi-Valued Decision Variables. Genetic and Evolutionary Computation Conference (GECCO) 2016: 1115-1122
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  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 OneMax-like functions defined over (\Omega=\{0,1,…,r−1\}n\). More precisely, we regard a variety of problem classes requesting the component-wise minimization of the distance to an unknown target vector (z in \Omega\). For such problems we see a crucial difference in how we extend the standard-bit mutation operator to these multi-valued 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 (Theta(nrlog n)\). If we change each selected position by either +1 or −1 (random choice), the optimization time reduces to (Theta(nr+nlog n)\). If we use a random mutation strength (i in \{0,1,…,r−1\}n\) with probability inversely proportional to (i\) and change the selected position by either +(i\) or −(i\) (random choice), then the optimization time becomes (Theta(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.
  @inproceedings{DBLP:conf/gecco/DoerrDK16, abstract = {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 OneMax-like functions defined over (\Omega=\{0,1,…,r−1\}n\). More precisely, we regard a variety of problem classes requesting the component-wise minimization of the distance to an unknown target vector (z in \Omega\). For such problems we see a crucial difference in how we extend the standard-bit mutation operator to these multi-valued 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 (Theta(nrlog n)\). If we change each selected position by either +1 or −1 (random choice), the optimization time reduces to (Theta(nr+nlog n)\). If we use a random mutation strength (i in \{0,1,…,r−1\}n\) with probability inversely proportional to (i\) and change the selected position by either +(i\) or −(i\) (random choice), then the optimization time becomes (Theta(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.}, author = {Doerr, Benjamin and Doerr, Carola and Kötzing, Timo}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, crossref = {DBLP:conf/gecco/2016}, pages = {1115-1122}, title = {The Right Mutation Strength for Multi-Valued Decision Variables}, year = 2016 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Schirneck, Martin The Parameterized Complexity of Dependency Detection in Relational Databases. International Symposium on Parameterized and Exact Computation (IPEC) 2016: 6:1--6:13
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  We study the parameterized complexity of classical problems that arise in the profiling of relational data. Namely, we characterize the complexity of detecting unique column combinations (candidate keys), functional dependencies, and inclusion dependencies with the solution size as parameter. While the discovery of uniques and functional dependencies, respectively, turns out to be W[2]-complete, the detection of inclusion dependencies is one of the first natural problems proven to be complete for the class W[3]. As a side effect, our reductions give insights into the complexity of enumerating all minimal unique column combinations or functional dependencies.
  @inproceedings{DBLP:conf/iwpec/Blasius0S16, abstract = {We study the parameterized complexity of classical problems that arise in the profiling of relational data. Namely, we characterize the complexity of detecting unique column combinations (candidate keys), functional dependencies, and inclusion dependencies with the solution size as parameter. While the discovery of uniques and functional dependencies, respectively, turns out to be W[2]-complete, the detection of inclusion dependencies is one of the first natural problems proven to be complete for the class W[3]. As a side effect, our reductions give insights into the complexity of enumerating all minimal unique column combinations or functional dependencies.}, address = {Dagstuhl, Germany}, annote = {Keywords: parameterized complexity, unique column combination, functional dependency, inclusion dependency, profiling relational data}, author = {Bläsius, Thomas and Friedrich, Tobias and Schirneck, Martin}, booktitle = {International Symposium on Parameterized and Exact Computation (IPEC)}, editor = {Guo, Jiong and Hermelin, Danny}, pages = {6:1--6:13}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, title = {The Parameterized Complexity of Dependency Detection in Relational Databases}, volume = 63, year = 2016 }
• 
  Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. The Benefit of Recombination in Noisy Evolutionary Search. Genetic and Evolutionary Computation Conference (GECCO) 2016: 161-162
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  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, randomized search heuristics such as evolutionary algorithms are a popular choice because they are often assumed to exhibit some kind of resistance to noise. Empirical evidence suggests that some algorithms, such as estimation of distribution algorithms (EDAs) are robust against a scaling of the noise intensity, even without resorting to explicit noise-handling techniques such as resampling. In this paper, we want to support such claims with mathematical rigor. We introduce the concept of graceful scaling in which the run time of an algorithm scales polynomially with noise intensity. We study a monotone fitness function over binary strings with additive noise taken from a Gaussian distribution. We show that myopic heuristics cannot efficiently optimize the function under arbitrarily intense noise without any explicit noise-handling. Furthermore, we prove that using a population does not help. Finally we show that a simple EDA called the Compact Genetic Algorithm can overcome the shortsightedness of mutation-only heuristics to scale gracefully with noise. We conjecture that recombinative genetic algorithms also have this property.
  @inproceedings{DBLP:conf/gecco/FriedrichKKS16, abstract = {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, randomized search heuristics such as evolutionary algorithms are a popular choice because they are often assumed to exhibit some kind of resistance to noise. Empirical evidence suggests that some algorithms, such as estimation of distribution algorithms (EDAs) are robust against a scaling of the noise intensity, even without resorting to explicit noise-handling techniques such as resampling. In this paper, we want to support such claims with mathematical rigor. We introduce the concept of graceful scaling in which the run time of an algorithm scales polynomially with noise intensity. We study a monotone fitness function over binary strings with additive noise taken from a Gaussian distribution. We show that myopic heuristics cannot efficiently optimize the function under arbitrarily intense noise without any explicit noise-handling. Furthermore, we prove that using a population does not help. Finally we show that a simple EDA called the Compact Genetic Algorithm can overcome the shortsightedness of mutation-only heuristics to scale gracefully with noise. We conjecture that recombinative genetic algorithms also have this property.}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Sutton, Andrew M.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, pages = {161-162}, title = {The Benefit of Recombination in Noisy Evolutionary Search}, year = 2016 }
• 
  Sutton, Andrew M. Superpolynomial Lower Bounds for the (1+1) EA on Some Easy Combinatorial Problems. Algorithmica 2016: 507-528
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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 2-coloring of a class of bipartite graphs, and constructing satisfying assignments for a class of satisfiable 2-CNF 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 so-called 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 polynomial-time performance guarantee on both problems.
  @article{DBLP:journals/algorithmica/Sutton16, abstract = {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 2-coloring of a class of bipartite graphs, and constructing satisfying assignments for a class of satisfiable 2-CNF 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 so-called 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 polynomial-time performance guarantee on both problems.}, author = {Sutton, Andrew M.}, journal = {Algorithmica}, number = 3, pages = {507-528}, title = {Superpolynomial Lower Bounds for the (1+1) EA on Some Easy Combinatorial Problems}, volume = 75, year = 2016 }
• 
  Case, John; Kötzing, Timo Strongly non-U-shaped language learning results by general techniques. Information and Computation 2016: 1-15
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  In learning, a semantic or behavioral U-shape occurs when a learner first learns, then unlearns, and, finally, relearns, some target concept. This paper introduces two general techniques and applies them especially to syntactic U-shapes 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 so-called self-learning classes of languages which are shown to characterize completely one criterion learning more than another. We apply these techniques to show that, for set-driven and rearrangement-independent learning, any kind of U-shapes is unnecessary. Furthermore, we show that U-shapes are necessary in a strong way for iterative learning, contrasting with an earlier result by Case and Moelius that semantic U-shapes are unnecessary for iterative learning.
  @article{DBLP:journals/iandc/CaseK16, abstract = {In learning, a semantic or behavioral U-shape occurs when a learner first learns, then unlearns, and, finally, relearns, some target concept. This paper introduces two general techniques and applies them especially to syntactic U-shapes 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 so-called self-learning classes of languages which are shown to characterize completely one criterion learning more than another. We apply these techniques to show that, for set-driven and rearrangement-independent learning, any kind of U-shapes is unnecessary. Furthermore, we show that U-shapes are necessary in a strong way for iterative learning, contrasting with an earlier result by Case and Moelius that semantic U-shapes are unnecessary for iterative learning.}, author = {Case, John and Kötzing, Timo}, journal = {Information and Computation}, pages = {1-15}, title = {Strongly non-U-shaped language learning results by general techniques}, volume = 251, year = 2016 }
• 
  Bläsius, Thomas; Rutter, Ignaz Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems. Transactions on Algorithms 2016: 16
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  In this article, we define and study the new problem of SIMULTANEOUS PQ-ORDERING. Its input consists of a set of PQ-trees, which represent sets of circular orders of their leaves, together with a set of child-parent relations between these PQ-trees, such that the leaves of the child form a subset of the leaves of the parent. SIMULTANEOUS PQ-ORDERING asks whether orders of the leaves of each of the trees can be chosen simultaneously; that is, for every child-parent relation, the order chosen for the parent is an extension of the order chosen for the child. We show that SIMULTANEOUS PQ-ORDERING is NP-complete in general, and we identify a family of instances that can be solved efficiently, the 2-fixed instances. We show that this result serves as a framework for several other problems that can be formulated as instances of SIMULTANEOUS PQ-ORDERING. In particular, we give linear-time algorithms for recognizing simultaneous interval graphs and extending partial interval representations. Moreover, we obtain a linear-time algorithm for PARTIALLY PQ-CONSTRAINED PLANARITY for biconnected graphs, which asks for a planar embedding in the presence of 16 PQ-trees that restrict the possible orderings of edges around vertices, and a quadratic-time 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.
  @article{DBLP:journals/talg/BlasiusR16, abstract = {In this article, we define and study the new problem of SIMULTANEOUS PQ-ORDERING. Its input consists of a set of PQ-trees, which represent sets of circular orders of their leaves, together with a set of child-parent relations between these PQ-trees, such that the leaves of the child form a subset of the leaves of the parent. SIMULTANEOUS PQ-ORDERING asks whether orders of the leaves of each of the trees can be chosen simultaneously; that is, for every child-parent relation, the order chosen for the parent is an extension of the order chosen for the child. We show that SIMULTANEOUS PQ-ORDERING is NP-complete in general, and we identify a family of instances that can be solved efficiently, the 2-fixed instances. We show that this result serves as a framework for several other problems that can be formulated as instances of SIMULTANEOUS PQ-ORDERING. In particular, we give linear-time algorithms for recognizing simultaneous interval graphs and extending partial interval representations. Moreover, we obtain a linear-time algorithm for PARTIALLY PQ-CONSTRAINED PLANARITY for biconnected graphs, which asks for a planar embedding in the presence of 16 PQ-trees that restrict the possible orderings of edges around vertices, and a quadratic-time 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.}, author = {Bläsius, Thomas and Rutter, Ignaz}, journal = {Transactions on Algorithms}, number = 2, pages = 16, title = {Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems}, volume = 12, year = 2016 }
• 
  Friedrich, Tobias Scale-Free Networks, Hyperbolic Geometry, and Efficient Algorithms. Symposium on Mathematical Foundations of Computer Science (MFCS) 2016: 4:1-4:3
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  The node degrees of large real-world networks often follow a power-law distribution. Such scale-free 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 scale-free networks (e.g. preferential attachment graphs, Chung-Lu 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, de-anonymization, embedding) and discuss a number of open problems. The talk assumes no prior knowledge about scale-free networks, distributed computing or hyperbolic geometry.
  @inproceedings{DBLP:conf/mfcs/Friedrich16, abstract = {The node degrees of large real-world networks often follow a power-law distribution. Such scale-free 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 scale-free networks (e.g. preferential attachment graphs, Chung-Lu 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, de-anonymization, embedding) and discuss a number of open problems. The talk assumes no prior knowledge about scale-free networks, distributed computing or hyperbolic geometry.}, author = {Friedrich, Tobias}, booktitle = {Symposium on Mathematical Foundations of Computer Science (MFCS)}, pages = {4:1-4:3}, title = {Scale-Free Networks, Hyperbolic Geometry, and Efficient Algorithms}, year = 2016 }
• 
  Baum, Moritz; Bläsius, Thomas; Gemsa, Andreas; Rutter, Ignaz; Wegner, Franziska Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths. European Symposium on Algorithms (ESA) 2016: 7:1-7:18
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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, large-scale 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 linear-time algorithm for minimum-link paths in simple polygons. Experiments in a challenging realistic setting show excellent performance of our algorithms in practice, computing near-optimal solutions in a few milliseconds on average, even for long ranges.
  @inproceedings{DBLP:conf/esa/BaumBGRW16, abstract = {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, large-scale 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 linear-time algorithm for minimum-link paths in simple polygons. Experiments in a challenging realistic setting show excellent performance of our algorithms in practice, computing near-optimal solutions in a few milliseconds on average, even for long ranges.}, author = {Baum, Moritz and Bläsius, Thomas and Gemsa, Andreas and Rutter, Ignaz and Wegner, Franziska}, booktitle = {European Symposium on Algorithms (ESA)}, pages = {7:1-7:18}, title = {Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths}, year = 2016 }
• 
  Gießen, Christian; Kötzing, Timo Robustness of Populations in Stochastic Environments. Algorithmica 2016: 462-489
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  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 (Theta(log n))\) 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.
  @article{DBLP:journals/algorithmica/GiessenK16, abstract = {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 (Theta(log n))\) 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.}, author = {Gießen, Christian and Kötzing, Timo}, journal = {Algorithmica}, number = 3, pages = {462-489}, title = {Robustness of Populations in Stochastic Environments}, volume = 75, year = 2016 }
• 
  Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. Robustness of Ant Colony Optimization to Noise. Evolutionary Computation 2016: 237-254
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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 ((\mu+1)\)-EA outperforms any ACO algorithm, with smaller (\mu\) being better; however, with large noise, the ((\mu+1)\)-EA fails, even for high values of (\mu\) (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 (\delta^2\) of the noise and the dimension (n\) of the search space ((p = o(1/(n(n + delta łog n)^2 łog n)))\), optimization will be successful.
  @article{DBLP:journals/ec/FriedrichKKS16, abstract = {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 ((\mu+1)\)-EA outperforms any ACO algorithm, with smaller (\mu\) being better; however, with large noise, the ((\mu+1)\)-EA fails, even for high values of (\mu\) (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 (\delta^2\) of the noise and the dimension (n\) of the search space ((p = o(1/(n(n + delta łog n)^2 łog n)))\), optimization will be successful.}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Sutton, Andrew M.}, journal = {Evolutionary Computation}, number = 2, pages = {237-254}, title = {Robustness of Ant Colony Optimization to Noise}, volume = 24, year = 2016 }
• 
  Doerr, Benjamin; Doerr, Carola; Kötzing, Timo Provably Optimal Self-Adjusting Step Sizes for Multi-Valued Decision Variables. Parallel Problem Solving From Nature (PPSN) 2016: 782-791
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  We regard the problem of maximizing a OneMax-like 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 achievable 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 self-adjusting 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 comparison-based search heuristics. This is the first time that self-adjusting parameter choices are shown to outperform static choices on a discrete multi-valued optimization problem.
  @inproceedings{DBLP:conf/ppsn/DoerrDK16, abstract = {We regard the problem of maximizing a OneMax-like 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 achievable 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 self-adjusting 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 comparison-based search heuristics. This is the first time that self-adjusting parameter choices are shown to outperform static choices on a discrete multi-valued optimization problem.}, author = {Doerr, Benjamin and Doerr, Carola and Kötzing, Timo}, booktitle = {Parallel Problem Solving From Nature (PPSN)}, pages = {782-791}, title = {Provably Optimal Self-Adjusting Step Sizes for Multi-Valued Decision Variables}, year = 2016 }
• 
  Arndt, Tobias; Hafner, Danijar; Kellermeier, Thomas; Krogmann, Simon; Razmjou, Armin; Krejca, Martin S.; Rothernberger, Ralf; Friedrich, Tobias Probabilistic Routing for On-Street Parking Search. European Symposium on Algorithms (ESA) 2016: 6:1-6:13
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  An estimated (30\%\) of urban traffic is caused by search for parking spots. 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 NP-complete. 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 per-street 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.
  @inproceedings{DBLP:conf/esa/ArndtHKKRKRF16, abstract = {An estimated (30\%\) of urban traffic is caused by search for parking spots. 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 NP-complete. 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 per-street 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.}, author = {Arndt, Tobias and Hafner, Danijar and Kellermeier, Thomas and Krogmann, Simon and Razmjou, Armin and Krejca, Martin S. and Rothernberger, Ralf and Friedrich, Tobias}, booktitle = {European Symposium on Algorithms (ESA)}, pages = {6:1-6:13}, title = {Probabilistic Routing for On-Street Parking Search}, year = 2016 }
• 
  Bläsius, Thomas; Lehmann, Sebastian; Rutter, Ignaz Orthogonal Graph Drawing with Inflexible Edges. Computational Geometry 2016: 26-40
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  We consider the problem of creating plane orthogonal drawings of 4-planar 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 NP-hard if (flex(e)=0\) for every edge (e\) 7. On the other hand, FlexDraw can be solved efficiently if (flex(e) ge 1\) 2 and is trivial if (flex(e) ge 2\) 1 for every edge (e\). To close the gap between the NP-hardness for (flex(e)=0\) and the efficient algorithm for (flex(e) ge 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 (epsilon > 0\) FlexDraw is NP-complete for instances with (O(n^\epsilon)\) inflexible edges with pairwise distance (Omega(n^{1−\epsilon})\) (including the case where they induce a matching). On the other hand, we give an FPT-algorithm 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.
  @article{DBLP:journals/comgeo/BlasiusLR16, abstract = {We consider the problem of creating plane orthogonal drawings of 4-planar 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 NP-hard if (flex(e)=0\) for every edge (e\) 7. On the other hand, FlexDraw can be solved efficiently if (flex(e) ge 1\) 2 and is trivial if (flex(e) ge 2\) 1 for every edge (e\). To close the gap between the NP-hardness for (flex(e)=0\) and the efficient algorithm for (flex(e) ge 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 (epsilon > 0\) FlexDraw is NP-complete for instances with (O(n^\epsilon)\) inflexible edges with pairwise distance (Omega(n^{1−\epsilon})\) (including the case where they induce a matching). On the other hand, we give an FPT-algorithm 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.}, author = {Bläsius, Thomas and Lehmann, Sebastian and Rutter, Ignaz}, journal = {Computational Geometry}, pages = {26-40}, title = {Orthogonal Graph Drawing with Inflexible Edges}, volume = 55, year = 2016 }
• 
  Bläsius, Thomas; Rutter, Ignaz; Wagner, Dorothea Optimal Orthogonal Graph Drawing with Convex Bend Costs. Transactions on Algorithms 2016: 33
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  Traditionally, the quality of orthogonal planar drawings is quantified by the total number off 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 (4-planar graph) and for each edge (e\) a cost function (cost_e colon N_0 rightarrow 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 NP-hard. 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 minimum-cost flow in a planar network with multiple sources and sinks. Our result is the first polynomial-time bend-optimization algorithm for general 4-planar graphs optimizing over all embeddings. Previous work considers restricted graph classes and unit costs.
  @article{DBLP:journals/talg/BlasiusRW16, abstract = {Traditionally, the quality of orthogonal planar drawings is quantified by the total number off 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 (4-planar graph) and for each edge (e\) a cost function (cost_e colon N_0 rightarrow 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 NP-hard. 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 minimum-cost flow in a planar network with multiple sources and sinks. Our result is the first polynomial-time bend-optimization algorithm for general 4-planar graphs optimizing over all embeddings. Previous work considers restricted graph classes and unit costs.}, author = {Bläsius, Thomas and Rutter, Ignaz and Wagner, Dorothea}, journal = {Transactions on Algorithms}, number = 3, pages = 33, title = {Optimal Orthogonal Graph Drawing with Convex Bend Costs}, volume = 12, year = 2016 }
• 
  Jain, Sanjay; Kötzing, Timo; Ma, Junqi; Stephan, Frank On the Role of Update Constraints and Text-Types in Iterative Learning. Information and Computation 2016: 152-168
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  The present work investigates the relationship of iterative learning with other learning criteria such as decisiveness, caution, reliability, non-U-shapedness, monotonicity, strong monotonicity and conservativeness. Building on the result of Case and Moelius that iterative learners can be made non-U-shaped, we show that they also can be made cautious and decisive. Furthermore, we obtain various special results with respect to one-one texts, fat texts and one-one hypothesis spaces.
  @article{DBLP:journals/iandc/JainKMS16, abstract = {The present work investigates the relationship of iterative learning with other learning criteria such as decisiveness, caution, reliability, non-U-shapedness, monotonicity, strong monotonicity and conservativeness. Building on the result of Case and Moelius that iterative learners can be made non-U-shaped, we show that they also can be made cautious and decisive. Furthermore, we obtain various special results with respect to one-one texts, fat texts and one-one hypothesis spaces.}, author = {Jain, Sanjay and Kötzing, Timo and Ma, Junqi and Stephan, Frank}, journal = {Information and Computation}, pages = {152-168}, title = {On the Role of Update Constraints and Text-Types in Iterative Learning}, volume = 247, year = 2016 }
• 
  Friedrich, Tobias; Kötzing, Timo; Sutton, Andrew M. On the Robustness of Evolving Populations. Parallel Problem Solving From Nature (PPSN) 2016: 771-781
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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 (\emph{mutational}\) 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.
  @inproceedings{DBLP:conf/ppsn/FriedrichKS16, abstract = {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 (\emph{mutational}\) 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.}, author = {Friedrich, Tobias and Kötzing, Timo and Sutton, Andrew M.}, booktitle = {Parallel Problem Solving From Nature (PPSN)}, pages = {771-781}, title = {On the Robustness of Evolving Populations}, year = 2016 }
• 
  Chauhan, Ankit; Lenzner, Pascal; Melnichenko, Anna; Münn, Martin On Selfish Creation of Robust Networks. Symposium on Algorithmic Game Theory (SAGT) 2016: 141-152
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  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, Internet-like 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 edge-failure. 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 non-robust 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.
  @inbook{Chauhan2016, abstract = {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, Internet-like 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 edge-failure. 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 non-robust 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.}, address = {Berlin, Heidelberg}, author = {Chauhan, Ankit and Lenzner, Pascal and Melnichenko, Anna and Münn, Martin}, booktitle = {Symposium on Algorithmic Game Theory (SAGT)}, editor = {Gairing, Martin and Savani, Rahul}, pages = {141-152}, publisher = {Springer Berlin Heidelberg}, title = {On Selfish Creation of Robust Networks}, year = 2016 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton Hyperbolic Random Graphs: Separators and Treewidth. European Symposium on Algorithms (ESA) 2016: 15:1-15:16
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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 worst-case run-time is then replaced by the expected run-time 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 real-world networks as they share many important properties such as a small diameter, a large clustering coefficient, and a power-law degree-distribution. 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 power-law exponent). We infer that these graphs have whp a treewidth of (O(sqrt(n^(3 - \beta)}))\), (O(\log^{2}n)\), 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.
  @inproceedings{DBLP:conf/esa/BlasiusFK16, abstract = {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 worst-case run-time is then replaced by the expected run-time 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 real-world networks as they share many important properties such as a small diameter, a large clustering coefficient, and a power-law degree-distribution. 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 power-law exponent). We infer that these graphs have whp a treewidth of (O(sqrt(n^(3 - \beta)}))\), (O(\log^{2}n)\), 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.}, author = {Bläsius, Thomas and Friedrich, Tobias and Krohmer, Anton}, booktitle = {European Symposium on Algorithms (ESA)}, pages = {15:1-15:16}, title = {Hyperbolic Random Graphs: Separators and Treewidth}, year = 2016 }
• 
  Chauhan, Ankit; Friedrich, Tobias; Rothenberger, Ralf Greed is Good for Deterministic Scale-Free Networks. Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2016: 33:1-33:15
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  Large real-world networks typically follow a power-law degree distribution. To study such networks, numerous random graph models have been proposed. However, real-world networks are not drawn at random. Therefore, Brach, Cygan, Lacki, and Sankowski [SODA 2016] introduced two natural deterministic conditions: (1) a power-law upper bound on the degree distribution (PLB-U) and (2) power-law neighborhoods, that is, the degree distribution of neighbors of each vertex is also upper bounded by a power law (PLB-N). They showed that many real-world 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 well-studied random graph models exhibit both the mentioned PLB properties and additionally also a power-law lower bound on the degree distribution (PLB-L). All three properties hold with high probability for Chung-Lu 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 NP-hard combinatorial optimization problems on PLB networks. It is known that on general graphs with maximum degree (\Delta\), a greedy algorithm, which chooses nodes in the order of their degree, only achieves a (Omega(ln \Delta)\)-approximation for Minimum Vertex Cover and Minimum Dominating Set, and a (Omega(\Delta)\)-approximation for Maximum Independent Set. We prove that the PLB-U property suffices for the greedy approach to achieve a constant-factor approximation for all three problems. We also show that all three combinatorial optimization problems are APX-complete even if all PLB-properties holds hence, PTAS cannot be expected unless P=NP.
  @inproceedings{DBLP:conf/fsttcs/Chauhan0R16, abstract = {Large real-world networks typically follow a power-law degree distribution. To study such networks, numerous random graph models have been proposed. However, real-world networks are not drawn at random. Therefore, Brach, Cygan, Lacki, and Sankowski [SODA 2016] introduced two natural deterministic conditions: (1) a power-law upper bound on the degree distribution (PLB-U) and (2) power-law neighborhoods, that is, the degree distribution of neighbors of each vertex is also upper bounded by a power law (PLB-N). They showed that many real-world 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 well-studied random graph models exhibit both the mentioned PLB properties and additionally also a power-law lower bound on the degree distribution (PLB-L). All three properties hold with high probability for Chung-Lu 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 NP-hard combinatorial optimization problems on PLB networks. It is known that on general graphs with maximum degree (\Delta\), a greedy algorithm, which chooses nodes in the order of their degree, only achieves a (Omega(ln \Delta)\)-approximation for Minimum Vertex Cover and Minimum Dominating Set, and a (Omega(\Delta)\)-approximation for Maximum Independent Set. We prove that the PLB-U property suffices for the greedy approach to achieve a constant-factor approximation for all three problems. We also show that all three combinatorial optimization problems are APX-complete even if all PLB-properties holds hence, PTAS cannot be expected unless P=NP.}, author = {Chauhan, Ankit and Friedrich, Tobias and Rothenberger, Ralf}, booktitle = {Foundations of Software Technology and Theoretical Computer Science (FSTTCS)}, pages = {33:1-33:15}, title = {Greed is Good for Deterministic Scale-Free Networks}, year = 2016 }
• 
  Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. Graceful Scaling on Uniform versus Steep-Tailed Noise. Parallel Problem Solving From Nature (PPSN) 2016: 761-770
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  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.
  @inproceedings{DBLP:conf/ppsn/FriedrichKKS16, abstract = {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.}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Sutton, Andrew M.}, booktitle = {Parallel Problem Solving From Nature (PPSN)}, pages = {761-770}, title = {Graceful Scaling on Uniform versus Steep-Tailed Noise}, year = 2016 }
• 
  Gao, Wanru; Friedrich, Tobias; Neumann, Frank Fixed-Parameter Single Objective Search Heuristics for Minimum Vertex Cover. Parallel Problem Solving From Nature (PPSN) 2016: 740-750
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  We consider how well-known 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 state-of-the-art 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.
  @inproceedings{DBLP:conf/ppsn/GaoFN16, abstract = {We consider how well-known 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 state-of-the-art 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.}, author = {Gao, Wanru and Friedrich, Tobias and Neumann, Frank}, booktitle = {Parallel Problem Solving From Nature (PPSN)}, pages = {740-750}, title = {Fixed-Parameter Single Objective Search Heuristics for Minimum Vertex Cover}, year = 2016 }
• 
  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: 661-668
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  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+\delta\), we require only (O(log 1/delta + 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-\epsilon)})\). Our second scenario is a family of vertex cover instances. Majority vote optimizes this family efficiently, while local searches fail and only highly specialized two-parent crossovers are successful.
  @inproceedings{DBLP:conf/gecco/FriedrichKKNNS16, abstract = {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+\delta\), we require only (O(log 1/delta + 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-\epsilon)})\). Our second scenario is a family of vertex cover instances. Majority vote optimizes this family efficiently, while local searches fail and only highly specialized two-parent crossovers are successful.}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Nallaperuma, Samadhi and Neumann, Frank and Schirneck, Martin}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, pages = {661-668}, publisher = {ACM Press}, title = {Fast Building Block Assembly by Majority Vote Crossover}, year = 2016 }
• 
  Dang, Duc-Cuong; 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: 645-652
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  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 ((\mu+1)\) GA using uniform crossover on the fitness function (Jump_k\). 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 (\mu\), 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 (\mu\): (O(n^{k-1})\) 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 single-receiver island model. This proves a sizeable advantage of all variants of the ((\mu+1)\) GA compared to the (1+1) EA, which requires (Theta(n^k)\). In a short empirical study we confirm that the asymptotic differences can also be observed experimentally.
  @inproceedings{DBLP:conf/gecco/DangFKKLOSS16, abstract = {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 ((\mu+1)\) GA using uniform crossover on the fitness function (Jump_k\). 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 (\mu\), 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 (\mu\): (O(n^{k-1})\) 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 single-receiver island model. This proves a sizeable advantage of all variants of the ((\mu+1)\) GA compared to the (1+1) EA, which requires (Theta(n^k)\). In a short empirical study we confirm that the asymptotic differences can also be observed experimentally.}, author = {Dang, Duc-Cuong and Friedrich, Tobias and Krejca, Martin S. and Kötzing, Timo and Lehre, Per Kristian and Oliveto, Pietro S. and Sudholt, Dirk and Sutton, Andrew Michael}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, pages = {645-652}, publisher = {ACM Press}, title = {Escaping Local Optima with Diversity Mechanisms and Crossover}, year = 2016 }
• 
  Jain, Sanjay; Kötzing, Timo; Stephan, Frank Enlarging learnable classes. Information and Computation 2016: 194-207
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  We study which classes of recursive functions satisfy that their union with any other explanatorily learnable class of recursive functions is again explanatorily learnable. We provide sufficient criteria for classes of recursive functions to satisfy this property and also investigate its effective variants. Furthermore, we study the question which learners can be effectively extended to learn a larger class of functions. We solve an open problem by showing that there is no effective procedure which does this task on all learners which do not learn a dense class of recursive functions. However, we show that there are two effective extension procedures such that each learner is extended by one of them.
  @article{DBLP:journals/iandc/JainKS16, abstract = {We study which classes of recursive functions satisfy that their union with any other explanatorily learnable class of recursive functions is again explanatorily learnable. We provide sufficient criteria for classes of recursive functions to satisfy this property and also investigate its effective variants. Furthermore, we study the question which learners can be effectively extended to learn a larger class of functions. We solve an open problem by showing that there is no effective procedure which does this task on all learners which do not learn a dense class of recursive functions. However, we show that there are two effective extension procedures such that each learner is extended by one of them.}, author = {Jain, Sanjay and Kötzing, Timo and Stephan, Frank}, journal = {Information and Computation}, pages = {194-207}, title = {Enlarging learnable classes}, volume = 251, year = 2016 }
• 
  Dang, Duc-Cuong; 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: 890-900
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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 mutation-only algorithms like the ((1+1)\) EA.
  @inproceedings{DBLP:conf/ppsn/DangFKKLOSS16, abstract = {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 mutation-only algorithms like the ((1+1)\) EA.}, author = {Dang, Duc-Cuong and Lehre, Per Kristian and Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Oliveto, Pietro S. and Sudholt, Dirk and Sutton, Andrew M.}, booktitle = {Parallel Problem Solving From Nature (PPSN)}, pages = {890-900}, title = {Emergence of Diversity and its Benefits for Crossover in Genetic Algorithms}, year = 2016 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton; Laue, Sören Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane. European Symposium on Algorithms (ESA) 2016: 16:1-16:18
  Best Paper
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  Hyperbolic geometry appears to be intrinsic in many large real networks. We construct and implement a new maximum likelihood estimation algorithm that embeds scale-free 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 Log-likelihood and greedy routing our algorithm discovers embeddings that are very close to the ground truth.
  @inproceedings{DBLP:conf/esa/BlasiusFKL16, abstract = {Hyperbolic geometry appears to be intrinsic in many large real networks. We construct and implement a new maximum likelihood estimation algorithm that embeds scale-free 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 Log-likelihood and greedy routing our algorithm discovers embeddings that are very close to the ground truth.}, author = {Bläsius, Thomas and Friedrich, Tobias and Krohmer, Anton and Laue, Sören}, booktitle = {European Symposium on Algorithms (ESA)}, note = {Best Paper}, pages = {16:1-16:18}, title = {Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane}, year = 2016 }
• 
  Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S. EDAs cannot be Balanced and Stable. Genetic and Evolutionary Computation Conference (GECCO) 2016: 1139-1146
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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, (\lambda\)-MMASIB, cGA, and ((1,\lambda)\)-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 well-known EDAs are balanced and thus not stable, they are not well-suited to optimize LeadingOnes. We give a stable EDA which optimizes LeadingOnes within a time of (O(n log n)\).
  @inproceedings{DBLP:conf/gecco/FriedrichKK16, abstract = {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, (\lambda\)-MMASIB, cGA, and ((1,\lambda)\)-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 well-known EDAs are balanced and thus not stable, they are not well-suited to optimize LeadingOnes. We give a stable EDA which optimizes LeadingOnes within a time of (O(n log n)\).}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, pages = {1139-1146}, publisher = {ACM Press}, title = {EDAs cannot be Balanced and Stable}, type = {Publication}, year = 2016 }
• 
  Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David Counting Homomorphisms to Square-Free Graphs, Modulo 2. Transactions on Computation Theory 2016: 12:1-12:29
  [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  @article{DBLP:journals/toct/0001GR16, author = {Göbel, Andreas and Goldberg, Leslie Ann and Richerby, David}, journal = {Transactions on Computation Theory}, number = 3, pages = {12:1-12:29}, title = {Counting Homomorphisms to Square-Free Graphs, Modulo 2}, volume = 8, year = 2016 }
• 
  Kötzing, Timo Concentration of First Hitting Times Under Additive Drift. Algorithmica 2016: 490-506
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  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's-Ruin-like 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 so-called negative drift theorem, for which we give new variants.
  @article{DBLP:journals/algorithmica/Kotzing16, abstract = {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's-Ruin-like 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 so-called negative drift theorem, for which we give new variants.}, author = {Kötzing, Timo}, journal = {Algorithmica}, number = 3, pages = {490-506}, title = {Concentration of First Hitting Times Under Additive Drift}, volume = 75, year = 2016 }
• 
  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: 3-4
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  Despite the pervasiveness of noise in real-world optimization, there is little understanding of the interplay between the operators of randomized search heuristics and explicit noise-handling techniques such as statistical resampling. Ant Colony Optimization (ACO) algorithms are claimed to be particularly well-suited to dynamic and noisy problems, even without explicit noise-handling techniques. In this work, we empirically investigate the trade-offs between resampling an the noise-handling abilities of ACO algorithms. Our main focus is to locate the point where resampling costs more than it is worth.
  @inproceedings{DBLP:conf/gecco/FriedrichKQS16, abstract = {Despite the pervasiveness of noise in real-world optimization, there is little understanding of the interplay between the operators of randomized search heuristics and explicit noise-handling techniques such as statistical resampling. Ant Colony Optimization (ACO) algorithms are claimed to be particularly well-suited to dynamic and noisy problems, even without explicit noise-handling techniques. In this work, we empirically investigate the trade-offs between resampling an the noise-handling abilities of ACO algorithms. Our main focus is to locate the point where resampling costs more than it is worth.}, author = {Friedrich, Tobias and Kötzing, Timo and Quinzan, Francesco and Sutton, Andrew M.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, pages = {3-4}, title = {Ant Colony Optimization Beats Resampling on Noisy Functions}, year = 2016 }
• 
  Galanis, Andreas; Göbel, Andreas; Goldberg, Leslie-Ann; Lapinskas, John; Richerby, David Amplifiers for the Moran Process. International Colloquium on Automata, Languages and Programming (ICALP) 2016: 62:1-62:13
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  The Moran process, as studied by Lieberman, Hauert and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlying graph where individuals correspond to vertices. Initially, one vertex (chosen uniformly at random) possesses a mutation, with fitness (r > 1\). All other individuals have fitness 1. During each step of the algorithm, an individual is chosen with probability proportional to its fitness, and its state (mutant or non-mutant) is passed on to an out-neighbour which is chosen uniformly at random. If the underlying graph is strongly connected then the algorithm will eventually reach fixation, in which all individuals are mutants, or extinction, in which no individuals are mutants. An infinite family of directed graphs is said to be strongly amplifying if, for every (r > 1\), the extinction probability tends to 0 as the number of vertices increases. Strong amplification is a rather surprising property - it means that in such graphs, the fixation probability of a uniformly-placed initial mutant tends to 1 even though the initial mutant only has a fixed selective advantage of (r > 1\) (independently of (n\)). The name "strongly amplifying" comes from the fact that this selective advantage is "amplified". Strong amplifiers have received quite a bit of attention, and Lieberman et al. proposed two potentially strongly-amplifying families - superstars and metafunnels. Heuristic arguments have been published, arguing that there are infinite families of superstars that are strongly amplifying. The same has been claimed for metafunnels. We give the first rigorous proof that there is an infinite family of directed graphs that is strongly amplifying. We call the graphs in the family "megastars". When the algorithm is run on an n-vertex graph in this family, starting with a uniformly-chosen mutant, the extinction probability is roughly (n^{-1/2}\) (up to logarithmic factors). We prove that all infinite families of superstars and metafunnels have larger extinction probabilities (as a function of (n\)). Finally, we prove that our analysis of megastars is fairly tight - there is no infinite family of megastars such that the Moran algorithm gives a smaller extinction probability (up to logarithmic factors). Also, we provide a counterexample which clarifies the literature concerning the isothermal theorem of Lieberman et al. A full version [Galanis/Göbel/Goldberg/Lapinskas/Richerby, Preprint] containing detailed proofs is available at http://arxiv.org/abs/1512.05632. Theorem-numbering here matches the full version.
  @inproceedings{DBLP:conf/icalp/Galanis0GLR16, abstract = {The Moran process, as studied by Lieberman, Hauert and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlying graph where individuals correspond to vertices. Initially, one vertex (chosen uniformly at random) possesses a mutation, with fitness (r > 1\). All other individuals have fitness 1. During each step of the algorithm, an individual is chosen with probability proportional to its fitness, and its state (mutant or non-mutant) is passed on to an out-neighbour which is chosen uniformly at random. If the underlying graph is strongly connected then the algorithm will eventually reach fixation, in which all individuals are mutants, or extinction, in which no individuals are mutants. An infinite family of directed graphs is said to be strongly amplifying if, for every (r > 1\), the extinction probability tends to 0 as the number of vertices increases. Strong amplification is a rather surprising property - it means that in such graphs, the fixation probability of a uniformly-placed initial mutant tends to 1 even though the initial mutant only has a fixed selective advantage of (r > 1\) (independently of (n\)). The name "strongly amplifying" comes from the fact that this selective advantage is "amplified". Strong amplifiers have received quite a bit of attention, and Lieberman et al. proposed two potentially strongly-amplifying families - superstars and metafunnels. Heuristic arguments have been published, arguing that there are infinite families of superstars that are strongly amplifying. The same has been claimed for metafunnels. We give the first rigorous proof that there is an infinite family of directed graphs that is strongly amplifying. We call the graphs in the family "megastars". When the algorithm is run on an n-vertex graph in this family, starting with a uniformly-chosen mutant, the extinction probability is roughly (n^{-1/2}\) (up to logarithmic factors). We prove that all infinite families of superstars and metafunnels have larger extinction probabilities (as a function of (n\)). Finally, we prove that our analysis of megastars is fairly tight - there is no infinite family of megastars such that the Moran algorithm gives a smaller extinction probability (up to logarithmic factors). Also, we provide a counterexample which clarifies the literature concerning the isothermal theorem of Lieberman et al. A full version [Galanis/Göbel/Goldberg/Lapinskas/Richerby, Preprint] containing detailed proofs is available at http://arxiv.org/abs/1512.05632. Theorem-numbering here matches the full version.}, author = {Galanis, Andreas and Göbel, Andreas and Goldberg, Leslie-Ann and Lapinskas, John and Richerby, David}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, pages = {62:1-62:13}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, series = {LIPIcs}, title = {Amplifiers for the Moran Process}, volume = 55, year = 2016 }
• 
  Bläsius, Thomas; Rutter, Ignaz A new perspective on clustered planarity as a combinatorial embedding problem. Theoretical Computer Science 2016: 306-315
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  The clustered planarity problem (c-planarity) asks whether a hierarchically clustered graph admits a planar drawing such that the clusters can be nicely represented by regions. We introduce the cd-tree data structure and give a new characterization of c-planarity. It leads to efficient algorithms for c-planarity testing in the following cases. (i) Every cluster and every co-cluster (complement of a cluster) has at most two connected components. (ii) Every cluster has at most five outgoing edges. Moreover, the cd-tree reveals interesting connections between c-planarity 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 c-planarity, on the other hand it provides a new perspective on previous results.
  @article{DBLP:journals/tcs/BlasiusR16, abstract = {The clustered planarity problem (c-planarity) asks whether a hierarchically clustered graph admits a planar drawing such that the clusters can be nicely represented by regions. We introduce the cd-tree data structure and give a new characterization of c-planarity. It leads to efficient algorithms for c-planarity testing in the following cases. (i) Every cluster and every co-cluster (complement of a cluster) has at most two connected components. (ii) Every cluster has at most five outgoing edges. Moreover, the cd-tree reveals interesting connections between c-planarity 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 c-planarity, on the other hand it provides a new perspective on previous results.}, author = {Bläsius, Thomas and Rutter, Ignaz}, journal = {Theoretical Computer Science}, pages = {306-315}, title = {A new perspective on clustered planarity as a combinatorial embedding problem}, volume = 609, year = 2016 }
• 
  Kötzing, Timo; Palenta, Raphaela A map of update constraints in inductive inference. Theoretical Computer Science 2016: 4-24
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  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 set-driven learning. This completes the picture for these well-studied 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.
  @article{DBLP:journals/tcs/KotzingP16, abstract = {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 set-driven learning. This completes the picture for these well-studied 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.}, author = {Kötzing, Timo and Palenta, Raphaela}, journal = {Theoretical Computer Science}, pages = {4-24}, title = {A map of update constraints in inductive inference}, volume = 650, year = 2016 }

2015

• 
  Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton Unbounded Discrepancy of Deterministic Random Walks on Grids. International Symposium on Algorithms and Computation (ISAAC) 2015: 212-222
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  Random walks are frequently used in randomized algorithms. We study a derandomized variant of a random walk on graphs, called rotor-router 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 rotor-router 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 (Z^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 (Z^d\). We show that this assumption is crucial by proving that otherwise the single vertex discrepancy can become arbitrarily large. For all dimensions (d ge 1\) and arbitrary discrepancies (ell ge 0\), we construct configurations that reach a discrepancy of at least (\ell\).
  @inproceedings{DBLP:conf/isaac/FriedrichKK15, abstract = {Random walks are frequently used in randomized algorithms. We study a derandomized variant of a random walk on graphs, called rotor-router 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 rotor-router 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 (Z^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 (Z^d\). We show that this assumption is crucial by proving that otherwise the single vertex discrepancy can become arbitrarily large. For all dimensions (d ge 1\) and arbitrary discrepancies (ell ge 0\), we construct configurations that reach a discrepancy of at least (\ell\).}, author = {Friedrich, Tobias and Katzmann, Maximilian and Krohmer, Anton}, booktitle = {International Symposium on Algorithms and Computation (ISAAC)}, pages = {212-222}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Unbounded Discrepancy of Deterministic Random Walks on Grids}, volume = 9472, year = 2015 }
• 
  Doerr, Benjamin; Doerr, Carola; Kötzing, Timo Unbiased Black-Box Complexities of Jump Functions. Evolutionary Computation 2015: 641-670
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  We analyze the unbiased black-box 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−\epsilon)n\), that is, only a small constant fraction of the fitness values is visible, then the unbiased black-box 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, polynomial-time mutation-based (i.e., unary unbiased) black-box optimization algorithms exist. This is quite surprising given that for the extreme jump function almost the whole search space (all but a (Theta(n^−1/2)\) fraction) is a plateau of constant fitness. To prove these results, we introduce new tools for the analysis of unbiased black-box 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.
  @article{DBLP:journals/ec/DoerrDK15, abstract = {We analyze the unbiased black-box 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−\epsilon)n\), that is, only a small constant fraction of the fitness values is visible, then the unbiased black-box 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, polynomial-time mutation-based (i.e., unary unbiased) black-box optimization algorithms exist. This is quite surprising given that for the extreme jump function almost the whole search space (all but a (Theta(n^−1/2)\) fraction) is a plateau of constant fitness. To prove these results, we introduce new tools for the analysis of unbiased black-box 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.}, author = {Doerr, Benjamin and Doerr, Carola and Kötzing, Timo}, journal = {Evolutionary Computation}, number = 4, pages = {641-670}, title = {Unbiased Black-Box Complexities of Jump Functions}, volume = 23, year = 2015 }
• 
  Bringmann, Karl; Friedrich, Tobias; Hoefer, Martin; Rothenberger, Ralf; Sauerwald, Thomas Ultra-Fast Load Balancing on Scale-Free Networks. International Colloquium on Automata, Languages and Programming (ICALP) 2015: 516-527
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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 scale-free networks by Chung-Lu random graphs and analyze a simple local algorithm for iterative load balancing. On n-node graphs our distributed algorithm balances the load within (O((loglog n)^2)\) steps. It does not need to know the exponent (beta in (2,3)\) of the power-law 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 load-balancing can be done in double-logarithmic time on realistic graph classes.
  @inproceedings{DBLP:conf/icalp/BringmannFHRS15, abstract = {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 scale-free networks by Chung-Lu random graphs and analyze a simple local algorithm for iterative load balancing. On n-node graphs our distributed algorithm balances the load within (O((loglog n)^2)\) steps. It does not need to know the exponent (beta in (2,3)\) of the power-law 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 load-balancing can be done in double-logarithmic time on realistic graph classes.}, author = {Bringmann, Karl and Friedrich, Tobias and Hoefer, Martin and Rothenberger, Ralf and Sauerwald, Thomas}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, pages = {516-527}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Ultra-Fast Load Balancing on Scale-Free Networks}, volume = 9135, year = 2015 }
• 
  Paixão, Tiago; Badkobeh, Golnaz; Barton, Nick H.; Çörüş, Doğan; Dang, Duc-Cuong; Friedrich, Tobias; Lehre, Per Kristian; Sudholt, Dirk; Sutton, Andrew; Trubenová, Barbora Toward a unifying framework for evolutionary processes. Journal of Theoretical Biology 2015: 28-43
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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.
  @article{JTB1, abstract = {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.}, author = {Paixão, Tiago and Badkobeh, Golnaz and Barton, Nick H. and Çörüş, Doğan and Dang, Duc-Cuong and Friedrich, Tobias and Lehre, Per Kristian and Sudholt, Dirk and Sutton, Andrew and Trubenová, Barbora}, journal = {Journal of Theoretical Biology}, pages = {28-43}, publisher = {Elsevier}, title = {Toward a unifying framework for evolutionary processes}, volume = 383, year = 2015 }
• 
  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: 140-150
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  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 meta-heuristics 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 ((\mu+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.
  @inproceedings{DBLP:conf/isaac/FriedrichKKS15, abstract = {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 meta-heuristics 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 ((\mu+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.}, address = {Berlin, Heidelberg}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Sutton, Andrew M.}, booktitle = {International Symposium of Algorithms and Computation (ISAAC)}, editor = {Elbassioni, Khaled and Makino, Kazuhisa}, pages = {140-150}, publisher = {Springer Berlin Heidelberg}, title = {The Benefit of Recombination in Noisy Evolutionary Search}, year = 2015 }
• 
  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: 831--838
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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 real-world 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.
  @inproceedings{DBLP:conf/gecco/DoerrDK15, abstract = {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 real-world 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.}, author = {Doerr, Benjamin and Doerr, Carola and Kötzing, Timo}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, pages = {831--838}, publisher = {ACM}, title = {Solving Problems with Unknown Solution Length at (Almost) No Extra Cost}, year = 2015 }
• 
  Friedrich, Tobias; Wagner, Markus Seeding the initial population of multi-objective evolutionary algorithms: A computational study. Applied Soft Computing 2015: 223-230
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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 problem-specific method. This seeding has been studied extensively for single-objective problems. For multi-objective 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 real-valued 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.
  @article{DBLP:journals/asc/Friedrich015, abstract = {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 problem-specific method. This seeding has been studied extensively for single-objective problems. For multi-objective 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 real-valued 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.}, author = {Friedrich, Tobias and Wagner, Markus}, journal = {Applied Soft Computing}, pages = {223-230}, title = {Seeding the initial population of multi-objective evolutionary algorithms: A computational study}, volume = 33, year = 2015 }
• 
  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: 17-24
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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 ((\mu+1)\)-EA outperforms any ACO algorithm, with smaller (\mu\) being better; however, with large noise, the ((\mu+1)\)-EA fails, even for high values of (\mu\) (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 (\mu\) is small enough dependent on the parameter (\delta^2\) of the noise and the dimension (n\) of the search space ((p = o(1/(n(n + delta log n)^2 log n)))\), optimization will be successful.
  @inproceedings{DBLP:conf/gecco/FriedrichKKS15, abstract = {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 ((\mu+1)\)-EA outperforms any ACO algorithm, with smaller (\mu\) being better; however, with large noise, the ((\mu+1)\)-EA fails, even for high values of (\mu\) (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 (\mu\) is small enough dependent on the parameter (\delta^2\) of the noise and the dimension (n\) of the search space ((p = o(1/(n(n + delta log n)^2 log n)))\), optimization will be successful.}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Sutton, Andrew M.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, pages = {17-24}, publisher = {ACM}, title = {Robustness of Ant Colony Optimization to Noise}, year = 2015 }
• 
  Berenbrink, Petra; Cooper, Colin; Friedetzky, Tom; Friedrich, Tobias; Sauerwald, Thomas Randomized diffusion for indivisible loads. Journal of Computer and System Sciences 2015: 159-185
  [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  @article{DBLP:journals/jcss/BerenbrinkCFFS15, author = {Berenbrink, Petra and Cooper, Colin and Friedetzky, Tom and Friedrich, Tobias and Sauerwald, Thomas}, journal = {Journal of Computer and System Sciences}, number = 1, pages = {159-185}, title = {Randomized diffusion for indivisible loads}, volume = 81, year = 2015 }
• 
  Nguyen, Anh Quang; Sutton, Andrew M.; Neumann, Frank Population size matters: Rigorous runtime results for maximizing the hypervolume indicator. Theoretical Computer Science 2015: 24-36
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  Using the hypervolume indicator to guide the search of evolutionary multi-objective 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 multi-objective variants of the problems OneMax and LeadingOnes called OMM and LOTZ, respectively, and investigate hypervolume-based 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 hypervolume-based evolutionary multi-objective algorithms which is contrary to the results on their single-objective variants and the well-studied (1+1)-EA.
  @article{DBLP:journals/tcs/NguyenSN15, abstract = {Using the hypervolume indicator to guide the search of evolutionary multi-objective 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 multi-objective variants of the problems OneMax and LeadingOnes called OMM and LOTZ, respectively, and investigate hypervolume-based 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 hypervolume-based evolutionary multi-objective algorithms which is contrary to the results on their single-objective variants and the well-studied (1+1)-EA.}, author = {Nguyen, Anh Quang and Sutton, Andrew M. and Neumann, Frank}, journal = {Theoretical Computer Science}, pages = {24-36}, title = {Population size matters: Rigorous runtime results for maximizing the hypervolume indicator}, volume = 561, year = 2015 }
• 
  Alam, Md. Jawaherul; Bläsius, Thomas; Rutter, Ignaz; Ueckerdt, Torsten; Wolff, Alexander Pixel and Voxel Representations of Graphs. Graph Drawing (GD) 2015: 472-486
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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 minimum-size representations is NP-complete. Then, we bound representation sizes needed for certain graph classes. In 2D, we show that, for (k\)-outerplanar graphs with (n\) vertices, (Theta(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, (Theta(n^2)\) voxels are always sufficient and sometimes necessary for any (n\)-vertex graph. We improve this bound to (Theta(n⋅\tau)\) for graphs of treewidth (\tau\) 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.
  @inproceedings{DBLP:conf/gd/AlamBRUW15, abstract = {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 minimum-size representations is NP-complete. Then, we bound representation sizes needed for certain graph classes. In 2D, we show that, for (k\)-outerplanar graphs with (n\) vertices, (Theta(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, (Theta(n^2)\) voxels are always sufficient and sometimes necessary for any (n\)-vertex graph. We improve this bound to (Theta(n⋅\tau)\) for graphs of treewidth (\tau\) 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.}, author = {Alam, Md. Jawaherul and Bläsius, Thomas and Rutter, Ignaz and Ueckerdt, Torsten and Wolff, Alexander}, booktitle = {Graph Drawing (GD)}, pages = {472-486}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Pixel and Voxel Representations of Graphs}, volume = 9411, year = 2015 }
• 
  Friedrich, Tobias; Krohmer, Anton Parameterized clique on inhomogeneous random graphs. Discrete Applied Mathematics 2015: 130-138
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  Finding cliques in graphs is a classical problem which is in general NP-hard and parameterized intractable. In typical applications like social networks or biological networks, however, 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 (\beta\), cliques of size (k\) can be found in time (O(n)\) for (beta ge 3\) and in time (O(ne^{k^4}\) for (2 < beta < 3\).
  @article{DBLP:journals/dam/FriedrichK15, abstract = {Finding cliques in graphs is a classical problem which is in general NP-hard and parameterized intractable. In typical applications like social networks or biological networks, however, 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 (\beta\), cliques of size (k\) can be found in time (O(n)\) for (beta ge 3\) and in time (O(ne^{k^4}\) for (2 < beta < 3\).}, author = {Friedrich, Tobias and Krohmer, Anton}, journal = {Discrete Applied Mathematics}, pages = {130-138}, title = {Parameterized clique on inhomogeneous random graphs}, volume = 184, year = 2015 }
• 
  Chauhan, Ankit; Rao, B. V. Raghavendra Parameterized Analogues of Probabilistic Computation. Conference on Algorithms and Discrete Applied Mathematics (CALDAM) 2015: 181-192
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  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 Schwartz-Zippel lemma [Schwartz, JACM 80 and Zippel, EUROSAM 79]. Additionally, we introduce a parameterized variant of permanent, and prove its #W[1] completeness.
  @inproceedings{DBLP:conf/caldam/ChauhanR15, abstract = {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 Schwartz-Zippel lemma [Schwartz, JACM 80 and Zippel, EUROSAM 79]. Additionally, we introduce a parameterized variant of permanent, and prove its #W[1] completeness.}, author = {Chauhan, Ankit and Rao, B. V. Raghavendra}, booktitle = {Conference on Algorithms and Discrete Applied Mathematics (CALDAM)}, crossref = {DBLP:conf/caldam/2015}, pages = {181-192}, title = {Parameterized Analogues of Probabilistic Computation}, year = 2015 }
• 
  Bläsius, Thomas; Lehmann, Sebastian; Rutter, Ignaz Orthogonal Graph Drawing with Inflexible Edges. Conference on Algorithms and Complexity (CIAC) 2015: 61-73
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  We consider the problem of creating plane orthogonal drawings of 4-planar 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 NP-hard if (flex(e)=0\) for every edge (e\) [7]. On the other hand, FlexDraw can be solved efficiently if (flex(e) \ge1\) [2] and is trivial if (flex(e) ge 2\) [1] for every edge (e\). To close the gap between the NP-hardness for (flex(e)=0\) and the efficient algorithm for (flex(e) ge 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 (epsilon > 0\) FlexDraw is NP-complete for instances with (O(n^\epsilon)\) inflexible edges with pairwise distance (Omega(n^{1−\epsilon})\) (including the case where they induce a matching). On the other hand, we give an FPT-algorithm 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.
  @inproceedings{DBLP:conf/ciac/BlasiusLR15, abstract = {We consider the problem of creating plane orthogonal drawings of 4-planar 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 NP-hard if (flex(e)=0\) for every edge (e\) [7]. On the other hand, FlexDraw can be solved efficiently if (flex(e) \ge1\) [2] and is trivial if (flex(e) ge 2\) [1] for every edge (e\). To close the gap between the NP-hardness for (flex(e)=0\) and the efficient algorithm for (flex(e) ge 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 (epsilon > 0\) FlexDraw is NP-complete for instances with (O(n^\epsilon)\) inflexible edges with pairwise distance (Omega(n^{1−\epsilon})\) (including the case where they induce a matching). On the other hand, we give an FPT-algorithm 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.}, author = {Bläsius, Thomas and Lehmann, Sebastian and Rutter, Ignaz}, booktitle = {Conference on Algorithms and Complexity (CIAC)}, pages = {61-73}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Orthogonal Graph Drawing with Inflexible Edges}, volume = 9079, year = 2015 }
• 
  Friedrich, Tobias; Hercher, Christian On the kernel size of clique cover reductions for random intersection graphs. Journal of Discrete Algorithms 2015: 128-136
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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 worst-case. 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 well-known 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 worst-case bounds.
  @article{DBLP:journals/jda/FriedrichH15, abstract = {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 worst-case. 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 well-known 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 worst-case bounds.}, author = {Friedrich, Tobias and Hercher, Christian}, journal = {Journal of Discrete Algorithms}, pages = {128-136}, title = {On the kernel size of clique cover reductions for random intersection graphs}, volume = 34, year = 2015 }
• 
  Friedrich, Tobias; Krohmer, Anton On the Diameter of Hyperbolic Random Graphs. International Colloquium on Automata, Languages and Programming (ICALP) 2015: 614-625
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  Large real-world networks are typically scale-free. 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 scale-free networks. Hyperbolic random graphs follow a power-law degree distribution with controllable exponent β and show high clustering (Gugelmann, Panagiotou, and Peter. ICALP, pp. 573-585, 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((log n)^32/((3−\beta)(5−\beta)}))\) (Kiwi and Mitsche. ANALCO, pp. 26-39, 2015). We present two much simpler proofs for an improved upper bound of (O((log n)^2/(3−\beta)})\) and a lower bound of (Omega(log n)\).
  @inproceedings{DBLP:conf/icalp/FriedrichK15, abstract = {Large real-world networks are typically scale-free. 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 scale-free networks. Hyperbolic random graphs follow a power-law degree distribution with controllable exponent β and show high clustering (Gugelmann, Panagiotou, and Peter. ICALP, pp. 573-585, 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((log n)^32/((3−\beta)(5−\beta)}))\) (Kiwi and Mitsche. ANALCO, pp. 26-39, 2015). We present two much simpler proofs for an improved upper bound of (O((log n)^2/(3−\beta)})\) and a lower bound of (Omega(log n)\).}, author = {Friedrich, Tobias and Krohmer, Anton}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, pages = {614-625}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {On the Diameter of Hyperbolic Random Graphs}, volume = 9135, year = 2015 }
• 
  Fountoulakis, Nikolaos; Friedrich, Tobias; Hermelin, Danny On the average-case complexity of parameterized clique. Theoretical Computer Science 2015: 18-29
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  The (k\)-Clique 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 well-known NP-complete and W[1]-complete problems. Moreover, its average-case 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 average-case complexity of the (k\)-Clique problem on the parameter (k\). To this end, we define two natural parameterized analogs of efficient average-case algorithms. We then show that (k\)-Clique admits both analogues for Erdős–Rényi random graphs of arbitrary density. We also show that (k\)-Clique is unlikely to admit either of these analogs for some specific computable input distribution.
  @article{DBLP:journals/tcs/FountoulakisFH15, abstract = {The (k\)-Clique 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 well-known NP-complete and W[1]-complete problems. Moreover, its average-case 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 average-case complexity of the (k\)-Clique problem on the parameter (k\). To this end, we define two natural parameterized analogs of efficient average-case algorithms. We then show that (k\)-Clique admits both analogues for Erdős–Rényi random graphs of arbitrary density. We also show that (k\)-Clique is unlikely to admit either of these analogs for some specific computable input distribution.}, author = {Fountoulakis, Nikolaos and Friedrich, Tobias and Hermelin, Danny}, journal = {Theoretical Computer Science}, pages = {18-29}, title = {On the average-case complexity of parameterized clique}, volume = 576, year = 2015 }
• 
  Schirneck, Martin On Restrictions in Computational Language Learning. 2015
  Examenspreis des Dekans 2016 (Dean's prize for best thesis)
  [ Abstract ] [ BibTeX ] [ Download ]
   
  In 1990 Fulk proved that partially set-drivenness (rearrangement-independence) does not weaken the power of unrestricted computational language learning. The question arises whether this result still holds if paired with various learning restrictions. We investigate the influence of two main categories of such restrictions, namely content-based and delayable ones. An adaption of Fulk’s theorem is verified for content-based learning and some delayable restrictions regarding U-shaped learning. On the other hand, we give an example criterion of delayable learning — explanatory learning from text by a strongly monotone scientist — for which partially set-drivenness does reduce the learning power. Additionally, the interdependence of these restrictions with several other interaction operators and success criteria are explored.
  @mastersthesis{schirneck2015restrictions, abstract = {In 1990 Fulk proved that partially set-drivenness (rearrangement-independence) does not weaken the power of unrestricted computational language learning. The question arises whether this result still holds if paired with various learning restrictions. We investigate the influence of two main categories of such restrictions, namely content-based and delayable ones. An adaption of Fulk’s theorem is verified for content-based learning and some delayable restrictions regarding U-shaped learning. On the other hand, we give an example criterion of delayable learning — explanatory learning from text by a strongly monotone scientist — for which partially set-drivenness does reduce the learning power. Additionally, the interdependence of these restrictions with several other interaction operators and success criteria are explored.}, author = {Schirneck, Martin}, note = {Examenspreis des Dekans 2016 (Dean's prize for best thesis)}, school = {Friedrich Schiller University Jena}, title = {On Restrictions in Computational Language Learning}, year = 2015 }
• 
  Bläsius, Thomas New Approaches to Classic Graph-Embedding Problems - Orthogonal Drawings & Constrained Planarity. 2015
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  Drawings of graphs are often used to represent a given data set in a human-readable way. In this thesis, we consider different classic algorithmic problems that arise when automatically generating graph drawings. More specifically, we solve some open problems in the context of orthogonal drawings and advance the current state of research on the problems clustered planarity and simultaneous planarity.
  @phdthesis{DBLP:phd/dnb/Blasius15, abstract = {Drawings of graphs are often used to represent a given data set in a human-readable way. In this thesis, we consider different classic algorithmic problems that arise when automatically generating graph drawings. More specifically, we solve some open problems in the context of orthogonal drawings and advance the current state of research on the problems clustered planarity and simultaneous planarity.}, author = {Bläsius, Thomas}, school = {Karlsruhe Institute of Technology}, title = {New Approaches to Classic Graph-Embedding Problems - Orthogonal Drawings & Constrained Planarity}, year = 2015 }
• 
  Cord-Landwehr, Andreas; Lenzner, Pascal Network Creation Games: Think Global - Act Local. Mathematical Foundations of Computer Science (MFCS) 2015: 248-260
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  We investigate a non-cooperative game-theoretic 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 non-local 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 non-constant lower bound on the Price of Anarchy.
  @inproceedings{DBLP:conf/mfcs/Cord-LandwehrL15, abstract = {We investigate a non-cooperative game-theoretic 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 non-local 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 non-constant lower bound on the Price of Anarchy.}, author = {Cord-Landwehr, Andreas and Lenzner, Pascal}, booktitle = {Mathematical Foundations of Computer Science (MFCS)}, pages = {248-260}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Network Creation Games: Think Global - Act Local}, volume = 9235, year = 2015 }
• 
  Friedrich, Tobias; Neumann, Frank; Thyssen, Christian Multiplicative Approximations, Optimal Hypervolume Distributions, and the Choice of the Reference Point. Evolutionary Computation 2015: 131-159
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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 multi-objective problems as the population of such an algorithm can be used to represent the trade-offs with respect to the given objective functions. In this paper, we contribute to the theoretical understanding of evolutionary algorithms for multi-objective problems. We consider indicator-based 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 hypervolume-based 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 bi-objective 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 hypervolume-based approaches and examine Pareto fronts of different shapes by numerical calculations.
  @article{DBLP:journals/ec/FriedrichNT15, abstract = {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 multi-objective problems as the population of such an algorithm can be used to represent the trade-offs with respect to the given objective functions. In this paper, we contribute to the theoretical understanding of evolutionary algorithms for multi-objective problems. We consider indicator-based 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 hypervolume-based 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 bi-objective 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 hypervolume-based approaches and examine Pareto fronts of different shapes by numerical calculations.}, author = {Friedrich, Tobias and Neumann, Frank and Thyssen, Christian}, journal = {Evolutionary Computation}, number = 1, pages = {131-159}, title = {Multiplicative Approximations, Optimal Hypervolume Distributions, and the Choice of the Reference Point}, volume = 23, year = 2015 }
• 
  Friedrich, Tobias; Neumann, Frank Maximizing Submodular Functions under Matroid Constraints by Evolutionary Algorithms. Evolutionary Computation 2015: 543-558
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  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 multi-objective 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 ((1-1/e)\)-approximation in expected polynomial time. For the case of monotone functions where the constraints are given by the intersection of (k ge 2\) matroids, we show that the (1+1) EA achieves a ((1 + k/\delta)\)-approximation in expected polynomial time for any constant (delta > 0\). Turning to non-monotone symmetric submodular functions with (k ge 1\) matroid intersection constraints, we show that the GSEMO achieves a (1/((k+2)(1+\epsilon)))\)-approximation in expected time (O(n^k+6 log(n)/\epsilon)\).
  @article{DBLP:journals/ec/FriedrichN15, abstract = {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 multi-objective 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 ((1-1/e)\)-approximation in expected polynomial time. For the case of monotone functions where the constraints are given by the intersection of (k ge 2\) matroids, we show that the (1+1) EA achieves a ((1 + k/\delta)\)-approximation in expected polynomial time for any constant (delta > 0\). Turning to non-monotone symmetric submodular functions with (k ge 1\) matroid intersection constraints, we show that the GSEMO achieves a (1/((k+2)(1+\epsilon)))\)-approximation in expected time (O(n^k+6 log(n)/\epsilon)\).}, author = {Friedrich, Tobias and Neumann, Frank}, journal = {Evolutionary Computation}, number = 4, pages = {543-558}, publisher = {MIT Press}, title = {Maximizing Submodular Functions under Matroid Constraints by Evolutionary Algorithms}, volume = 23, year = 2015 }
• 
  Doerr, Benjamin; Neumann, Frank; Sutton, Andrew M. Improved Runtime Bounds for the (1+1) EA on Random 3-CNF Formulas Based on Fitness-Distance Correlation. Genetic and Evolutionary Computation Conference (GECCO) 2015: 1415-1422
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  With this paper, we contribute to the theoretical understanding of randomized search heuristics by investigating their behavior on random 3-SAT instances. We improve the results for the (1+1) EA obtained by Sutton and Neumann [PPSN 2014, 942-951] 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 high-density satisfiable 3-CNF 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 fitness-distance 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 fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.
  @inproceedings{DBLP:conf/gecco/DoerrNS15, abstract = {With this paper, we contribute to the theoretical understanding of randomized search heuristics by investigating their behavior on random 3-SAT instances. We improve the results for the (1+1) EA obtained by Sutton and Neumann [PPSN 2014, 942-951] 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 high-density satisfiable 3-CNF 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 fitness-distance 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 fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.}, author = {Doerr, Benjamin and Neumann, Frank and Sutton, Andrew M.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, pages = {1415-1422}, publisher = {ACM}, title = {Improved Runtime Bounds for the (1+1) EA on Random 3-CNF Formulas Based on Fitness-Distance Correlation}, year = 2015 }
• 
  Friedrich, Tobias; He, Jun; Jansen, Thomas; Moraglio, Alberto Genetic and Evolutionary Computation. Theoretical Computer Science 2015: 1-2
  [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  @article{DBLP:journals/tcs/FriedrichHJM15, author = {Friedrich, Tobias and He, Jun and Jansen, Thomas and Moraglio, Alberto}, journal = {Theoretical Computer Science}, pages = {1-2}, title = {Genetic and Evolutionary Computation}, volume = 561, year = 2015 }
• 
  Chicano, Francisco; Sutton, Andrew M.; Whitley, L. Darrell; Alba, Enrique Fitness Probability Distribution of Bit-Flip Mutation. Evolutionary Computation 2015: 217-248
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  Bit-flip 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 bit-flip 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 closed-form expressions for an easy linear problem Onemax, and an NP-hard problem, MAX-SAT. We also discuss a connection of the results with runtime analysis.
  @article{DBLP:journals/ec/ChicanoSWA15, abstract = {Bit-flip 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 bit-flip 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 closed-form expressions for an easy linear problem Onemax, and an NP-hard problem, MAX-SAT. We also discuss a connection of the results with runtime analysis.}, author = {Chicano, Francisco and Sutton, Andrew M. and Whitley, L. Darrell and Alba, Enrique}, journal = {Evolutionary Computation}, number = 2, pages = {217-248}, title = {Fitness Probability Distribution of Bit-Flip Mutation}, volume = 23, year = 2015 }
• 
  Freydenberger, Dominik D.; Kötzing, Timo Fast Learning of Restricted Regular Expressions and DTDs. Theory of Computing Systems 2015: 1114-1158
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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 non-optimal 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.
  @article{DBLP:journals/mst/FreydenbergerK15, abstract = {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 non-optimal 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.}, author = {Freydenberger, Dominik D. and Kötzing, Timo}, journal = {Theory of Computing Systems}, number = 4, pages = {1114-1158}, title = {Fast Learning of Restricted Regular Expressions and DTDs}, volume = 57, year = 2015 }
• 
  Wagner, Markus; Bringmann, Karl; Friedrich, Tobias; Neumann, Frank Efficient optimization of many objectives by approximation-guided evolution. European Journal of Operational Research 2015: 465-479
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  Multi-objective optimization problems arise frequently in applications, but can often only be solved approximately by heuristic approaches. Evolutionary algorithms have been widely used to tackle multi-objective 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 multi-objective optimization that allows to work with a formal notion of approximation. This approximation-guided evolutionary algorithm (AGE) has a worst-case runtime linear in the number of objectives and works with an archive that is an approximation of the non-dominated 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 NSGA-II, SPEA2, and SMS-EMOA. In this paper we compare AGE with two additional algorithms that use very fast hypervolume-approximations to guide their search. This significantly speeds up the runtime of the hypervolume-based algorithms, which now allows a comparison of the underlying selection schemes.
  @article{DBLP:journals/eor/0007BFN15, abstract = {Multi-objective optimization problems arise frequently in applications, but can often only be solved approximately by heuristic approaches. Evolutionary algorithms have been widely used to tackle multi-objective 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 multi-objective optimization that allows to work with a formal notion of approximation. This approximation-guided evolutionary algorithm (AGE) has a worst-case runtime linear in the number of objectives and works with an archive that is an approximation of the non-dominated 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 NSGA-II, SPEA2, and SMS-EMOA. In this paper we compare AGE with two additional algorithms that use very fast hypervolume-approximations to guide their search. This significantly speeds up the runtime of the hypervolume-based algorithms, which now allows a comparison of the underlying selection schemes.}, author = {Wagner, Markus and Bringmann, Karl and Friedrich, Tobias and Neumann, Frank}, journal = {European Journal of Operational Research}, number = 2, pages = {465-479}, title = {Efficient optimization of many objectives by approximation-guided evolution}, volume = 243, year = 2015 }
• 
  Bringmann, Karl; Friedrich, Tobias; Klitzke, Patrick Efficient computation of two-dimensional solution sets maximizing the epsilon-indicator. Congress on Evolutionary Computation (CEC) 2015: 970-977
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  The majority of empirical comparisons of multi-objective evolutionary algorithms (MOEAs) are performed on synthetic benchmark functions. One of the advantages of synthetic test functions is the a-priori 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 (\epsilon\)-indicator values achievable with solution sets of size (k\), up to an error of (\delta\). We present a new algorithm with runtime (O(k · log^2(\delta-1))\), which is an exponential improvement regarding the dependence on the error (\delta\) compared to all previous work. We show mathematical correctness of our algorithm and determine optimal solution sets for sets of cardinality (k in 2, 3, 4, 5, 10, 20, 50, 100, 1000\}\) for the well known test suits DTLZ, ZDT, WFG and LZ09 up to error (delta = 10^{-25}\).
  @inproceedings{DBLP:conf/cec/BringmannFK15, abstract = {The majority of empirical comparisons of multi-objective evolutionary algorithms (MOEAs) are performed on synthetic benchmark functions. One of the advantages of synthetic test functions is the a-priori 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 (\epsilon\)-indicator values achievable with solution sets of size (k\), up to an error of (\delta\). We present a new algorithm with runtime (O(k · log^2(\delta-1))\), which is an exponential improvement regarding the dependence on the error (\delta\) compared to all previous work. We show mathematical correctness of our algorithm and determine optimal solution sets for sets of cardinality (k in 2, 3, 4, 5, 10, 20, 50, 100, 1000\}\) for the well known test suits DTLZ, ZDT, WFG and LZ09 up to error (delta = 10^{-25}\).}, author = {Bringmann, Karl and Friedrich, Tobias and Klitzke, Patrick}, booktitle = {Congress on Evolutionary Computation (CEC)}, pages = {970-977}, publisher = {IEEE}, title = {Efficient computation of two-dimensional solution sets maximizing the epsilon-indicator}, year = 2015 }
• 
  Rothenberger, Ralf; Grau, Sascha; Rossberg, Michael Dominating an s-t-Cut in a Network. Conference on Current Trends in Theory and Practice of Informatics (SOFSEM) 2015: 401-411
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  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  subset  V\) of minimum cardinality, such that (X\) and its neighborhood constitute an (s-t\) 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−\delta}n}\), with (delta = 1 / \log\log^cn\) and arbitrary (c<1/2\) (if P (\neq\) 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\sqrt{n}\)-approximation algorithm and study the problem on graphs with bounded node degree. With (\Delta\) being the maximum degree of nodes (V ∖\ {s,t\}\), we identify a ((\Delta + 1)\) approximation algorithm.
  @inproceedings{DBLP:conf/sofsem/RothenbergerGR15, abstract = {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  subset  V\) of minimum cardinality, such that (X\) and its neighborhood constitute an (s-t\) 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−\delta}n}\), with (delta = 1 / \log\log^cn\) and arbitrary (c<1/2\) (if P (\neq\) 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\sqrt{n}\)-approximation algorithm and study the problem on graphs with bounded node degree. With (\Delta\) being the maximum degree of nodes (V ∖\ {s,t\}\), we identify a ((\Delta + 1)\) approximation algorithm.}, author = {Rothenberger, Ralf and Grau, Sascha and Rossberg, Michael}, booktitle = {Conference on Current Trends in Theory and Practice of Informatics (SOFSEM)}, crossref = {DBLP:conf/sofsem/2015}, pages = {401-411}, title = {Dominating an s-t-Cut in a Network}, year = 2015 }
• 
  Bläsius, Thomas; Rutter, Ignaz Disconnectivity and relative positions in simultaneous embeddings. Computational Geometry 2015: 459-478
  [ Abstract ] [ BibTeX ] [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)\).
  @article{DBLP:journals/comgeo/BlasiusR15, 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}, journal = {Computational Geometry}, number = 6, pages = {459-478}, title = {Disconnectivity and relative positions in simultaneous embeddings}, volume = 48, year = 2015 }
• 
  Göbel, Andreas; Goldberg, Leslie Ann; McQuillan, Colin; Richerby, David; Yamakami, Tomoyuki Counting List Matrix Partitions of Graphs. SIAM Journal on Computing 2015: 1089-1118
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  Given a symmetric (Dtimes D\) matrix (M\) over 0,1,*, a list (M\)-partition 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 graph-theoretic structures can be represented as list (M\)-partitions including graph colorings, split graphs, and homogeneous sets and pairs, 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 (M\)-partitions are tractable. This paper focuses on the problem of counting list (M\)-partitions, given a graph (G\) and given a list for each vertex of (G\). We identify a certain set of “tractable” matrices (M\). We give an algorithm that counts list (M\)-partitions in polynomial time for every (fixed) matrix (M\) in this set. The algorithm relies on data structures such as sparse-dense partitions and subcube 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 are controlled. We show how to solve the resulting restricted instances by converting them into particular counting constraint satisfaction problems (({\#CSP}\)s), which we show how to solve using a constraint satisfaction technique known as arc-consistency. For every matrix (M\) for which our algorithm fails, we show that the problem of counting list (M\)-partitions is ({\#P}\)-complete. Furthermore, we give an explicit characterization of the dichotomy theorem: counting list (M\)-partitions is tractable (in ({FP}\)) if the matrix (M\) has a structure called a derectangularizing sequence. If (M\) has no derectangularizing sequence, we show that counting list (M\)-partitions is ({\#P}\)-hard. We show that the metaproblem of determining whether a given matrix has a derectangularizing sequence is ({NP}\)-complete. Finally, we show that list (M\)-partitions can be used to encode cardinality restrictions in (M\)-partitions problems, and we use this to give a polynomial-time algorithm for counting homogeneous pairs in graphs.
  @article{DBLP:journals/siamcomp/0001GMRY15, abstract = {Given a symmetric (Dtimes D\) matrix (M\) over 0,1,*, a list (M\)-partition 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 graph-theoretic structures can be represented as list (M\)-partitions including graph colorings, split graphs, and homogeneous sets and pairs, 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 (M\)-partitions are tractable. This paper focuses on the problem of counting list (M\)-partitions, given a graph (G\) and given a list for each vertex of (G\). We identify a certain set of “tractable” matrices (M\). We give an algorithm that counts list (M\)-partitions in polynomial time for every (fixed) matrix (M\) in this set. The algorithm relies on data structures such as sparse-dense partitions and subcube 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 are controlled. We show how to solve the resulting restricted instances by converting them into particular counting constraint satisfaction problems (({\#CSP}\)s), which we show how to solve using a constraint satisfaction technique known as arc-consistency. For every matrix (M\) for which our algorithm fails, we show that the problem of counting list (M\)-partitions is ({\#P}\)-complete. Furthermore, we give an explicit characterization of the dichotomy theorem: counting list (M\)-partitions is tractable (in ({FP}\)) if the matrix (M\) has a structure called a derectangularizing sequence. If (M\) has no derectangularizing sequence, we show that counting list (M\)-partitions is ({\#P}\)-hard. We show that the metaproblem of determining whether a given matrix has a derectangularizing sequence is ({NP}\)-complete. Finally, we show that list (M\)-partitions can be used to encode cardinality restrictions in (M\)-partitions problems, and we use this to give a polynomial-time algorithm for counting homogeneous pairs in graphs.}, author = {Göbel, Andreas and Goldberg, Leslie Ann and McQuillan, Colin and Richerby, David and Yamakami, Tomoyuki}, journal = {SIAM Journal on Computing}, number = 4, pages = {1089-1118}, title = {Counting List Matrix Partitions of Graphs}, volume = 44, year = 2015 }
• 
  Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David Counting Homomorphisms to Square-Free Graphs, Modulo 2. International Colloquium on Automata, Languages, and Programming (ICALP) 2015: 642-653
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  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 4-cycles, ⊕HomsToH is either in polynomial time or is ⊕P-complete. This partially confirms a conjecture of Faben and Jerrum that was previously only known to hold for trees and for a restricted class of tree-width-2 graphs called cactus graphs. We confirm the conjecture for a rich class of graphs, including graphs of unbounded tree-width. In particular, we focus on square-free graphs, which are graphs without 4-cycles. 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 tree-like so that tree-like 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.
  @inproceedings{DBLP:conf/icalp/0001GR15, abstract = {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 4-cycles, ⊕HomsToH is either in polynomial time or is ⊕P-complete. This partially confirms a conjecture of Faben and Jerrum that was previously only known to hold for trees and for a restricted class of tree-width-2 graphs called cactus graphs. We confirm the conjecture for a rich class of graphs, including graphs of unbounded tree-width. In particular, we focus on square-free graphs, which are graphs without 4-cycles. 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 tree-like so that tree-like 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.}, author = {Göbel, Andreas and Goldberg, Leslie Ann and Richerby, David}, booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)}, crossref = {DBLP:conf/icalp/2015-1}, pages = {642-653}, title = {Counting Homomorphisms to Square-Free Graphs, Modulo 2}, year = 2015 }
• 
  Friedrich, Tobias; Krohmer, Anton Cliques in hyperbolic random graphs. International Conference on Computer Communications (INFOCOM) 2015: 1544-1552
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  Most complex real-world networks display scale-free features. This motivated the study of numerous random graph models with a power-law 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. 2973-2981, 2010) and has shown theoretically and empirically to fulfill all typical properties of real-world networks, including power-law degree distribution and high clustering. We study cliques in hyperbolic random graphs (G\) and present new results on the expected number of (k\)-cliques (E[K_k]\) and the size of the largest clique (omega(G)\). We observe that there is a phase transition at power-law exponent (γ = 3\). More precisely, for (γ in (2,3)\) we prove (E[K_k] = n^k(3-γ)/2 Theta(k)^{-k}\) and (omega(G) = Theta(n(3-γ)/2})\) while for (γ ge 3\) we prove (E[K_k] = n Theta(k)^{-k}\) and (omega(G) = Θ(log(n)/log log n)\). We empirically compare the (omega(G)\) value of several scale-free random graph models with real-world networks. Our experiments show that the (omega(G)\)-predictions by hyperbolic random graphs are much closer to the data than other scale-free random graph models.
  @inproceedings{DBLP:conf/infocom/FriedrichK15, abstract = {Most complex real-world networks display scale-free features. This motivated the study of numerous random graph models with a power-law 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. 2973-2981, 2010) and has shown theoretically and empirically to fulfill all typical properties of real-world networks, including power-law degree distribution and high clustering. We study cliques in hyperbolic random graphs (G\) and present new results on the expected number of (k\)-cliques (E[K_k]\) and the size of the largest clique (omega(G)\). We observe that there is a phase transition at power-law exponent (γ = 3\). More precisely, for (γ in (2,3)\) we prove (E[K_k] = n^k(3-γ)/2 Theta(k)^{-k}\) and (omega(G) = Theta(n(3-γ)/2})\) while for (γ ge 3\) we prove (E[K_k] = n Theta(k)^{-k}\) and (omega(G) = Θ(log(n)/log log n)\). We empirically compare the (omega(G)\) value of several scale-free random graph models with real-world networks. Our experiments show that the (omega(G)\)-predictions by hyperbolic random graphs are much closer to the data than other scale-free random graph models.}, author = {Friedrich, Tobias and Krohmer, Anton}, booktitle = {International Conference on Computer Communications (INFOCOM)}, pages = {1544-1552}, publisher = {IEEE}, title = {Cliques in hyperbolic random graphs}, year = 2015 }
• 
  Kötzing, Timo; Lissovoi, Andrei; Witt, Carsten (1+1) EA on Generalized Dynamic OneMax. Foundations of Genetic Algorithms (FOGA) 2015: 40-51
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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 re-prove 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.
  @inproceedings{DBLP:conf/foga/KotzingLW15, abstract = {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 re-prove 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.}, author = {Kötzing, Timo and Lissovoi, Andrei and Witt, Carsten}, booktitle = {Foundations of Genetic Algorithms (FOGA)}, pages = {40-51}, publisher = {ACM}, title = {(1+1) EA on Generalized Dynamic OneMax}, year = 2015 }

2014

• 
  Doerr, Benjamin; Doerr, Carola; Kötzing, Timo Unbiased black-box complexities of jump functions: how to cross large plateaus. Genetic and Evolutionary Computation Conference (GECCO) 2014: 769-776
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  We analyze the unbiased black-box 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 black-box 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, polynomial-time mutation-based (i.e., unary unbiased) black-box optimization algorithms exist. This is quite surprising given that for the extreme jump function almost the whole search space (all but a (Theta(n^{-1/2})\) fraction) is a plateau of constant fitness.To prove these results, we introduce new tools for the analysis of unbiased black-box 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.
  @inproceedings{DBLP:conf/gecco/DoerrDK14, abstract = {We analyze the unbiased black-box 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 black-box 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, polynomial-time mutation-based (i.e., unary unbiased) black-box optimization algorithms exist. This is quite surprising given that for the extreme jump function almost the whole search space (all but a (Theta(n^{-1/2})\) fraction) is a plateau of constant fitness.To prove these results, we introduce new tools for the analysis of unbiased black-box 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.}, author = {Doerr, Benjamin and Doerr, Carola and Kötzing, Timo}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, pages = {769-776}, publisher = {ACM}, title = {Unbiased black-box complexities of jump functions: how to cross large plateaus}, year = 2014 }
• 
  Bringmann, Karl; Friedrich, Tobias; Klitzke, Patrick Two-dimensional subset selection for hypervolume and epsilon-indicator. Genetic and Evolutionary Computation Conference (GECCO) 2014: 589-596
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  The goal of bi-objective optimization is to find a small set of good compromise solutions. A common problem for bi-objective evolutionary algorithms is the following subset selection problem (SSP): Given (n\) solutions (P subset 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 in R^2\). Similarly, the (\epsilon\)-indicator SSP aims at selecting (tilde k\) points (P^*\) that minimize the (\epsilon\)-indicator (I_epsilon(P^*,R)\) for some reference set (R subset 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 (\epsilon\)-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.
  @inproceedings{DBLP:conf/gecco/BringmannFK14, abstract = {The goal of bi-objective optimization is to find a small set of good compromise solutions. A common problem for bi-objective evolutionary algorithms is the following subset selection problem (SSP): Given (n\) solutions (P subset 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 in R^2\). Similarly, the (\epsilon\)-indicator SSP aims at selecting (tilde k\) points (P^*\) that minimize the (\epsilon\)-indicator (I_epsilon(P^*,R)\) for some reference set (R subset 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 (\epsilon\)-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.}, author = {Bringmann, Karl and Friedrich, Tobias and Klitzke, Patrick}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, pages = {589-596}, publisher = {ACM}, title = {Two-dimensional subset selection for hypervolume and epsilon-indicator}, year = 2014 }
• 
  Doerr, Benjamin; Doerr, Carola; Kötzing, Timo The unbiased black-box complexity of partition is polynomial. Artificial Intelligence 2014: 275-286
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  Unbiased black-box complexity was introduced as a refined complexity model for random-ized 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 black-box complexity remains artificially small. More precisely, for two different formulations of an NP -hard subclass of the well-known Partition problem, we give mutation-only unbiased black-box algorithms having complexity (O(n log ⁡n)\). This indicates that also the unary unbiased black-box complexity does not give a complete picture of the true difficulty of this problem for randomized search heuristics.
  @article{DBLP:journals/ai/DoerrDK14, abstract = {Unbiased black-box complexity was introduced as a refined complexity model for random-ized 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 black-box complexity remains artificially small. More precisely, for two different formulations of an NP -hard subclass of the well-known Partition problem, we give mutation-only unbiased black-box algorithms having complexity (O(n log ⁡n)\). This indicates that also the unary unbiased black-box complexity does not give a complete picture of the true difficulty of this problem for randomized search heuristics.}, author = {Doerr, Benjamin and Doerr, Carola and Kötzing, Timo}, journal = {Artificial Intelligence}, pages = {275-286}, title = {The unbiased black-box complexity of partition is polynomial}, volume = 216, year = 2014 }
• 
  Kötzing, Timo; Sutton, Andrew M.; Neumann, Frank; O'Reilly, Una-May The Max problem revisited: The importance of mutation in genetic programming. Theoretical Computer Science 2014: 94-107
  [ 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.
  @article{DBLP:journals/tcs/KotzingSNO14, 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}, journal = {Theoretical Computer Science}, pages = {94-107}, title = {The Max problem revisited: The importance of mutation in genetic programming}, volume = 545, year = 2014 }
• 
  Whitley, Darrell; Sutton, Andrew M.; Ochoa, Gabriela; Chicano, Francisco The component model for elementary landscapes and partial neighborhoods. Theoretical Computer Science 2014: 59-75
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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 2-opt neighborhood can be decomposed into (lfloor n/2 − 1\rfloor\) 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.
  @article{DBLP:journals/tcs/WhitleySOC14, abstract = {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 2-opt neighborhood can be decomposed into (lfloor n/2 − 1\rfloor\) 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.}, author = {Whitley, Darrell and Sutton, Andrew M. and Ochoa, Gabriela and Chicano, Francisco}, journal = {Theoretical Computer Science}, pages = {59-75}, title = {The component model for elementary landscapes and partial neighborhoods}, volume = 545, year = 2014 }
• 
  Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David The complexity of counting homomorphisms to cactus graphs modulo 2. Transactions on Computation Theory 2014: 17:1-17:29
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  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 graph-theoretic. 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 (oplus 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.
  @article{DBLP:journals/toct/0001GR14, abstract = {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 graph-theoretic. 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 (oplus 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.}, author = {Göbel, Andreas and Goldberg, Leslie Ann and Richerby, David}, journal = {Transactions on Computation Theory}, number = 4, pages = {17:1-17:29}, title = {The complexity of counting homomorphisms to cactus graphs modulo 2}, volume = 6, year = 2014 }
• 
  Angelini, Patrizio; Bläsius, Thomas; Rutter, Ignaz Testing Mutual duality of Planar graphs. Computational Geometry and Applications 2014: 325-346
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  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 NP-completeness for general graphs and give a linear-time 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, SPQR-tree-like 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 self-dual. Our algorithm can handle the case of biconnected graphs in linear time and our NP-hardness proof extends to self-duality and also to map self-duality testing (which additionally requires to preserve the embedding).
  @article{DBLP:journals/ijcga/AngeliniBR14, abstract = {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 NP-completeness for general graphs and give a linear-time 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, SPQR-tree-like 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 self-dual. Our algorithm can handle the case of biconnected graphs in linear time and our NP-hardness proof extends to self-duality and also to map self-duality testing (which additionally requires to preserve the embedding).}, author = {Angelini, Patrizio and Bläsius, Thomas and Rutter, Ignaz}, journal = {Computational Geometry and Applications}, number = 4, pages = {325-346}, title = {Testing Mutual duality of Planar graphs}, volume = 24, year = 2014 }
• 
  Sutton, Andrew M.; Neumann, Frank Runtime Analysis of Evolutionary Algorithms on Randomly Constructed High-Density Satisfiable 3-CNF Formulas. Parallel Problem Solving from Nature (PPSN) 2014: 942-951
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  We show that simple mutation-only evolutionary algorithms find a satisfying assignment on two similar models of random planted 3-CNF 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 so-called filtered distribution) and conclude that most high-density 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 well-studied distributions of random satisfiability problems.
  @inproceedings{DBLP:conf/ppsn/SuttonN14, abstract = {We show that simple mutation-only evolutionary algorithms find a satisfying assignment on two similar models of random planted 3-CNF 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 so-called filtered distribution) and conclude that most high-density 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 well-studied distributions of random satisfiability problems.}, author = {Sutton, Andrew M. and Neumann, Frank}, booktitle = {Parallel Problem Solving from Nature (PPSN)}, pages = {942-951}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Runtime Analysis of Evolutionary Algorithms on Randomly Constructed High-Density Satisfiable 3-CNF Formulas}, volume = 8672, year = 2014 }
• 
  Gießen, Christian; Kötzing, Timo Robustness of populations in stochastic environments. Genetic and Evolutionary Computation Conference (GECCO) 2014: 1383-1390
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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 (Theta(log n)\)) 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.
  @inproceedings{DBLP:conf/gecco/GiessenK14, abstract = {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 (Theta(log n)\)) 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.}, author = {Gießen, Christian and Kötzing, Timo}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, pages = {1383-1390}, publisher = {ACM}, title = {Robustness of populations in stochastic environments}, year = 2014 }
• 
  Doerr, Benjamin; Friedrich, Tobias; Sauerwald, Thomas Quasirandom Rumor Spreading. Transactions on Algorithms 2014: 9:1-9:35
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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ős-Ré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 above-mentioned bounds still hold. In some cases, even better bounds than for the classical model can be shown.
  @article{DBLP:journals/talg/DoerrFS14, abstract = {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ős-Ré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 above-mentioned bounds still hold. In some cases, even better bounds than for the classical model can be shown.}, author = {Doerr, Benjamin and Friedrich, Tobias and Sauerwald, Thomas}, journal = {Transactions on Algorithms}, number = 2, pages = {9:1-9:35}, title = {Quasirandom Rumor Spreading}, volume = 11, year = 2014 }
• 
  Sutton, Andrew M.; Neumann, Frank; Nallaperuma, Samadhi Parameterized Runtime Analyses of Evolutionary Algorithms for the Planar Euclidean Traveling Salesperson Problem. Evolutionary Computation 2014: 595-628
  [ Abstract ] [ BibTeX ] [DOI] [ 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 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 ((mu + \lambda)\) EA in a strictly black box setting and show that it can solve the Euclidean TSP in expected time (O(n cdot A(\epsilon) cdot max(mu / \lambda) cdot n^2 , 1 + (mu / \lambda) cdot n^4k(2k − 1)!)\) where (A\) is a function of the minimum angle (\epsilon\) 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 2-opt moves and permutation jumps. This strategy improves the upper bound to (O(n cdot A(\epsilon) cdot max(mu / \lambda) cdot n^2 , 1 + (mu / \lambda) cdot 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 fixed-parameter tractable (FPT) evolutionary algorithms for the planar Euclidean TSP. We first develop a (mu + \lambda) EA based on an analysis by M. Theile, 2009, ”Exact solutions to the traveling salesperson problem by a population-based evolutionary algorithm,” Lecture notes in computer science, Vol. 5482 (pp. 145–155), that solves the TSP with (k\) inner points in (O(max\{2^kk^2n^2\lambda^{-1},n\})\) generations with probability (1 - e^-Omega(n)}\). We then design a ((mu + \lambda)\) EA that incorporates a dynamic programming step into the fitness evaluation. We prove that a variant of this evolutionary algorithm using 2-opt mutation solves the problem after (O(max(k − 2)!k^2k-2lambda^-1, 1\})\) steps in expectation with a cost of (O(nk)\) for each fitness evaluation.
  @article{DBLP:journals/ec/SuttonNN14, 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 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 ((mu + \lambda)\) EA in a strictly black box setting and show that it can solve the Euclidean TSP in expected time (O(n cdot A(\epsilon) cdot max(mu / \lambda) cdot n^2 , 1 + (mu / \lambda) cdot n^4k(2k − 1)!)\) where (A\) is a function of the minimum angle (\epsilon\) 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 2-opt moves and permutation jumps. This strategy improves the upper bound to (O(n cdot A(\epsilon) cdot max(mu / \lambda) cdot n^2 , 1 + (mu / \lambda) cdot 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 fixed-parameter tractable (FPT) evolutionary algorithms for the planar Euclidean TSP. We first develop a (mu + \lambda) EA based on an analysis by M. Theile, 2009, ”Exact solutions to the traveling salesperson problem by a population-based evolutionary algorithm,” Lecture notes in computer science, Vol. 5482 (pp. 145–155), that solves the TSP with (k\) inner points in (O(max\{2^kk^2n^2\lambda^{-1},n\})\) generations with probability (1 - e^-Omega(n)}\). We then design a ((mu + \lambda)\) EA that incorporates a dynamic programming step into the fitness evaluation. We prove that a variant of this evolutionary algorithm using 2-opt mutation solves the problem after (O(max(k − 2)!k^2k-2lambda^-1, 1\})\) steps in expectation with a cost of (O(nk)\) for each fitness evaluation.}, author = {Sutton, Andrew M. and Neumann, Frank and Nallaperuma, Samadhi}, journal = {Evolutionary Computation}, number = 4, pages = {595-628}, title = {Parameterized Runtime Analyses of Evolutionary Algorithms for the Planar Euclidean Traveling Salesperson Problem}, volume = 22, year = 2014 }
• 
  Bläsius, Thomas; Krug, Marcus; Rutter, Ignaz; Wagner, Dorothea Orthogonal Graph Drawing with Flexibility Constraints. Algorithmica 2014: 859-885
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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 colon E rightarrow N_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 (\beta\)-embeddability asking whether (G\) can be embedded with at most (\beta\) bends per edge. We give an algorithm with running-time (O(n^2)\) solving FlexDraw when the flexibility of each edge is positive. This includes 1-embeddability as a special case and thus closes the complexity gap between 0-embeddability, which is NP-hard to decide, and 2-embeddability, which is efficiently solvable since every planar graph with maximum degree 4 admits a 2-embedding except for the octahedron. In addition to the polynomial-time algorithm we show that FlexDraw is NP-hard even if the edges with flexibility 0 induce a tree or a union of disjoint stars.
  @article{DBLP:journals/algorithmica/BlasiusKRW14, abstract = {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 colon E rightarrow N_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 (\beta\)-embeddability asking whether (G\) can be embedded with at most (\beta\) bends per edge. We give an algorithm with running-time (O(n^2)\) solving FlexDraw when the flexibility of each edge is positive. This includes 1-embeddability as a special case and thus closes the complexity gap between 0-embeddability, which is NP-hard to decide, and 2-embeddability, which is efficiently solvable since every planar graph with maximum degree 4 admits a 2-embedding except for the octahedron. In addition to the polynomial-time algorithm we show that FlexDraw is NP-hard even if the edges with flexibility 0 induce a tree or a union of disjoint stars.}, author = {Bläsius, Thomas and Krug, Marcus and Rutter, Ignaz and Wagner, Dorothea}, journal = {Algorithmica}, number = 4, pages = {859-885}, title = {Orthogonal Graph Drawing with Flexibility Constraints}, volume = 68, year = 2014 }
• 
  Jain, Sanjay; Kötzing, Timo; Ma, Junqi; Stephan, Frank On the Role of Update Constraints and Text-Types in Iterative Learning. Algorithmic Learning Theory (ALT) 2014: 55--69
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  The present work investigates the relationship of iterative learning with other learning criteria such as decisiveness, caution, reliability, non-U-shapedness, monotonicity, strong monotonicity and conservativeness. Building on the result of Case and Moelius that iterative learners can be made non-U-shaped, we show that they also can be made cautious and decisive. Furthermore, we obtain various special results with respect to one-one texts, fat texts and one-one hypothesis spaces.
  @inproceedings{DBLP:conf/alt/JainKMS14, abstract = {The present work investigates the relationship of iterative learning with other learning criteria such as decisiveness, caution, reliability, non-U-shapedness, monotonicity, strong monotonicity and conservativeness. Building on the result of Case and Moelius that iterative learners can be made non-U-shaped, we show that they also can be made cautious and decisive. Furthermore, we obtain various special results with respect to one-one texts, fat texts and one-one hypothesis spaces.}, author = {Jain, Sanjay and Kötzing, Timo and Ma, Junqi and Stephan, Frank}, booktitle = {Algorithmic Learning Theory (ALT)}, pages = {55--69}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {On the Role of Update Constraints and Text-Types in Iterative Learning}, volume = 8776, year = 2014 }
• 
  Friedrich, Tobias; Neumann, Frank Maximizing Submodular Functions under Matroid Constraints by Multi-objective Evolutionary Algorithms. Parallel Problem Solving from Nature (PPSN) 2014: 922-931
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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 multi-objective 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(log n+k))\), where (k\) is the value of the given constraint. For the case of non-monotone submodular functions with (k\) matroid intersection constraints, we show that GSEMO achieves a (1/(k + 2 + 1/k +\epsilon)\)-approximation in expected time (O(n^k+5log(n)/\epsilon)\).
  @inproceedings{DBLP:conf/ppsn/FriedrichN14, abstract = {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 multi-objective 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(log n+k))\), where (k\) is the value of the given constraint. For the case of non-monotone submodular functions with (k\) matroid intersection constraints, we show that GSEMO achieves a (1/(k + 2 + 1/k +\epsilon)\)-approximation in expected time (O(n^k+5log(n)/\epsilon)\).}, author = {Friedrich, Tobias and Neumann, Frank}, booktitle = {Parallel Problem Solving from Nature (PPSN)}, pages = {922-931}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Maximizing Submodular Functions under Matroid Constraints by Multi-objective Evolutionary Algorithms}, volume = 8672, year = 2014 }
• 
  Kötzing, Timo Iterative learning from positive data and counters. Theoretical Computer Science 2014: 155-169
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  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 non-decreasing 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.
  @article{DBLP:journals/tcs/Kotzing14, abstract = {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 non-decreasing 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.}, author = {Kötzing, Timo}, journal = {Theoretical Computer Science}, pages = {155-169}, title = {Iterative learning from positive data and counters}, volume = 519, year = 2014 }
• 
  Friedrich, Tobias; Rowe, Jonathan E. Genetic and Evolutionary Computation. Theoretical Computer Science 2014: 1
  [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  @article{DBLP:journals/tcs/FriedrichR14, author = {Friedrich, Tobias and Rowe, Jonathan E.}, journal = {Theoretical Computer Science}, pages = 1, title = {Genetic and Evolutionary Computation}, volume = 545, year = 2014 }
• 
  Bringmann, Karl; Friedrich, Tobias; Klitzke, Patrick Generic Postprocessing via Subset Selection for Hypervolume and Epsilon-Indicator. Parallel Problem Solving from Nature (PPSN) 2014: 518-527
  [ Abstract ] [ BibTeX ] [DOI]