2014

Kötzing, Timo; Palenta, Raphaela A Map of Update Constraints in Inductive InferenceAlgorithmic Learning Theory (ALT) 2014: 40–54
[ Abstract ] [ BibTeX ] [ 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.
@inproceedings{DBLP:conf/alt/KotzingP14, 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}, booktitle = {Algorithmic Learning Theory (ALT)}, keywords = {imported timokoetzing year2014}, pages = {40-54}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {A Map of Update Constraints in Inductive Inference}, volume = 8776, year = 2014 }

Jain, Sanjay; Kötzing, Timo; Ma, Junqi; Stephan, Frank On the Role of Update Constraints and Text-Types in Iterative LearningAlgorithmic 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)}, keywords = {imported timokoetzing year2014}, 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 }

Göbel, Andreas; Goldberg, Leslie Ann; McQuillan, Colin; Richerby, David; Yamakami, Tomoyuki Counting List Matrix Partitions of GraphsConference on Computational Complexity (CCC) 2014: 56–65
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Given a symmetric \(D \times 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 non-edge of \(G\) is mapped to a 1 in \(M\). Many important graph-theoretic structures can be represented as list \(M\)-partitions including graph colourings, split graphs and homogeneous sets, which arise in the proofs of the weak and strong perfect graph conjectures. Thus, there has been quite a bit of work on determining for which matrices \(M\) computations involving list \(M\)-partitions are tractable. This paper focuses on the problem of counting list \(M\)-partitions, given a graph \(G\) and given lists for each vertex of \(G\). We give an algorithm that solves this problem in polynomial time for every (fixed) matrix \(M\) for which the problem is tractable. The algorithm relies on data structures such as sparse-dense partitions and sub cube decompositions to reduce each problem instance to a sequence of problem instances in which the lists have a certain useful structure that restricts access to portions of \(M\) in which the interactions of 0s and 1s is controlled. We show how to solve the resulting restricted instances by converting them into particular counting constraint satisfaction problems (\#CSPs) which we show how to solve using a constraint satisfaction technique known as "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 characterisation of the dichotomy theorem - counting list \(M\)-partitions is tractable (in FP) if and only if the matrix \(M\) has a structure called a derectangularising sequence. Finally, we show that the meta-problem of determining whether a given matrix has a derectangularising sequence is NP-complete.
@inproceedings{DBLP:conf/coco/0001GMRY14, abstract = {Given a symmetric \(D \times 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 non-edge of \(G\) is mapped to a 1 in \(M\). Many important graph-theoretic structures can be represented as list \(M\)-partitions including graph colourings, split graphs and homogeneous sets, which arise in the proofs of the weak and strong perfect graph conjectures. Thus, there has been quite a bit of work on determining for which matrices \(M\) computations involving list \(M\)-partitions are tractable. This paper focuses on the problem of counting list \(M\)-partitions, given a graph \(G\) and given lists for each vertex of \(G\). We give an algorithm that solves this problem in polynomial time for every (fixed) matrix \(M\) for which the problem is tractable. The algorithm relies on data structures such as sparse-dense partitions and sub cube decompositions to reduce each problem instance to a sequence of problem instances in which the lists have a certain useful structure that restricts access to portions of \(M\) in which the interactions of 0s and 1s is controlled. We show how to solve the resulting restricted instances by converting them into particular counting constraint satisfaction problems (\#CSPs) which we show how to solve using a constraint satisfaction technique known as "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 characterisation of the dichotomy theorem - counting list \(M\)-partitions is tractable (in FP) if and only if the matrix \(M\) has a structure called a derectangularising sequence. Finally, we show that the meta-problem of determining whether a given matrix has a derectangularising sequence is NP-complete.}, author = {Göbel, Andreas and Goldberg, Leslie Ann and McQuillan, Colin and Richerby, David and Yamakami, Tomoyuki}, booktitle = {Conference on Computational Complexity (CCC)}, keywords = {andreasgoebel ccc year2014}, pages = {56-65}, title = {Counting List Matrix Partitions of Graphs}, year = 2014 }

Bläsius, Thomas; Brückner, Guido; Rutter, Ignaz Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky ModelEuropean Symposium on Algorithms (ESA) 2014: 161–172
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We show that finding orthogonal grid-embeddings of plane graphs (planar with fixed combinatorial embedding) with the minimum number of bends in the so-called Kandinsky model (which allows vertices of degree >4) is NP-complete, thus solving a long-standing open problem. On the positive side, we give an efficient algorithm for several restricted variants, such as graphs of bounded branch width and a subexponential exact algorithm for general plane graphs.
@inproceedings{DBLP:conf/esa/BlasiusBR14, abstract = {We show that finding orthogonal grid-embeddings of plane graphs (planar with fixed combinatorial embedding) with the minimum number of bends in the so-called Kandinsky model (which allows vertices of degree >4) is NP-complete, thus solving a long-standing open problem. On the positive side, we give an efficient algorithm for several restricted variants, such as graphs of bounded branch width and a subexponential exact algorithm for general plane graphs.}, author = {Bläsius, Thomas and Brückner, Guido and Rutter, Ignaz}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {imported thomas thomasblaesius year2014}, pages = {161-172}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model}, volume = 8737, year = 2014 }

Bringmann, Karl; Friedrich, Tobias; Krohmer, Anton De-anonymization of Heterogeneous Random Graphs in Quasilinear TimeEuropean Symposium on Algorithms (ESA) 2014: 197–208
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
There are hundreds of online social networks with billions of users in total. Many such networks publicly release structural information, with all personal information removed. Empirical studies have shown, however, that this provides a false sense of privacy - it is possible to identify almost all users that appear in two such anonymized network as long as a few initial mappings are known. We analyze this problem theoretically by reconciling two versions of an artificial power-law network arising from independent subsampling of vertices and edges. We present a new algorithm that identifies most vertices and makes no wrong identifications with high probability. The number of vertices matched is shown to be asymptotically optimal. For an \(n\)-vertex graph, our algorithm uses \(n^\epsilon\) seed nodes (for an arbitrarily small \(\epsilon\)) and runs in quasilinear time. This improves previous theoretical results which need \(\Theta(n)\) seed nodes and have runtimes of order \(n^{1 + \Omega(1)}\). Additionally, the applicability of our algorithm is studied experimentally on different networks.
@inproceedings{DBLP:conf/esa/BringmannFK14, abstract = {There are hundreds of online social networks with billions of users in total. Many such networks publicly release structural information, with all personal information removed. Empirical studies have shown, however, that this provides a false sense of privacy - it is possible to identify almost all users that appear in two such anonymized network as long as a few initial mappings are known. We analyze this problem theoretically by reconciling two versions of an artificial power-law network arising from independent subsampling of vertices and edges. We present a new algorithm that identifies most vertices and makes no wrong identifications with high probability. The number of vertices matched is shown to be asymptotically optimal. For an \(n\)-vertex graph, our algorithm uses \(n^\epsilon\) seed nodes (for an arbitrarily small \(\epsilon\)) and runs in quasilinear time. This improves previous theoretical results which need \(\Theta(n)\) seed nodes and have runtimes of order \(n^{1 + \Omega(1)}\). Additionally, the applicability of our algorithm is studied experimentally on different networks.}, author = {Bringmann, Karl and Friedrich, Tobias and Krohmer, Anton}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {antonkrohmer esa imported tobiasfriedrich year2014}, pages = {197-208}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {De-anonymization of Heterogeneous Random Graphs in Quasilinear Time}, volume = 8737, year = 2014 }

Casel, Katrin A Fixed-Parameter Approach for Privacy-Protection with Global RecodingFrontiers in Algorithmics (FAW) 2014: 25–35
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
This paper discusses a problem arising in the field of privacy-protection in statistical databases: Given a \(n \times m\) \(\{0,1\}\)-matrix \(M\), is there a set of mergings which transforms \(M\) into a zero matrix and only affects a bounded number of rows/columns. “Merging” here refers to combining adjacent lines with a component-wise logical AND. This kind transformation models a generalization on OLAP-cubes also called global recoding. Counting the number of affected lines presents a new measure of information-loss for this method. Parameterized by the number of affected lines \(k\) we introduce reduction rules and an \(O^*(2.618^k)\)-algorithm for the new abstract combinatorial problem LMAL.
@inproceedings{DBLP:conf/faw/Casel14, abstract = {This paper discusses a problem arising in the field of privacy-protection in statistical databases: Given a \(n \times m\) \(\{0,1\}\)-matrix \(M\), is there a set of mergings which transforms \(M\) into a zero matrix and only affects a bounded number of rows/columns. “Merging” here refers to combining adjacent lines with a component-wise logical AND. This kind transformation models a generalization on OLAP-cubes also called global recoding. Counting the number of affected lines presents a new measure of information-loss for this method. Parameterized by the number of affected lines \(k\) we introduce reduction rules and an \(O^*(2.618^k)\)-algorithm for the new abstract combinatorial problem LMAL.}, author = {Casel, Katrin}, booktitle = {Frontiers in Algorithmics (FAW)}, editor = {Chen, Jianer and Hopcroft, John E. and Wang, Jianxin}, keywords = {faw katrincasel year2014}, pages = {25-35}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {A Fixed-Parameter Approach for Privacy-Protection with Global Recoding}, volume = 8497, year = 2014 }

Bläsius, Thomas; Rutter, Ignaz A New Perspective on Clustered Planarity as a Combinatorial Embedding ProblemGraph Drawing (GD) 2014: 440–451
[ Abstract ] [ BibTeX ] [ 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 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.
@inproceedings{DBLP:conf/gd/BlasiusR14, 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 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}, booktitle = {Graph Drawing (GD)}, keywords = {GD imported thomas thomasblaesius year2014}, pages = {440-451}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem}, volume = 8871, year = 2014 }

Chicano, Francisco; Whitley, Darrell; Sutton, Andrew M. Efficient identification of improving moves in a ball for pseudo-boolean problemsGenetic and Evolutionary Computation Conference (GECCO) 2014: 437–444
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Hill climbing algorithms are at the core of many approaches to solve optimization problems. Such algorithms usually require the complete enumeration of a neighborhood of the current solution. In the case of problems defined over binary strings of length \(n\), we define the \(r\)-ball neighborhood as the set of solutions at Hamming distance \(r\) or less from the current solution. For \(r \ll n\) this neighborhood contains \(\Theta(n^r)\) solutions. In this paper efficient methods areintroduced to locate improving moves in the \(r\)-ball neighborhood for problems that can be written as a sum of a linear number of subfunctions depending on a bounded number of variables. NK-landscapes and MAX-\(k\)-SAT are examples of these problems. If the number of subfunctions depending on any given variable is also bounded, then we prove that the method can explore the neighborhood in constant time, despite the fact that the number of solutions in the neighborhood is polynomial in \(n\). We develop a hill climber based on our exploration method and we analyze its efficiency and efficacy using experiments with NKq-landscapes instances.
@inproceedings{DBLP:conf/gecco/ChicanoWS14, abstract = {Hill climbing algorithms are at the core of many approaches to solve optimization problems. Such algorithms usually require the complete enumeration of a neighborhood of the current solution. In the case of problems defined over binary strings of length \(n\), we define the \(r\)-ball neighborhood as the set of solutions at Hamming distance \(r\) or less from the current solution. For \(r \ll n\) this neighborhood contains \(\Theta(n^r)\) solutions. In this paper efficient methods areintroduced to locate improving moves in the \(r\)-ball neighborhood for problems that can be written as a sum of a linear number of subfunctions depending on a bounded number of variables. NK-landscapes and MAX-\(k\)-SAT are examples of these problems. If the number of subfunctions depending on any given variable is also bounded, then we prove that the method can explore the neighborhood in constant time, despite the fact that the number of solutions in the neighborhood is polynomial in \(n\). We develop a hill climber based on our exploration method and we analyze its efficiency and efficacy using experiments with NKq-landscapes instances.}, author = {Chicano, Francisco and Whitley, Darrell and Sutton, Andrew M.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {andrewmsutton gecco imported year2014}, pages = {437-444}, title = {Efficient identification of improving moves in a ball for pseudo-boolean problems}, year = 2014 }

Bringmann, Karl; Friedrich, Tobias; Klitzke, Patrick Two-dimensional subset selection for hypervolume and epsilon-indicatorGenetic 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 \mathbb{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^*,\mathbb{R})\) for some reference set \(R \subset R^2\) of size \(m\) (which can be \(\mathbb{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 \mathbb{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^*,\mathbb{R})\) for some reference set \(R \subset R^2\) of size \(m\) (which can be \(\mathbb{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)}, keywords = {gecco imported tobiasfriedrich year2014}, pages = {589-596}, publisher = {{ACM}}, title = {Two-dimensional subset selection for hypervolume and epsilon-indicator}, year = 2014 }

Doerr, Benjamin; Doerr, Carola; Kötzing, Timo Unbiased black-box complexities of jump functions: how to cross large plateausGenetic 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)}, keywords = {benjamindoerr caroladoerr gecco imported timokoetzing year2014}, pages = {769-776}, title = {Unbiased black-box complexities of jump functions: how to cross large plateaus}, year = 2014 }

Gießen, Christian; Kötzing, Timo Robustness of populations in stochastic environmentsGenetic 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)}, keywords = {gecco imported timokoetzing year2014}, pages = {1383-1390}, title = {Robustness of populations in stochastic environments}, year = 2014 }

Kötzing, Timo Concentration of first hitting times under additive driftGenetic and Evolutionary Computation Conference (GECCO) 2014: 1391–1398
[ Abstract ] [ BibTeX ] [ 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.
@inproceedings{DBLP:conf/gecco/Kotzing14, 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}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {gecco imported timokoetzing year2014}, pages = {1391-1398}, title = {Concentration of first hitting times under additive drift}, year = 2014 }

Bringmann, Karl; Friedrich, Tobias; Klitzke, Patrick Generic Postprocessing via Subset Selection for Hypervolume and Epsilon-IndicatorParallel Problem Solving from Nature (PPSN) 2014: 518–527
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Most biobjective evolutionary algorithms maintain a population of fixed size \(\mu\) and return the final population at termination. During the optimization process many solutions are considered, but most are discarded. We present two generic postprocessing algorithms which utilize the archive of all non-dominated solutions evaluated during the search. We choose the best \(\mu\) solutions from the archive such that the hypervolume or \(\epsilon\)-indicator is maximized. This postprocessing costs no additional fitness function evaluations and has negligible runtime compared to most EMOAs. We experimentally examine our postprocessing for four standard algorithms (NSGA-II, SPEA2, SMS-EMOA, IBEA) on ten standard test functions (DTLZ 1-2,7, ZDT 1-3, WFG 3-6) and measure the average quality improvement. The median decrease of the distance to the optimal \(\epsilon\)-indicator is \(95\%\), the median decrease of the distance to the optimal hypervolume value is \(86\%\). We observe similar performance on a real-world problem (wind turbine placement).
@inproceedings{DBLP:conf/ppsn/BringmannFK14, abstract = {Most biobjective evolutionary algorithms maintain a population of fixed size \(\mu\) and return the final population at termination. During the optimization process many solutions are considered, but most are discarded. We present two generic postprocessing algorithms which utilize the archive of all non-dominated solutions evaluated during the search. We choose the best \(\mu\) solutions from the archive such that the hypervolume or \(\epsilon\)-indicator is maximized. This postprocessing costs no additional fitness function evaluations and has negligible runtime compared to most EMOAs. We experimentally examine our postprocessing for four standard algorithms (NSGA-II, SPEA2, SMS-EMOA, IBEA) on ten standard test functions (DTLZ 1-2,7, ZDT 1-3, WFG 3-6) and measure the average quality improvement. The median decrease of the distance to the optimal \(\epsilon\)-indicator is \(95\%\), the median decrease of the distance to the optimal hypervolume value is \(86\%\). We observe similar performance on a real-world problem (wind turbine placement).}, author = {Bringmann, Karl and Friedrich, Tobias and Klitzke, Patrick}, booktitle = {Parallel Problem Solving from Nature (PPSN)}, keywords = {imported ppsn tobiasfriedrich year2014}, pages = {518-527}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Generic Postprocessing via Subset Selection for Hypervolume and Epsilon-Indicator}, volume = 8672, year = 2014 }

Friedrich, Tobias; Neumann, Frank Maximizing Submodular Functions under Matroid Constraints by Multi-objective Evolutionary AlgorithmsParallel Problem Solving from Nature (PPSN) 2014: 922–931
Nominated for Best Paper Award
[ 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+5\log(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+5}\log(n)/\epsilon)\).}, author = {Friedrich, Tobias and Neumann, Frank}, booktitle = {Parallel Problem Solving from Nature (PPSN)}, keywords = {frankneumann imported ppsn tobiasfriedrich year2014}, note = {Nominated for Best Paper Award}, 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 }

Sutton, Andrew M.; Neumann, Frank Runtime Analysis of Evolutionary Algorithms on Randomly Constructed High-Density Satisfiable 3-CNF FormulasParallel 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)}, keywords = {andrewmsutton frankneumann imported ppsn year2014}, 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 }

Cseh, Ágnes; Skutella, Martin Paths to Stable AllocationsSymposium Algorithmic Game Theory (SAGT) 2014: 61–73
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
 
The stable allocation problem is one of the broadest extensions of the well-known stable marriage problem. In an allocation problem, edges of a bipartite graph have capacities and vertices have quotas to fill. Here we investigate the case of uncoordinated processes in stable allocation instances. In this setting, a feasible allocation is given and the aim is to reach a stable allocation by raising the value of the allocation along blocking edges and reducing it on worse edges if needed. Do such myopic changes lead to a stable solution? In our present work, we analyze both better and best response dynamics from an algorithmic point of view. With the help of two deterministic algorithms we show that random procedures reach a stable solution with probability one for all rational input data in both cases. Surprisingly, while there is a polynomial path to stability when better response strategies are played (even for irrational input data), the more intuitive best response steps may require exponential time. We also study the special case of correlated markets. There, random best response strategies lead to a stable allocation in expected polynomial time.
@inproceedings{cseh2014paths, abstract = {The stable allocation problem is one of the broadest extensions of the well-known stable marriage problem. In an allocation problem, edges of a bipartite graph have capacities and vertices have quotas to fill. Here we investigate the case of uncoordinated processes in stable allocation instances. In this setting, a feasible allocation is given and the aim is to reach a stable allocation by raising the value of the allocation along blocking edges and reducing it on worse edges if needed. Do such myopic changes lead to a stable solution? In our present work, we analyze both better and best response dynamics from an algorithmic point of view. With the help of two deterministic algorithms we show that random procedures reach a stable solution with probability one for all rational input data in both cases. Surprisingly, while there is a polynomial path to stability when better response strategies are played (even for irrational input data), the more intuitive best response steps may require exponential time. We also study the special case of correlated markets. There, random best response strategies lead to a stable allocation in expected polynomial time.}, author = {Cseh, Ágnes and Skutella, Martin}, booktitle = {Symposium Algorithmic Game Theory (SAGT)}, keywords = {sys:relevantfor:ae agnescseh martinskutella sagt year2014}, pages = {61-73}, title = {Paths to Stable Allocations}, year = 2014 }

Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David Counting Homomorphisms to Cactus Graphs Modulo 2Symposium on Theoretical Aspects of Computer Science (STACS) 2014: 350–361
[ 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.
@inproceedings{DBLP:conf/stacs/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}, booktitle = {Symposium on Theoretical Aspects of Computer Science (STACS)}, keywords = {andreasgoebel stacs year2014}, pages = {350-361}, title = {Counting Homomorphisms to Cactus Graphs Modulo 2}, year = 2014 }

Kötzing, Timo A Solution to Wiehagen’s ThesisSymposium on Theoretical Aspects of Computer Science (STACS) 2014: 494–505
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Wiehagen's Thesis in Inductive Inference (1991) essentially states that, for each learning criterion, learning can be done in a normalized, enumerative way. The thesis was not a formal statement and thus did not allow for a formal proof, but support was given by examples of a number of different learning criteria that can be learned by enumeration. Building on recent formalizations of learning criteria, we are now able to formalize Wiehagen's Thesis. We prove the thesis for a wide range of learning criteria, including many popular criteria from the literature. We also show the limitations of the thesis by giving four learning criteria for which the thesis does not hold (and, in two cases, was probably not meant to hold). Beyond the original formulation of the thesis, we also prove stronger versions which allow for many corollaries relating to strongly decisive and conservative learning.
@inproceedings{DBLP:conf/stacs/Kotzing14, abstract = {Wiehagen's Thesis in Inductive Inference (1991) essentially states that, for each learning criterion, learning can be done in a normalized, enumerative way. The thesis was not a formal statement and thus did not allow for a formal proof, but support was given by examples of a number of different learning criteria that can be learned by enumeration. Building on recent formalizations of learning criteria, we are now able to formalize Wiehagen's Thesis. We prove the thesis for a wide range of learning criteria, including many popular criteria from the literature. We also show the limitations of the thesis by giving four learning criteria for which the thesis does not hold (and, in two cases, was probably not meant to hold). Beyond the original formulation of the thesis, we also prove stronger versions which allow for many corollaries relating to strongly decisive and conservative learning.}, author = {Kötzing, Timo}, booktitle = {Symposium on Theoretical Aspects of Computer Science (STACS)}, keywords = {imported stacs timokoetzing year2014}, pages = {494-505}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, series = {LIPIcs}, title = {A Solution to Wiehagen's Thesis}, volume = 25, year = 2014 }

2014

Doerr, Benjamin; Friedrich, Tobias; Sauerwald, Thomas Quasirandom Rumor SpreadingACM 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, ErdHo}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\H{o}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 = {ACM Transactions on Algorithms}, keywords = {imported talg tobiasfriedrich year2014}, number = 2, pages = {9:1-9:35}, title = {Quasirandom Rumor Spreading}, volume = 11, year = 2014 }

Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David The complexity of counting homomorphisms to cactus graphs modulo 2ACM 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 = {ACM Transactions on Computation Theory}, keywords = {TOCT andreasgoebel year2014}, number = 4, pages = {17:1-17:29}, title = {The complexity of counting homomorphisms to cactus graphs modulo 2}, volume = 6, year = 2014 }

Bläsius, Thomas; Krug, Marcus; Rutter, Ignaz; Wagner, Dorothea Orthogonal Graph Drawing with Flexibility ConstraintsAlgorithmica 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}, keywords = {imported thomas thomasblaesius year2014}, number = 4, pages = {859-885}, title = {Orthogonal Graph Drawing with Flexibility Constraints}, volume = 68, year = 2014 }

Doerr, Benjamin; Doerr, Carola; Kötzing, Timo The unbiased black-box complexity of partition is polynomialArtificial 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}, keywords = {benjamindoerr caroladoerr imported timokoetzing year2014}, pages = {275-286}, title = {The unbiased black-box complexity of partition is polynomial}, volume = 216, year = 2014 }

Angelini, Patrizio; Bläsius, Thomas; Rutter, Ignaz Testing Mutual duality of Planar graphsComputational 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}, keywords = {ijcga thomasblaesius year2014}, number = 4, pages = {325-346}, title = {Testing Mutual duality of Planar graphs}, volume = 24, year = 2014 }

Sutton, Andrew M.; Neumann, Frank; Nallaperuma, Samadhi Parameterized Runtime Analyses of Evolutionary Algorithms for the Planar Euclidean Traveling Salesperson ProblemEvolutionary 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-2\lambda^{-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-2}\lambda^{-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}, keywords = {andrewmsutton ec frankneumann imported samadhinallaperuma year2014}, number = 4, pages = {595-628}, title = {Parameterized Runtime Analyses of Evolutionary Algorithms for the Planar Euclidean Traveling Salesperson Problem}, volume = 22, year = 2014 }

Bringmann, Karl; Friedrich, Tobias Convergence of Hypervolume-Based Archiving AlgorithmsIEEE Transactions on Evolutionary Computation 2014: 643–657
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Multiobjective evolutionary algorithms typically maintain a set of solutions. A crucial part of these algorithms is the archiving, which decides what solutions to keep. A \((\mu + \lambda)\) archiving algorithm defines how to choose in each generation \(\mu\) children from \(\mu\) parents and \(\lambda\) offspring together. We study mathematically the convergence behavior of hypervolume-based archiving algorithms. We distinguish two cases for the offspring generation. A best-case view leads to a study of the effectiveness of archiving algorithms. It was known that all \((\mu + 1)\)-archiving algorithms are ineffective, which means that a set with maximum hypervolume is not necessarily reached. We prove that for \(\lambda < \mu\), all archiving algorithms are ineffective. We also present upper and lower bounds for the achievable hypervolume for different classes of archiving algorithms. On the other hand, a worstcase view on the offspring generation leads to a study of the competitive ratio of archiving algorithms. This measures how much smaller hypervolumes are achieved due to not knowing the future offspring in advance. We present upper and lower bounds on the competitive ratio of different archiving algorithms and present an archiving algorithm, which is the first known computationally efficient archiving algorithm with constant competitive ratio.
@article{DBLP:journals/tec/BringmannF14, abstract = {Multiobjective evolutionary algorithms typically maintain a set of solutions. A crucial part of these algorithms is the archiving, which decides what solutions to keep. A \((\mu + \lambda)\) archiving algorithm defines how to choose in each generation \(\mu\) children from \(\mu\) parents and \(\lambda\) offspring together. We study mathematically the convergence behavior of hypervolume-based archiving algorithms. We distinguish two cases for the offspring generation. A best-case view leads to a study of the effectiveness of archiving algorithms. It was known that all \((\mu + 1)\)-archiving algorithms are ineffective, which means that a set with maximum hypervolume is not necessarily reached. We prove that for \(\lambda < \mu\), all archiving algorithms are ineffective. We also present upper and lower bounds for the achievable hypervolume for different classes of archiving algorithms. On the other hand, a worstcase view on the offspring generation leads to a study of the competitive ratio of archiving algorithms. This measures how much smaller hypervolumes are achieved due to not knowing the future offspring in advance. We present upper and lower bounds on the competitive ratio of different archiving algorithms and present an archiving algorithm, which is the first known computationally efficient archiving algorithm with constant competitive ratio.}, author = {Bringmann, Karl and Friedrich, Tobias}, journal = {IEEE Transactions on Evolutionary Computation}, keywords = {imported tevoc tobiasfriedrich year2014}, number = 5, pages = {643-657}, publisher = {IEEE}, title = {Convergence of Hypervolume-Based Archiving Algorithms}, volume = 18, year = 2014 }

Friedrich, Tobias; Rowe, Jonathan E. Genetic and Evolutionary ComputationTheoretical Computer Science 2014: 1
[ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
@article{DBLP:journals/tcs/FriedrichR14, author = {Friedrich, Tobias and Rowe, Jonathan E.}, journal = {Theoretical Computer Science}, keywords = {noabstract tobiasfriedrich year2014}, pages = 1, title = {Genetic and Evolutionary Computation}, volume = 545, year = 2014 }

Whitley, Darrell; Sutton, Andrew M.; Ochoa, Gabriela; Chicano, Francisco The component model for elementary landscapes and partial neighborhoodsTheoretical 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}, keywords = {andrewmsutton imported tcs year2014}, pages = {59-75}, title = {The component model for elementary landscapes and partial neighborhoods}, volume = 545, year = 2014 }

Kötzing, Timo; Sutton, Andrew M.; Neumann, Frank; O’Reilly, Una-May The Max problem revisited: The importance of mutation in genetic programmingTheoretical 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}, keywords = {andrewmsutton frankneumann imported tcs timokoetzing unamayoreilly year2014}, pages = {94-107}, title = {The Max problem revisited: The importance of mutation in genetic programming}, volume = 545, year = 2014 }

Kötzing, Timo Iterative learning from positive data and countersTheoretical 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}, keywords = {imported timokoetzing year2014}, pages = {155-169}, title = {Iterative learning from positive data and counters}, volume = 519, year = 2014 }