Publications of Tobias Friedrich

2021 [ nach oben ]

• 
  Bläsius, Thomas; Friedrich, Tobias; Göbel, Andreas; Levy, Jordi; Rothenberger, RalfThe Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability. Symposium on Discrete Algorithms (SODA) 2021
  [ Abstract ] [ BibTeX ] [ Download ]
   
  Satisfiability is considered the canonical NP-complete problem and is used as a starting point for hardness reductions in theory, while in practice heuristic SAT solving algorithms can solve large-scale industrial SAT instances very efficiently. This disparity between theory and practice is believed to be a result of inherent properties of industrial SAT instances that make them tractable. Two characteristic properties seem to be prevalent in the majority of real-world SAT instances, heterogeneous degree distribution and locality. To understand the impact of these two properties on SAT, we study the proof complexity of random k-SAT models that allow to control heterogeneity and locality. Our findings show that heterogeneity alone does not make SAT easy as heterogeneous random k-SAT instances have superpolynomial resolution size. This implies intractability of these instances for modern SAT-solvers. On the other hand, modeling locality with an underlying geometry leads to small unsatisfiable subformulas, which can be found within polynomial time. A key ingredient for the result on geometric random k-SAT can be found in the complexity of higher-order Voronoi diagrams. As an additional technical contribution, we show an upper bound on the number of non-empty Voronoi regions, that holds for points with random positions in a very general setting. In particular, it covers arbitrary p-norms, higher dimensions, and weights affecting the area of influence of each point multiplicatively. Our bound is linear in the total weight. This is in stark contrast to quadratic lower bounds for the worst case.
  @inproceedings{blasius2021impact, abstract = {Satisfiability is considered the canonical NP-complete problem and is used as a starting point for hardness reductions in theory, while in practice heuristic SAT solving algorithms can solve large-scale industrial SAT instances very efficiently. This disparity between theory and practice is believed to be a result of inherent properties of industrial SAT instances that make them tractable. Two characteristic properties seem to be prevalent in the majority of real-world SAT instances, heterogeneous degree distribution and locality. To understand the impact of these two properties on SAT, we study the proof complexity of random k-SAT models that allow to control heterogeneity and locality. Our findings show that heterogeneity alone does not make SAT easy as heterogeneous random k-SAT instances have superpolynomial resolution size. This implies intractability of these instances for modern SAT-solvers. On the other hand, modeling locality with an underlying geometry leads to small unsatisfiable subformulas, which can be found within polynomial time. A key ingredient for the result on geometric random k-SAT can be found in the complexity of higher-order Voronoi diagrams. As an additional technical contribution, we show an upper bound on the number of non-empty Voronoi regions, that holds for points with random positions in a very general setting. In particular, it covers arbitrary p-norms, higher dimensions, and weights affecting the area of influence of each point multiplicatively. Our bound is linear in the total weight. This is in stark contrast to quadratic lower bounds for the worst case.}, author = {Bläsius, Thomas and Friedrich, Tobias and Göbel, Andreas and Levy, Jordi and Rothenberger, Ralf}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {jordilevy sat thomasblaesius andreasgoebel tobiasfriedrich ralfrothenberger soda year2021}, title = {The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability}, year = 2021 }

2020 [ nach oben ]

• 
  Shi, Feng; Schirneck, Martin; Friedrich, Tobias; Kötzing, Timo; Neumann, FrankCorrection to: Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints. Algorithmica 2020: 3117-3123
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  In the article "Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints", we claimed a worst-case runtime of \(O(nD \log D)\) and \(O(nD)\) for the Multi-Objective Evolutionary Algorithm and the Multi-Objective \((\mu+(\lambda, \lambda))\) Genetic Algorithm, respectively, on linear profit functions under dynamic uniform constraint, where \(D = |B − B^*|\) denotes the difference between the original constraint bound \(B\) and the new one \(B^*\) . The technique used to prove these results contained an error. We correct this mistake and show a weaker bound of \(O(nD^2)\) for both algorithms instead.
  @article{shi20correction, abstract = {In the article "Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints", we claimed a worst-case runtime of \(O(nD \log D)\) and \(O(nD)\) for the Multi-Objective Evolutionary Algorithm and the Multi-Objective \((\mu+(\lambda, \lambda))\) Genetic Algorithm, respectively, on linear profit functions under dynamic uniform constraint, where \(D = |B − B^*|\) denotes the difference between the original constraint bound \(B\) and the new one \(B^*\) . The technique used to prove these results contained an error. We correct this mistake and show a weaker bound of \(O(nD^2)\) for both algorithms instead.}, author = {Shi, Feng and Schirneck, Martin and Friedrich, Tobias and Kötzing, Timo and Neumann, Frank}, journal = {Algorithmica}, keywords = {algorithmica timokoetzing fengshi tobiasfriedrich frankneumann martinschirneck year2020}, number = 10, pages = {3117-3123}, title = {Correction to: Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints}, volume = 82, year = 2020 }
• 
  Chauhan, Ankit; Friedrich, Tobias; Rothenberger, RalfGreed is Good for Deterministic Scale-Free Networks. Algorithmica 2020: 3338–3389
  [ 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.
  @article{cfr-gigfdsn-2020, 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}, journal = {Algorithmica}, keywords = {algorithmica sys:relevantfor:ae tobiasfriedrich ralfrothenberger ankitchauhan year2020}, month = {jun}, pages = {3338–3389}, title = {Greed is Good for Deterministic Scale-Free Networks}, volume = 82, year = 2020 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, AntonHyperbolic Embeddings for Near-Optimal Greedy Routing. Journal of Experimental Algorithmics (JEA) 2020
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Greedy routing computes paths between nodes in a network by successively moving to the neighbor closest to the target with respect to coordinates given by an embedding into some metric space. Its advantage is that only local information is used for routing decisions. We present different algorithms for generating graph embeddings into the hyperbolic plane that are well suited for greedy routing. In particular, our embeddings guarantee that greedy routing always succeeds in reaching the target, and we try to minimize the lengths of the resulting greedy paths. We evaluate our algorithm on multiple generated and real-world networks. For networks that are generally assumed to have a hidden underlying hyperbolic geometry, such as the Internet graph, we achieve near-optimal results (i.e., the resulting greedy paths are only slightly longer than the corresponding shortest paths). In the case of the Internet graph, they are only \(6\%\) longer when using our best algorithm, which greatly improves upon the previous best known embedding, whose creation required substantial manual intervention. In addition to measuring the stretch, we empirically evaluate our algorithms regarding the size of the coordinates of the resulting embeddings and observe how it impacts the success rate when coordinates are not represented with very high precision. Since numerical difficulties are a major issue when performing computations in the hyperbolic plane, we consider variations of our algorithm that improve the success rate when using coordinates with lower precision.
  @article{blasius2020hyperbolic, abstract = {Greedy routing computes paths between nodes in a network by successively moving to the neighbor closest to the target with respect to coordinates given by an embedding into some metric space. Its advantage is that only local information is used for routing decisions. We present different algorithms for generating graph embeddings into the hyperbolic plane that are well suited for greedy routing. In particular, our embeddings guarantee that greedy routing always succeeds in reaching the target, and we try to minimize the lengths of the resulting greedy paths. We evaluate our algorithm on multiple generated and real-world networks. For networks that are generally assumed to have a hidden underlying hyperbolic geometry, such as the Internet graph, we achieve near-optimal results (i.e., the resulting greedy paths are only slightly longer than the corresponding shortest paths). In the case of the Internet graph, they are only \(6\%\) longer when using our best algorithm, which greatly improves upon the previous best known embedding, whose creation required substantial manual intervention. In addition to measuring the stretch, we empirically evaluate our algorithms regarding the size of the coordinates of the resulting embeddings and observe how it impacts the success rate when coordinates are not represented with very high precision. Since numerical difficulties are a major issue when performing computations in the hyperbolic plane, we consider variations of our algorithm that improve the success rate when using coordinates with lower precision.}, author = {Bläsius, Thomas and Friedrich, Tobias and Katzmann, Maximilian and Krohmer, Anton}, journal = {Journal of Experimental Algorithmics (JEA)}, keywords = {jea thomasblaesius tobiasfriedrich hyperbolic_embedding antonkrohmer maximiliankatzmann year2020}, month = {March}, number = 1, title = {Hyperbolic Embeddings for Near-Optimal Greedy Routing}, volume = 25, year = 2020 }
• 
  Birnick, Johann; Bläsius, Thomas; Friedrich, Tobias; Naumann, Felix; Papenbrock, Thorsten; Schirneck, MartinHitting Set Enumeration with Partial Information for Unique Column Combination Discovery. Proceedings of the VLDB Endowment 2020: 2270 - 2283
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Unique column combinations (UCCs) are a fundamental concept in relational databases. They identify entities in the data and support various data management activities. Still, UCCs are usually not explicitly defined and need to be discovered. State-of-the-art data profiling algorithms are able to efficiently discover UCCs in moderately sized datasets, but they tend to fail on large and, in particular, on wide datasets due to run time and memory limitations. In this paper, we introduce HPIValid, a novel UCC discovery algorithm that implements a faster and more resource-saving search strategy. HPIValid models the metadata discovery as a hitting set enumeration problem in hypergraphs. In this way, it combines efficient discovery techniques from data profiling research with the most recent theoretical insights into enumeration algorithms. Our evaluation shows that HPIValid is not only orders of magnitude faster than related work, it also has a much smaller memory footprint.
  @article{birnick2020hitting, abstract = {Unique column combinations (UCCs) are a fundamental concept in relational databases. They identify entities in the data and support various data management activities. Still, UCCs are usually not explicitly defined and need to be discovered. State-of-the-art data profiling algorithms are able to efficiently discover UCCs in moderately sized datasets, but they tend to fail on large and, in particular, on wide datasets due to run time and memory limitations. In this paper, we introduce HPIValid, a novel UCC discovery algorithm that implements a faster and more resource-saving search strategy. HPIValid models the metadata discovery as a hitting set enumeration problem in hypergraphs. In this way, it combines efficient discovery techniques from data profiling research with the most recent theoretical insights into enumeration algorithms. Our evaluation shows that HPIValid is not only orders of magnitude faster than related work, it also has a much smaller memory footprint.}, author = {Birnick, Johann and Bläsius, Thomas and Friedrich, Tobias and Naumann, Felix and Papenbrock, Thorsten and Schirneck, Martin}, journal = {Proceedings of the VLDB Endowment}, keywords = {pvldb thomasblaesius johannbirnick tobiasfriedrich thorstenpapenbrock felixnaumann martinschirneck year2020}, number = 11, pages = {2270 - 2283}, title = {Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery}, volume = 13, year = 2020 }
• 
  Friedrich, Tobias; Kötzing, Timo; Lagodzinski, J. A. Gregor; Neumann, Frank; Schirneck, MartinAnalysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints. Theoretical Computer Science 2020: 3-19
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Linear functions have gained great attention in the run time analysis of evolutionary computation methods. The corresponding investigations have provided many effective tools for analyzing more complex problems. So far, the runtime analysis of evolutionary algorithms has mainly focused on unconstrained problems, but problems occurring in applications frequently involve constraints. Therefore, there is a strong need to extend the methods for analyzing unconstrained problems to a setting involving constraints. In this paper, we consider the behavior of the classical (1+1) evolutionary algorithm on linear functions under linear constraint. We show tight bounds in the case where the constraint is given by the OneMax function and the objective function is given by either the OneMax or the BinVal function. For the general case we present upper and lower bounds.
  @article{friedrich2020analysis, abstract = {Linear functions have gained great attention in the run time analysis of evolutionary computation methods. The corresponding investigations have provided many effective tools for analyzing more complex problems. So far, the runtime analysis of evolutionary algorithms has mainly focused on unconstrained problems, but problems occurring in applications frequently involve constraints. Therefore, there is a strong need to extend the methods for analyzing unconstrained problems to a setting involving constraints. In this paper, we consider the behavior of the classical (1+1) evolutionary algorithm on linear functions under linear constraint. We show tight bounds in the case where the constraint is given by the OneMax function and the objective function is given by either the OneMax or the BinVal function. For the general case we present upper and lower bounds.}, author = {Friedrich, Tobias and Kötzing, Timo and Lagodzinski, J. A. Gregor and Neumann, Frank and Schirneck, Martin}, editor = {Oliveto, Pietro S. and Sutton, Andrew M.}, journal = {Theoretical Computer Science}, keywords = {gregorlagodzinski tcs timokoetzing year2018 tobiasfriedrich frankneumann martinschirneck}, pages = {3-19}, title = {Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints}, volume = 832, year = 2020 }
• 
  Bläsius, Thomas; Böther, Maximilian; Fischbeck, Philipp; Friedrich, Tobias; Gries, Alina; Hüffner, Falk; Kißig, Otto; Lenzner, Pascal; Molitor, Louise; Schiller, Leon; Wells, Armin; Witheger, SimonA Strategic Routing Framework and Algorithms for Computing Alternative Paths. Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) 2020
  [ Abstract ] [ BibTeX ] [ Download ]
   
  Traditional navigation services find the fastest route for a single driver. Though always using the fastest route seems desirable for every individual, selfish behavior can have undesirable effects such as higher energy consumption and avoidable congestion, even leading to higher overall and individual travel times. In contrast, strategic routing aims at optimizing the traffic for all agents regarding a global optimization goal. We introduce a framework to formalize real-world strategic routing scenarios as algorithmic problems and study one of them, which we call Single Alternative Path (SAP), in detail. There, we are given an original route between a single origin–destination pair. The goal is to suggest an alternative route to all agents that optimizes the overall travel time under the assumption that the agents distribute among both routes according to a psychological model, for which we introduce the concept of Pareto-conformity. We show that the SAP problem is NP-complete, even for such models. Nonetheless, assuming Pareto-conformity, we give multiple algorithms for different variants of SAP, using multi-criteria shortest path algorithms as subroutines.Moreover, we prove that several natural models are in fact Pareto-conform. The implementation and evaluation of our algorithms serve as a proof of concept, showing that SAP can be solved in reasonable time even though the algorithms have exponential running time in the worst case.
  @inproceedings{blasius2020strategic, abstract = {Traditional navigation services find the fastest route for a single driver. Though always using the fastest route seems desirable for every individual, selfish behavior can have undesirable effects such as higher energy consumption and avoidable congestion, even leading to higher overall and individual travel times. In contrast, strategic routing aims at optimizing the traffic for all agents regarding a global optimization goal. We introduce a framework to formalize real-world strategic routing scenarios as algorithmic problems and study one of them, which we call Single Alternative Path (SAP), in detail. There, we are given an original route between a single origin–destination pair. The goal is to suggest an alternative route to all agents that optimizes the overall travel time under the assumption that the agents distribute among both routes according to a psychological model, for which we introduce the concept of Pareto-conformity. We show that the SAP problem is NP-complete, even for such models. Nonetheless, assuming Pareto-conformity, we give multiple algorithms for different variants of SAP, using multi-criteria shortest path algorithms as subroutines.Moreover, we prove that several natural models are in fact Pareto-conform. The implementation and evaluation of our algorithms serve as a proof of concept, showing that SAP can be solved in reasonable time even though the algorithms have exponential running time in the worst case.}, author = {Bläsius, Thomas and Böther, Maximilian and Fischbeck, Philipp and Friedrich, Tobias and Gries, Alina and Hüffner, Falk and Kißig, Otto and Lenzner, Pascal and Molitor, Louise and Schiller, Leon and Wells, Armin and Witheger, Simon}, booktitle = {Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS)}, keywords = {maximilianboether falkhueffner tobiasfriedrich simonwietheger arminwells atmos ottokissig sys:relevantfor:ae philippfischbeck thomasblaesius louisemolitor alinagries leonschiller pascallenzner year2020}, title = {A Strategic Routing Framework and Algorithms for Computing Alternative Paths}, year = 2020 }
• 
  Doskoč, Vanja; Friedrich, Tobias; Göbel, Andreas; Neumann, Aneta; Neumann, Frank; Quinzan, FrancescoNon-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings. European Conference on Artificial Intelligence (ECAI) 2020: 435-442
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We study the problem of maximizing a non-monotone submodular function under multiple knapsack constraints. We propose a simple discrete greedy algorithm to approach this problem, and prove that it yields strong approximation guarantees for functions with bounded curvature. In contrast to other heuristics, this does not require problem relaxation to continuous domains and it maintains a constant-factor approximation guarantee in the problem size. In the case of a single knapsack, our analysis suggests that the standard greedy can be used in non-monotone settings. Additionally, we study this problem in a dynamic setting, in which knapsacks change during the optimization process. We modify our greedy algorithm to avoid a complete restart at each constraint update. This modification retains the approximation guarantees of the static case. We evaluate our results experimentally on a video summarization and sensor placement task. We show that our proposed algorithm competes with the state-of-the-art in static settings. Furthermore, we show that in dynamic settings with tight computational time budget, our modified greedy yields significant improvements over starting the greedy from scratch, in terms of the solution quality achieved.
  @inproceedings{doskoc2020nonmonotone, abstract = {We study the problem of maximizing a non-monotone submodular function under multiple knapsack constraints. We propose a simple discrete greedy algorithm to approach this problem, and prove that it yields strong approximation guarantees for functions with bounded curvature. In contrast to other heuristics, this does not require problem relaxation to continuous domains and it maintains a constant-factor approximation guarantee in the problem size. In the case of a single knapsack, our analysis suggests that the standard greedy can be used in non-monotone settings. Additionally, we study this problem in a dynamic setting, in which knapsacks change during the optimization process. We modify our greedy algorithm to avoid a complete restart at each constraint update. This modification retains the approximation guarantees of the static case. We evaluate our results experimentally on a video summarization and sensor placement task. We show that our proposed algorithm competes with the state-of-the-art in static settings. Furthermore, we show that in dynamic settings with tight computational time budget, our modified greedy yields significant improvements over starting the greedy from scratch, in terms of the solution quality achieved.}, author = {Doskoč, Vanja and Friedrich, Tobias and Göbel, Andreas and Neumann, Aneta and Neumann, Frank and Quinzan, Francesco}, booktitle = {European Conference on Artificial Intelligence (ECAI)}, keywords = {anetaneumann vanjadoskoc andreasgoebel francescoquinzan tobiasfriedrich ecai frankneumann year2020}, pages = {435-442}, publisher = {{IOS} Press}, title = {Non-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings}, year = 2020 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Schirneck, MartinThe Minimization of Random Hypergraphs. European Symposium on Algorithms (ESA) 2020: 21:1-21:15
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We investigate the maximum-entropy model \(\mathcal{B}_{n,m,p}\) for random \(n\)-vertex, \(m\)-edge multi-hypergraphs with expected edge size \(pn\). We show that the expected size of the minimization \(\min(\mathcal{B}_{n,m,p})\), i.e., the number of inclusion-wise minimal edges of \(\mathcal{B}_{n,m,p}\), undergoes a phase transition with respect to \(m\). If \(m\) is at most \(1/(1-p)^(1-p)n}\), then \(\mathrm{E[|\min(\mathcal{B}_{n,m,p})|]\) is of order \(\Theta(m)\), while for \(m ge 1/(1-p)^(1-p+\varepsilon)n}\) for any \(\varepsilon > 0\), it is \(\Theta( 2^(\mathrm{H(\alpha) + (1-\alpha) \log_2 p) n/ \sqrt{n})\). Here, \(\mathrm{H}\) denotes the binary entropy function and \(alpha = - (\log_{1-p m)/n\). The result implies that the maximum expected number of minimal edges over all \(m\) is \(\Theta((1+p)^n/\sqrt{n})\). Our structural findings have algorithmic implications for minimizing an input hypergraph. This has applications in the profiling of relational databases as well as for the Orthogonal Vectors problem studied in fine-grained complexity. We make several technical contributions that are of independent interest in probability. First, we improve the Chernoff--Hoeffding theorem on the tail of the binomial distribution. In detail, we show that for a binomial variable \(Y sim \mathrm{Bin(n,p)\) and any \(0 < x < p\), it holds that \(\mathrm{P[Y le xn] = \Theta( 2^-\!\mathrm{D(x \,\|}\, p) n}/\sqrt{n})\), where \(\mathrm{D}\) is the binary Kullback--Leibler divergence between Bernoulli distributions. We give explicit upper and lower bounds on the constants hidden in the big-O notation that hold for all \(n\). Secondly, we establish the fact that the probability of a set of cardinality \(i\) being minimal after \(m\) i.i.d. maximum-entropy trials exhibits a sharp threshold behavior at \(i^* = n + \log_{1-p m\).
  @inproceedings{Blaesius20MinimizationESA, abstract = {We investigate the maximum-entropy model \(\mathcal{B}_{n,m,p}\) for random \(n\)-vertex, \(m\)-edge multi-hypergraphs with expected edge size \(pn\). We show that the expected size of the minimization \(\min(\mathcal{B}_{n,m,p})\), i.e., the number of inclusion-wise minimal edges of \(\mathcal{B}_{n,m,p}\), undergoes a phase transition with respect to \(m\). If \(m\) is at most \(1/(1-p)^{(1-p)n}\), then \(\mathrm{E}[|\min(\mathcal{B}_{n,m,p})|]\) is of order \(\Theta(m)\), while for \(m \ge 1/(1-p)^{(1-p+\varepsilon)n}\) for any \(\varepsilon > 0\), it is \(\Theta( 2^{(\mathrm{H}(\alpha) + (1-\alpha) \log_2 p) n}/ \sqrt{n})\). Here, \(\mathrm{H}\) denotes the binary entropy function and \(\alpha = - (\log_{1-p} m)/n\). The result implies that the maximum expected number of minimal edges over all \(m\) is \(\Theta((1+p)^n/\sqrt{n})\). Our structural findings have algorithmic implications for minimizing an input hypergraph. This has applications in the profiling of relational databases as well as for the Orthogonal Vectors problem studied in fine-grained complexity. We make several technical contributions that are of independent interest in probability. First, we improve the Chernoff&ndash;Hoeffding theorem on the tail of the binomial distribution. In detail, we show that for a binomial variable \(Y \sim \mathrm{Bin}(n,p)\) and any \(0 < x < p\), it holds that \(\mathrm{P}[Y \le xn] = \Theta( 2^{-\!\mathrm{D}(x \,{\|}\, p) n}/\sqrt{n})\), where \(\mathrm{D}\) is the binary Kullback&ndash;Leibler divergence between Bernoulli distributions. We give explicit upper and lower bounds on the constants hidden in the big-O notation that hold for all \(n\). Secondly, we establish the fact that the probability of a set of cardinality \(i\) being minimal after \(m\) i.i.d. maximum-entropy trials exhibits a sharp threshold behavior at \(i^* = n + \log_{1-p} m\).}, author = {Bläsius, Thomas and Friedrich, Tobias and Schirneck, Martin}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {esa thomasblaesius tobiasfriedrich martinschirneck year2020}, pages = {21:1-21:15}, title = {The Minimization of Random Hypergraphs}, year = 2020 }
• 
  Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna; Molitor, LouiseFair Tree Connection Games with Topology-Dependent Edge Cost. Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2020
  [ BibTeX ]
   
  @inproceedings{bilo2020connection, author = {Bilò, Davide and Friedrich, Tobias and Lenzner, Pascal and Melnichenko, Anna and Molitor, Louise}, booktitle = {Foundations of Software Technology and Theoretical Computer Science (FSTTCS)}, keywords = {fsttcs louisemolitor tobiasfriedrich annamelnichenko pascallenzner year2020}, title = {Fair Tree Connection Games with Topology-Dependent Edge Cost}, year = 2020 }
• 
  Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rizzo, Manuel; Zahn, ArthurMemetic Genetic Algorithms for Time Series Compression by Piecewise Linear Approximation. International Conference on Neural Information Processing (ICONIP) 2020
  [ Abstract ] [ BibTeX ] [ Download ]
   
  Time series are sequences of data indexed by time. Such data are collected in various domains, often in massive amounts, such that storing them proves challenging. Thus, time series are commonly stored in a compressed format. An important compression approach is piecewise linear approximation (PLA), which only keeps a small set of time points and interpolates the remainder linearly. Picking a subset of time points such that the PLA minimizes the mean squared error to the original time series is a challenging task, naturally lending itself to heuristics. We propose the piecewise linear approximation genetic algorithm (PLA-GA) for compressing time series by PLA. The PLA-GA is a memetic \((\mu + \lambda)\) GA that makes use of two distinct operators tailored to time series compression. First, we add special individuals to the initial population that are derived using established PLA heuristics. Second, we propose a novel local search operator that greedily improves a compressed time series. We compare the PLA-GA empirically with existing evolutionary approaches and with a deterministic PLA algorithm, known as Bellman's algorithm, that is optimal for the restricted setting of sampling. In both cases, the PLA-GA approximates the original time series better and quicker. Further, it drastically outperforms Bellman's algorithm with increasing instance size with respect to run time until finding a solution of equal or better quality -- we observe speed-up factors between 7 and 100 for instances of 90,000 to 100,000 data points.
  @inproceedings{friedrich2020memetic, abstract = {Time series are sequences of data indexed by time. Such data are collected in various domains, often in massive amounts, such that storing them proves challenging. Thus, time series are commonly stored in a compressed format. An important compression approach is piecewise linear approximation (PLA), which only keeps a small set of time points and interpolates the remainder linearly. Picking a subset of time points such that the PLA minimizes the mean squared error to the original time series is a challenging task, naturally lending itself to heuristics. We propose the piecewise linear approximation genetic algorithm (PLA-GA) for compressing time series by PLA. The PLA-GA is a memetic \((\mu + \lambda)\) GA that makes use of two distinct operators tailored to time series compression. First, we add special individuals to the initial population that are derived using established PLA heuristics. Second, we propose a novel local search operator that greedily improves a compressed time series. We compare the PLA-GA empirically with existing evolutionary approaches and with a deterministic PLA algorithm, known as Bellman's algorithm, that is optimal for the restricted setting of sampling. In both cases, the PLA-GA approximates the original time series better and quicker. Further, it drastically outperforms Bellman's algorithm with increasing instance size with respect to run time until finding a solution of equal or better quality &ndash; we observe speed-up factors between 7 and 100 for instances of 90,000 to 100,000 data points.}, author = {Friedrich, Tobias and Krejca, Martin S. and Lagodzinski, J. A. Gregor and Rizzo, Manuel and Zahn, Arthur}, booktitle = {International Conference on Neural Information Processing (ICONIP)}, keywords = {gregorlagodzinski martinskrejca manuelrizzo tobiasfriedrich arthurzahn iconip year2020}, title = {Memetic Genetic Algorithms for Time Series Compression by Piecewise Linear Approximation}, year = 2020 }
• 
  Echzell, Hagen; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, AnnaFlow-Based Network Creation Games. International Joint Conference on Artificial Intelligence (IJCAI) 2020: 139-145
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Network Creation Games (NCGs) model the creation of decentralized communication networks like the Internet. In such games strategic agents corresponding to network nodes selfishly decide with whom to connect to optimize some objective function. Past research intensively analyzed models where the agents strive for a central position in the network. This models agents optimizing the network for low-latency applications like VoIP. However, with today's abundance of streaming services it is important to ensure that the created network can satisfy the increased bandwidth demand. To the best of our knowledge, this natural problem of the decentralized strategic creation of networks with sufficient bandwidth has not yet been studied. We introduce Flow-Based NCGs where the selfish agents focus on bandwidth instead of latency. In essence, budget-constrained agents create network links to maximize their minimum or average network flow value to all other network nodes. Equivalently, this can also be understood as agents who create links to increase their connectivity and thus also the robustness of the network. For this novel type of NCG we prove that pure Nash equilibria exist, we give a simple algorithm for computing optimal networks, we show that the Price of Stability is~1 and we prove an (almost) tight bound of 2 on the Price of Anarchy. Last but not least, we show that our models do not admit a potential function.
  @inproceedings{echzell2020flowbased, abstract = {Network Creation Games (NCGs) model the creation of decentralized communication networks like the Internet. In such games strategic agents corresponding to network nodes selfishly decide with whom to connect to optimize some objective function. Past research intensively analyzed models where the agents strive for a central position in the network. This models agents optimizing the network for low-latency applications like VoIP. However, with today's abundance of streaming services it is important to ensure that the created network can satisfy the increased bandwidth demand. To the best of our knowledge, this natural problem of the decentralized strategic creation of networks with sufficient bandwidth has not yet been studied. We introduce Flow-Based NCGs where the selfish agents focus on bandwidth instead of latency. In essence, budget-constrained agents create network links to maximize their minimum or average network flow value to all other network nodes. Equivalently, this can also be understood as agents who create links to increase their connectivity and thus also the robustness of the network. For this novel type of NCG we prove that pure Nash equilibria exist, we give a simple algorithm for computing optimal networks, we show that the Price of Stability is&nbsp;1 and we prove an (almost) tight bound of 2 on the Price of Anarchy. Last but not least, we show that our models do not admit a potential function.}, author = {Echzell, Hagen and Friedrich, Tobias and Lenzner, Pascal and Melnichenko, Anna}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, editor = {Bessiere, Christian}, keywords = {ijcai hagenechzell tobiasfriedrich annamelnichenko pascallenzner year2020}, pages = {139-145}, publisher = {ijcai.org}, title = {Flow-Based Network Creation Games}, year = 2020 }
• 
  Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Katzmann, MaximilianSolving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs. Symposium on the Theoretical Aspects of Computer Science (STACS) 2020: 25:1-25:14
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  The VertexCover problem is proven to be computationally hard in different ways: It is NP-complete to find an optimal solution and even NP-hard to find an approximation with reasonable factors. In contrast, recent experiments suggest that on many real-world networks the run time to solve VertexCover is way smaller than even the best known FPT-approaches can explain. Similarly, greedy algorithms deliver very good approximations to the optimal solution in practice. We link these observations to two properties that are observed in many real-world networks, namely a heterogeneous degree distribution and high clustering. To formalize these properties and explain the observed behavior, we analyze how a branch-and-reduce algorithm performs on hyperbolic random graphs, which have become increasingly popular for modeling real-world networks. In fact, we are able to show that the VertexCover problem on hyperbolic random graphs can be solved in polynomial time, with high probability. The proof relies on interesting structural properties of hyperbolic random graphs. Since these predictions of the model are interesting in their own right, we conducted experiments on real-world networks showing that these properties are also observed in practice. When utilizing the same structural properties in an adaptive greedy algorithm, further experiments suggest that, on real instances, this leads to better approximations than the standard greedy approach within reasonable time. We link these observations to two properties that are observed in many real-world networks, namely a heterogeneous degree distribution and high clustering. To formalize these properties and explain the observed behavior, we analyze how a branch-and-reduce algorithm performs on hyperbolic random graphs, which have become increasingly popular for modeling real-world networks. In fact, we are able to show that the VertexCover problem on hyperbolic random graphs can be solved in polynomial time, with high probability. The proof relies on interesting structural properties of hyperbolic random graphs. Since these predictions of the model are interesting in their own right, we conducted experiments on real-world networks showing that these properties are also observed in practice. When utilizing the same structural properties in an adaptive greedy algorithm, further experiments suggest that this leads to even better approximations than the standard greedy approach on real instances.
  @inproceedings{blasius2020solving, abstract = {The VertexCover problem is proven to be computationally hard in different ways: It is NP-complete to find an optimal solution and even NP-hard to find an approximation with reasonable factors. In contrast, recent experiments suggest that on many real-world networks the run time to solve VertexCover is way smaller than even the best known FPT-approaches can explain. Similarly, greedy algorithms deliver very good approximations to the optimal solution in practice. We link these observations to two properties that are observed in many real-world networks, namely a heterogeneous degree distribution and high clustering. To formalize these properties and explain the observed behavior, we analyze how a branch-and-reduce algorithm performs on hyperbolic random graphs, which have become increasingly popular for modeling real-world networks. In fact, we are able to show that the VertexCover problem on hyperbolic random graphs can be solved in polynomial time, with high probability. The proof relies on interesting structural properties of hyperbolic random graphs. Since these predictions of the model are interesting in their own right, we conducted experiments on real-world networks showing that these properties are also observed in practice. When utilizing the same structural properties in an adaptive greedy algorithm, further experiments suggest that, on real instances, this leads to better approximations than the standard greedy approach within reasonable time. We link these observations to two properties that are observed in many real-world networks, namely a heterogeneous degree distribution and high clustering. To formalize these properties and explain the observed behavior, we analyze how a branch-and-reduce algorithm performs on hyperbolic random graphs, which have become increasingly popular for modeling real-world networks. In fact, we are able to show that the VertexCover problem on hyperbolic random graphs can be solved in polynomial time, with high probability. The proof relies on interesting structural properties of hyperbolic random graphs. Since these predictions of the model are interesting in their own right, we conducted experiments on real-world networks showing that these properties are also observed in practice. When utilizing the same structural properties in an adaptive greedy algorithm, further experiments suggest that this leads to even better approximations than the standard greedy approach on real instances.}, author = {Bläsius, Thomas and Fischbeck, Philipp and Friedrich, Tobias and Katzmann, Maximilian}, booktitle = {Symposium on the Theoretical Aspects of Computer Science (STACS)}, keywords = {philippfischbeck thomasblaesius stacs tobiasfriedrich maximiliankatzmann hyperbolic_analysis year2020}, pages = {25:1-25:14}, title = {Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs}, year = 2020 }

2019 [ nach oben ]

• 
  Friedrich, Tobias; Krejca, Martin S.; Rothenberger, Ralf; Arndt, Tobias; Hafner, Danijar; Kellermeier, Thomas; Krogmann, Simon; Razmjou, ArminRouting for On-Street Parking Search using Probabilistic Data. AI Communications 2019: 113-124
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  A significant percentage of urban traffic is caused by the search for parking spots. One possible approach to improve this situation is to guide drivers along routes which are likely to have free parking spots. The task of finding such a route can be modeled as a probabilistic graph problem which is NP-complete. Thus, we propose heuristic approaches for solving this problem and evaluate them experimentally. For this, we use probabilities of finding a parking spot, which are based on publicly available empirical data from TomTom International B.V. Additionally, we propose a heuristic that relies exclusively on conventional road attributes. Our experiments show that this algorithm comes close to the baseline by a factor of 1.3 in our cost measure. Last, we complement our experiments with results from a field study, comparing the success rates of our algorithms against real human drivers.
  @article{friedrich2019routing, abstract = {A significant percentage of urban traffic is caused by the search for parking spots. One possible approach to improve this situation is to guide drivers along routes which are likely to have free parking spots. The task of finding such a route can be modeled as a probabilistic graph problem which is NP-complete. Thus, we propose heuristic approaches for solving this problem and evaluate them experimentally. For this, we use probabilities of finding a parking spot, which are based on publicly available empirical data from TomTom International B.V. Additionally, we propose a heuristic that relies exclusively on conventional road attributes. Our experiments show that this algorithm comes close to the baseline by a factor of 1.3 in our cost measure. Last, we complement our experiments with results from a field study, comparing the success rates of our algorithms against real human drivers.}, author = {Friedrich, Tobias and Krejca, Martin S. and Rothenberger, Ralf and Arndt, Tobias and Hafner, Danijar and Kellermeier, Thomas and Krogmann, Simon and Razmjou, Armin}, journal = {AI Communications}, keywords = {tobiasarndt year2019 martinskrejca thomaskellermeier tobiasfriedrich arminrazmjou ralfrothenberger simonkrogmann danijarhafner}, number = 2, pages = {113-124}, title = {Routing for On-Street Parking Search using Probabilistic Data}, volume = 32, year = 2019 }
• 
  Shi, Feng; Schirneck, Martin; Friedrich, Tobias; Kötzing, Timo; Neumann, FrankReoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints. Algorithmica 2019: 828-857
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Rigorous runtime analysis is a major approach towards understanding evolutionary computing techniques, and in this area linear pseudo-Boolean objective functions play a central role. Having an additional linear constraint is then equivalent to the NP-hard Knapsack problem, certain classes thereof have been studied in recent works. In this article, we present a dynamic model of optimizing linear functions under uniform constraints. Starting from an optimal solution with respect to a given constraint bound, we investigate the runtimes that different evolutionary algorithms need to recompute an optimal solution when the constraint bound changes by a certain amount. The classical \((1+1)\) EA and several population-based algorithms are designed for that purpose, and are shown to recompute efficiently. Furthermore, a variant of the \((1+(\lambda,\lambda))\) GA for the dynamic optimization problem is studied, whose performance is better when the change of the constraint bound is small.
  @article{shi2019reoptimization, abstract = {Rigorous runtime analysis is a major approach towards understanding evolutionary computing techniques, and in this area linear pseudo-Boolean objective functions play a central role. Having an additional linear constraint is then equivalent to the NP-hard Knapsack problem, certain classes thereof have been studied in recent works. In this article, we present a dynamic model of optimizing linear functions under uniform constraints. Starting from an optimal solution with respect to a given constraint bound, we investigate the runtimes that different evolutionary algorithms need to recompute an optimal solution when the constraint bound changes by a certain amount. The classical \((1+1)\) EA and several population-based algorithms are designed for that purpose, and are shown to recompute efficiently. Furthermore, a variant of the \((1+(\lambda,\lambda))\) GA for the dynamic optimization problem is studied, whose performance is better when the change of the constraint bound is small.}, author = {Shi, Feng and Schirneck, Martin and Friedrich, Tobias and Kötzing, Timo and Neumann, Frank}, journal = {Algorithmica}, keywords = {algorithmica year2019 timokoetzing fengshi tobiasfriedrich frankneumann martinschirneck}, number = 2, pages = {828-857}, title = {Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints}, volume = 81, year = 2019 }
• 
  Doerr, Benjamin; Fischbeck, Philipp; Frahnow, Clemens; Friedrich, Tobias; Kötzing, Timo; Schirneck, MartinIsland Models Meet Rumor Spreading. Algorithmica 2019: 886-915
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ 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 both measures (i) by improving the run time bounds via a careful analysis, (ii) by balancing individual computation and communication in a more appropriate manner, and (iii) by replacing the usual communicate-with-all approach with randomized rumor spreading. In the latter, 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 island models running simple (1+1) evolutionary algorithms to optimize the classic test functions OneMax and LeadingOnes. We investigate binary trees, d-dimensional tori, and complete graphs as communication topologies.
  @article{doerr2019island, 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 both measures (i) by improving the run time bounds via a careful analysis, (ii) by balancing individual computation and communication in a more appropriate manner, and (iii) by replacing the usual communicate-with-all approach with randomized rumor spreading. In the latter, 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 island models running simple (1+1) evolutionary algorithms to optimize the classic test functions OneMax and LeadingOnes. We investigate binary trees, d-dimensional tori, and complete graphs as communication topologies.}, author = {Doerr, Benjamin and Fischbeck, Philipp and Frahnow, Clemens and Friedrich, Tobias and Kötzing, Timo and Schirneck, Martin}, journal = {Algorithmica}, keywords = {algorithmica philippfischbeck year2019 timokoetzing tobiasfriedrich benjamindoerr martinschirneck clemensfrahnow}, month = {feb}, number = 2, pages = {886-915}, title = {Island Models Meet Rumor Spreading}, volume = 81, year = 2019 }
• 
  Neumann, Aneta; Neumann, Frank; Friedrich, TobiasQuasi-random Image Transition and Animation. Australian Journal of Intelligent Information Processing Systems 2019: 10-18
  [ Abstract ] [ BibTeX ] [ Download ]
   
  Evolutionary algorithms have been widely used in the area of creativity. Recently, evolutionary processes have been used to create artistic image transition processes using random walks. In this paper, we explore the use of quasi-random walks for evolutionary image transition and animation. Quasi-random walks show similar features as standard random walks, but with much less randomness. We utilize this established model from discrete mathematics and show how agents carrying out quasi-random walks can be used for evolutionary image transition and animation. The key idea is to generalize the notion of quasi-random walks and let a set of autonomous agents perform quasi-random walks painting an image. Each agent has one particular target image that they paint when following a sequence of directions for their quasi-random walk.The sequence can easily be chosen by a user and allows them to produce a wide range of different transition patterns and animations.
  @article{neumann2019quasirandom, abstract = {Evolutionary algorithms have been widely used in the area of creativity. Recently, evolutionary processes have been used to create artistic image transition processes using random walks. In this paper, we explore the use of quasi-random walks for evolutionary image transition and animation. Quasi-random walks show similar features as standard random walks, but with much less randomness. We utilize this established model from discrete mathematics and show how agents carrying out quasi-random walks can be used for evolutionary image transition and animation. The key idea is to generalize the notion of quasi-random walks and let a set of autonomous agents perform quasi-random walks painting an image. Each agent has one particular target image that they paint when following a sequence of directions for their quasi-random walk.The sequence can easily be chosen by a user and allows them to produce a wide range of different transition patterns and animations.}, author = {Neumann, Aneta and Neumann, Frank and Friedrich, Tobias}, journal = {Australian Journal of Intelligent Information Processing Systems}, keywords = {anetaneumann year2019 ajiips tobiasfriedrich frankneumann}, number = 1, pages = {10-18}, title = {Quasi-random Image Transition and Animation}, volume = 16, year = 2019 }
• 
  Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.Unbiasedness of Estimation-of-Distribution Algorithms. Theoretical Computer Science 2019: 46-59
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  In the context of black-box optimization, black-box complexity is used for understanding the inherent difficulty of a given optimization problem. Central to our understanding of nature-inspired search heuristics in this context is the notion of unbiasedness. Specialized black-box complexities have been developed in order to better understand the limitations of these heuristics – especially of (population-based) evolutionary algorithms (EAs). In contrast to this, we focus on a model for algorithms explicitly maintaining a probability distribution over the search space: so-called estimation-of-distribution algorithms (EDAs). We consider the recently introduced \(n\)-Bernoulli-\(\lambda\)-EDA framework, which subsumes, for example, the commonly known EDAs PBIL, UMDA, \(\lambda\)-MMAS\(_\textrm{IB}\), and cGA. We show that an \(n\)-Bernoulli-\(\lambda\)-EDA is unbiased if and only if its probability distribution satisfies a certain invariance property under isometric automorphisms of \([0, 1]^n\). By restricting how an \(n\)-Bernoulli-\(\lambda\)-EDA can perform an update, in a way common to many examples, we derive conciser characterizations, which are easy to verify. We demonstrate this by showing that our examples above are all unbiased.
  @article{friedrich2019unbiasedness, abstract = {In the context of black-box optimization, black-box complexity is used for understanding the inherent difficulty of a given optimization problem. Central to our understanding of nature-inspired search heuristics in this context is the notion of unbiasedness. Specialized black-box complexities have been developed in order to better understand the limitations of these heuristics – especially of (population-based) evolutionary algorithms (EAs). In contrast to this, we focus on a model for algorithms explicitly maintaining a probability distribution over the search space: so-called estimation-of-distribution algorithms (EDAs). We consider the recently introduced \(n\)-Bernoulli-\(\lambda\)-EDA framework, which subsumes, for example, the commonly known EDAs PBIL, UMDA, \(\lambda\)-MMAS\(_\textrm{IB}\), and cGA. We show that an \(n\)-Bernoulli-\(\lambda\)-EDA is unbiased if and only if its probability distribution satisfies a certain invariance property under isometric automorphisms of \([0, 1]^n\). By restricting how an \(n\)-Bernoulli-\(\lambda\)-EDA can perform an update, in a way common to many examples, we derive conciser characterizations, which are easy to verify. We demonstrate this by showing that our examples above are all unbiased.}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S.}, journal = {Theoretical Computer Science}, keywords = {tcs year2019 martinskrejca timokoetzing tobiasfriedrich}, pages = {46-59}, title = {Unbiasedness of Estimation-of-Distribution Algorithms}, volume = 785, year = 2019 }
• 
  Friedrich, Tobias; Göbel, Andreas; Neumann, Frank; Quinzan, Francesco; Rothenberger, RalfGreedy Maximization of Functions with Bounded Curvature Under Partition Matroid Constraints. Conference on Artificial Intelligence (AAAI) 2019: 2272-2279
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We investigate the performance of a deterministic GREEDY algorithm for the problem of maximizing functions under a partition matroid constraint. We consider non-monotone submodular functions and monotone subadditive functions. Even though constrained maximization problems of monotone submodular functions have been extensively studied, little is known about greedy maximization of non-monotone submodular functions or monotone subadditive functions. We give approximation guarantees for GREEDY on these problems, in terms of the curvature. We find that this simple heuristic yields a strong approximation guarantee on a broad class of functions. We discuss the applicability of our results to three real-world problems: Maximizing the determinant function of a positive semidefinite matrix, and related problems such as the maximum entropy sampling problem, the constrained maximum cut problem on directed graphs, and combinatorial auction games. We conclude that GREEDY is well-suited to approach these problems. Overall, we present evidence to support the idea that, when dealing with constrained maximization problems with bounded curvature, one needs not search for (approximate) monotonicity to get good approximate solutions.
  @inproceedings{AAAI19a, abstract = {We investigate the performance of a deterministic GREEDY algorithm for the problem of maximizing functions under a partition matroid constraint. We consider non-monotone submodular functions and monotone subadditive functions. Even though constrained maximization problems of monotone submodular functions have been extensively studied, little is known about greedy maximization of non-monotone submodular functions or monotone subadditive functions. We give approximation guarantees for GREEDY on these problems, in terms of the curvature. We find that this simple heuristic yields a strong approximation guarantee on a broad class of functions. We discuss the applicability of our results to three real-world problems: Maximizing the determinant function of a positive semidefinite matrix, and related problems such as the maximum entropy sampling problem, the constrained maximum cut problem on directed graphs, and combinatorial auction games. We conclude that GREEDY is well-suited to approach these problems. Overall, we present evidence to support the idea that, when dealing with constrained maximization problems with bounded curvature, one needs not search for (approximate) monotonicity to get good approximate solutions.}, author = {Friedrich, Tobias and Göbel, Andreas and Neumann, Frank and Quinzan, Francesco and Rothenberger, Ralf}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {year2019 andreasgoebel francescoquinzan tobiasfriedrich aaai frankneumann ralfrothenberger}, pages = {2272-2279}, title = {Greedy Maximization of Functions with Bounded Curvature Under Partition Matroid Constraints}, year = 2019 }
• 
  Roostapour, Vahid; Neumann, Aneta; Neumann, Frank; Friedrich, TobiasPareto Optimization for Subset Selection with Dynamic Cost Constraints. Conference on Artificial Intelligence (AAAI) 2019: 2354-2361
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  In this paper, we consider subset selection problems for functions \(f\) with constraints where the constraint bound \(B\) changes over time. We point out that adaptive variants of greedy approaches commonly used in the area of submodular optimization are not able to maintain their approximation quality. Investigating the recently introduced POMC Pareto optimization approach, we show that this algorithm efficiently computes a \( phi= (\alpha_f/2)(1-\frac{1}{e^{\alpha_f}})\)-approximation, where \(\alpha_f\) is the submodularity ratio, for each possible constraint bound \(b \leq B\). Furthermore, we show that POMC is able to adapt its set of solutions quickly in the case that \(B\) increases. Our experimental investigations for the influence maximization in social networks show the advantage of POMC over generalized greedy algorithms.
  @inproceedings{AAAI19b, abstract = {In this paper, we consider subset selection problems for functions \(f\) with constraints where the constraint bound \(B\) changes over time. We point out that adaptive variants of greedy approaches commonly used in the area of submodular optimization are not able to maintain their approximation quality. Investigating the recently introduced POMC Pareto optimization approach, we show that this algorithm efficiently computes a \( \phi= (\alpha_f/2)(1-\frac{1}{e^{\alpha_f}})\)-approximation, where \(\alpha_f\) is the submodularity ratio, for each possible constraint bound \(b \leq B\). Furthermore, we show that POMC is able to adapt its set of solutions quickly in the case that \(B\) increases. Our experimental investigations for the influence maximization in social networks show the advantage of POMC over generalized greedy algorithms.}, author = {Roostapour, Vahid and Neumann, Aneta and Neumann, Frank and Friedrich, Tobias}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {anetaneumann year2019 vahidroostapour tobiasfriedrich aaai frankneumann}, pages = {2354-2361}, title = {Pareto Optimization for Subset Selection with Dynamic Cost Constraints}, year = 2019 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Lischeid, Julius; Meeks, Kitty; Schirneck, MartinEfficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling. Algorithm Engineering and Experiments (ALENEX) 2019: 130-143
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We devise an enumeration method for inclusion-wise minimal hitting sets in hypergraphs. It has delay \(O(m^{k^\ast+1} \cdot n^2)\) and uses linear space. Hereby, \(n\) is the number of vertices, \(m\) the number of hyperedges, and \(k^\ast\) the rank of the transversal hypergraph. In particular, on classes of hypergraphs for which the cardinality \(k^\ast\) of the largest minimal hitting set is bounded, the delay is polynomial. The algorithm solves the extension problem for minimal hitting sets as a subroutine. We show that the extension problem is W[3]-complete when parameterised by the cardinality of the set which is to be extended. For the subroutine, we give an algorithm that is optimal under the exponential time hypothesis. Despite these lower bounds, we provide empirical evidence showing that the enumeration outperforms the theoretical worst-case guarantee on hypergraphs arising in the profiling of relational databases, namely, in the detection of unique column combinations.
  @inproceedings{blasius2019efficiently, abstract = {We devise an enumeration method for inclusion-wise minimal hitting sets in hypergraphs. It has delay \(O(m^{k^\ast+1} \cdot n^2)\) and uses linear space. Hereby, \(n\) is the number of vertices, \(m\) the number of hyperedges, and \(k^\ast\) the rank of the transversal hypergraph. In particular, on classes of hypergraphs for which the cardinality \(k^\ast\) of the largest minimal hitting set is bounded, the delay is polynomial. The algorithm solves the extension problem for minimal hitting sets as a subroutine. We show that the extension problem is W[3]-complete when parameterised by the cardinality of the set which is to be extended. For the subroutine, we give an algorithm that is optimal under the exponential time hypothesis. Despite these lower bounds, we provide empirical evidence showing that the enumeration outperforms the theoretical worst-case guarantee on hypergraphs arising in the profiling of relational databases, namely, in the detection of unique column combinations.}, author = {Bläsius, Thomas and Friedrich, Tobias and Lischeid, Julius and Meeks, Kitty and Schirneck, Martin}, booktitle = {Algorithm Engineering and Experiments (ALENEX)}, keywords = {alenex kittymeeks thomasblaesius year2019 juliuslischeid tobiasfriedrich martinschirneck}, pages = {130-143}, title = {Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling}, year = 2019 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Meyer, Ulrich; Penschuck, Manuel; Weyand, ChristopherEfficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs. European Symposium on Algorithms (ESA) 2019: 21:2-21:14

  EATCS Best Paper Award
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Hyperbolic random graphs (HRG) and geometric inhomogeneous random graphs (GIRG) are two similar generative network models that were designed to resemble complex real world networks. In particular, they have a power-law degree distribution with controllable exponent \(\beta\), and high clustering that can be controlled via the temperature \(T\). We present the first implementation of an efficient GIRG generator running in expected linear time. Besides varying temperatures, it also supports underlying geometries of higher dimensions. It is capable of generating graphs with ten million edges in under a second on commodity hardware. The algorithm can be adapted to HRGs. Our resulting implementation is the fastest sequential HRG generator, despite the fact that we support non-zero temperatures. Though non-zero temperatures are crucial for many applications, most existing generators are restricted to \(T = 0\). We also support parallelization, although this is not the focus of this paper. Moreover, we note that our generators draw from the correct probability distribution, i.e., they involve no approximation. Besides the generators themselves, we also provide an efficient algorithm to determine the non-trivial dependency between the average degree of the resulting graph and the input parameters of the GIRG model. This makes it possible to specify \(\bar{d}\) as input and obtain a graph with expected average degree \(\bar{d}\). Moreover, we investigate the differences between HRGs and GIRGs, shedding new light on the nature of the relation between the two models. Although HRGs represent, in a certain sense, a special case of the GIRG model, we find that a straight-forward inclusion does not hold in practice. However, the difference is negligible for most use cases.
  @inproceedings{blaesius2019efficiently, abstract = {Hyperbolic random graphs (HRG) and geometric inhomogeneous random graphs (GIRG) are two similar generative network models that were designed to resemble complex real world networks. In particular, they have a power-law degree distribution with controllable exponent \(\beta\), and high clustering that can be controlled via the temperature \(T\). We present the first implementation of an efficient GIRG generator running in expected linear time. Besides varying temperatures, it also supports underlying geometries of higher dimensions. It is capable of generating graphs with ten million edges in under a second on commodity hardware. The algorithm can be adapted to HRGs. Our resulting implementation is the fastest sequential HRG generator, despite the fact that we support non-zero temperatures. Though non-zero temperatures are crucial for many applications, most existing generators are restricted to \(T = 0\). We also support parallelization, although this is not the focus of this paper. Moreover, we note that our generators draw from the correct probability distribution, i.e., they involve no approximation. Besides the generators themselves, we also provide an efficient algorithm to determine the non-trivial dependency between the average degree of the resulting graph and the input parameters of the GIRG model. This makes it possible to specify \(\bar{d}\) as input and obtain a graph with expected average degree \(\bar{d}\). Moreover, we investigate the differences between HRGs and GIRGs, shedding new light on the nature of the relation between the two models. Although HRGs represent, in a certain sense, a special case of the GIRG model, we find that a straight-forward inclusion does not hold in practice. However, the difference is negligible for most use cases.}, author = {Bläsius, Thomas and Friedrich, Tobias and Katzmann, Maximilian and Meyer, Ulrich and Penschuck, Manuel and Weyand, Christopher}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {esa manuelpenschuck thomasblaesius year2019 tobiasfriedrich christopherweyand hyperbolic_generation maximiliankatzmann ulrichmeyer}, note = {EATCS Best Paper Award}, pages = {21:2-21:14}, title = {Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs}, year = 2019 }
• 
  Friedrich, Tobias; Rothenberger, RalfThe Satisfiability Threshold for Non-Uniform Random 2-SAT. International Colloquium on Automata, Languages and Programming (ICALP) 2019: 61:1-61:14
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. Its worst-case hardness lies at the core of computational complexity theory, for example in the form of NP-hardness and the (Strong) Exponential Time Hypothesis. In practice however, SAT instances can often be solved efficiently. This contradicting behavior has spawned interest in the average-case analysis of SAT and has triggered the development of sophisticated rigorous and non-rigorous techniques for analyzing random structures. Despite a long line of research and substantial progress, most theoretical work on random SAT assumes a uniform distribution on the variables. In contrast, real-world instances often exhibit large fluctuations in variable occurrence. This can be modeled by a non-uniform distribution of the variables, which can result in distributions closer to industrial SAT instances. We study satisfiability thresholds of non-uniform random 2-SAT with n variables and m clauses and with an arbitrary probability distribution \((p_i)_{i \in [n]}\) with \(p_1 \ge p_2 \ge \dots \ge p_n > 0\) over the n variables. We show for \(p_1^2 = \Theta(\sum_{i=1^n p_i^2)\) that the asymptotic satisfiability threshold is at \(m = \Theta((1− \sum_{i=1^n p_i^2) / \)\((p_1 (\sum_{i=2^n p_i^2)^{1/2}))\) and that it is coarse. For \(p_1^2 = o( \sum_{i=1^n p_i^2)\) we show that there is a sharp satisfiability threshold at \(m = (\sum_{i=1^n p_i^2)^{−1}\). This result generalizes the seminal works by Chvatal and Reed [FOCS 1992] and by Goerdt [JCSS 1996].
  @inproceedings{friedrich2019satisfiabilityICALP, abstract = {Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. Its worst-case hardness lies at the core of computational complexity theory, for example in the form of NP-hardness and the (Strong) Exponential Time Hypothesis. In practice however, SAT instances can often be solved efficiently. This contradicting behavior has spawned interest in the average-case analysis of SAT and has triggered the development of sophisticated rigorous and non-rigorous techniques for analyzing random structures. Despite a long line of research and substantial progress, most theoretical work on random SAT assumes a uniform distribution on the variables. In contrast, real-world instances often exhibit large fluctuations in variable occurrence. This can be modeled by a non-uniform distribution of the variables, which can result in distributions closer to industrial SAT instances. We study satisfiability thresholds of non-uniform random 2-SAT with n variables and m clauses and with an arbitrary probability distribution \((p_i)_{i \in [n]}\) with \(p_1 \ge p_2 \ge \dots \ge p_n > 0\) over the n variables. We show for \(p_1^2 = \Theta(\sum_{i=1}^n p_i^2)\) that the asymptotic satisfiability threshold is at \(m = \Theta((1− \sum_{i=1}^n p_i^2) / \)\((p_1 (\sum_{i=2}^n p_i^2)^{1/2}))\) and that it is coarse. For \(p_1^2 = o( \sum_{i=1}^n p_i^2)\) we show that there is a sharp satisfiability threshold at \(m = (\sum_{i=1}^n p_i^2)^{−1}\). This result generalizes the seminal works by Chvatal and Reed [FOCS 1992] and by Goerdt [JCSS 1996].}, author = {Friedrich, Tobias and Rothenberger, Ralf}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {year2019 tobiasfriedrich scalefree_sat icalp ralfrothenberger}, pages = {61:1-61:14}, title = {The Satisfiability Threshold for Non-Uniform Random 2-SAT}, year = 2019 }
• 
  Peters, Jannik; Stephan, Daniel; Amon, Isabel; Gawendowicz, Hans; Lischeid, Julius; Salabarria, Julius; Umland, Jonas; Werner, Felix; Krejca, Martin S.; Rothenberger, Ralf; Kötzing, Timo; Friedrich, TobiasMixed Integer Programming versus Evolutionary Computation for Optimizing a Hard Real-World Staff Assignment Problem. International Conference on Automated Planning and Scheduling (ICAPS) 2019: 541-554
  [ Abstract ] [ BibTeX ] [ URL ] [ Download ]
   
  Assigning staff to engagements according to hard constraints while optimizing several objectives is a task encountered by many companies on a regular basis. Simplified versions of such assignment problems are NP-hard. Despite this, a typical approach to solving them consists of formulating them as mixed integer programming (MIP) problems and using a state-of-the-art solver to get solutions that closely approximate the optimum. In this paper, we consider a complex real-world staff assignment problem encountered by the professional service company KPMG, with the goal of finding an algorithm that solves it faster and with a better solution than a commercial MIP solver. We follow the evolutionary algorithm (EA) metaheuristic and design a search heuristic which iteratively improves a solution using domain-specific mutation operators. Furthermore, we use a flow algorithm to optimally solve a subproblem, which tremendously reduces the search space for the EA. For our real-world instance of the assignment problem, given the same total time budget of \(100\) hours, a parallel EA approach finds a solution that is only \(1.7\)% away from an upper bound for the (unknown) optimum within under five hours, while the MIP solver Gurobi still has a gap of \(10.5\) %.
  @inproceedings{peters2019mixed, abstract = {Assigning staff to engagements according to hard constraints while optimizing several objectives is a task encountered by many companies on a regular basis. Simplified versions of such assignment problems are NP-hard. Despite this, a typical approach to solving them consists of formulating them as mixed integer programming (MIP) problems and using a state-of-the-art solver to get solutions that closely approximate the optimum. In this paper, we consider a complex real-world staff assignment problem encountered by the professional service company KPMG, with the goal of finding an algorithm that solves it faster and with a better solution than a commercial MIP solver. We follow the evolutionary algorithm (EA) metaheuristic and design a search heuristic which iteratively improves a solution using domain-specific mutation operators. Furthermore, we use a flow algorithm to optimally solve a subproblem, which tremendously reduces the search space for the EA. For our real-world instance of the assignment problem, given the same total time budget of \(100\) hours, a parallel EA approach finds a solution that is only \(1.7\)\% away from an upper bound for the (unknown) optimum within under five hours, while the MIP solver Gurobi still has a gap of \(10.5\) \%.}, author = {Peters, Jannik and Stephan, Daniel and Amon, Isabel and Gawendowicz, Hans and Lischeid, Julius and Salabarria, Julius and Umland, Jonas and Werner, Felix and Krejca, Martin S. and Rothenberger, Ralf and Kötzing, Timo and Friedrich, Tobias}, booktitle = {International Conference on Automated Planning and Scheduling (ICAPS)}, keywords = {year2019 martinskrejca felixwerner tobiasfriedrich danielstephan hansgawendowicz jonasumland timokoetzing isabelamon lennartsalabarria jannikpeters juliuslischeid ralfrothenberger icaps}, pages = {541-554}, title = {Mixed Integer Programming versus Evolutionary Computation for Optimizing a Hard Real-World Staff Assignment Problem}, year = 2019 }
• 
  Friedrich, Tobias; Rothenberger, RalfSharpness of the Satisfiability Threshold for Non-Uniform Random \(k\)-SAT.International Joint Conference on Artificial Intelligence (IJCAI) 2019: 6151-6155
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We study non-uniform random k-SAT on n variables with an arbitrary probability distribution p on the variable occurrences. The number \(t = t(n)\) of randomly drawn clauses at which random formulas go from asymptotically almost surely (a.a.s.) satisfiable to a.a.s. unsatisfiable is called the satisfiability threshold. Such a threshold is called sharp if it approaches a step function as n increases. We show that a threshold t(n) for random k-SAT with an ensemble \((p_n)_{n\in\mathbb{N}}\) of arbitrary probability distributions on the variable occurrences is sharp if \(\|p\|_2^2 = O_n(t^{-2/k})\) and \(\|p\|_\infty\) \(= o_n(t^-k/(2k-1) \log^{-(k-1)/(2k-1)(t))\). This result generalizes Friedgut’s sharpness result from uniform to non-uniform random k-SAT and implies sharpness for thresholds of a wide range of random k-SAT models with heterogeneous probability distributions, for example such models where the variable probabilities follow a power-law distribution.
  @inproceedings{friedrich2019satisfiabilityIJCAI, abstract = {We study non-uniform random k-SAT on n variables with an arbitrary probability distribution p on the variable occurrences. The number \(t = t(n)\) of randomly drawn clauses at which random formulas go from asymptotically almost surely (a.a.s.) satisfiable to a.a.s. unsatisfiable is called the satisfiability threshold. Such a threshold is called sharp if it approaches a step function as n increases. We show that a threshold t(n) for random k-SAT with an ensemble \((p_n)_{n\in\mathbb{N}}\) of arbitrary probability distributions on the variable occurrences is sharp if \(\|p\|_2^2 = O_n(t^{-2/k})\) and \(\|p\|_\infty\) \(= o_n(t^{-k/(2k-1)} \log^{-(k-1)/(2k-1)}(t))\). This result generalizes Friedgut’s sharpness result from uniform to non-uniform random k-SAT and implies sharpness for thresholds of a wide range of random k-SAT models with heterogeneous probability distributions, for example such models where the variable probabilities follow a power-law distribution.}, author = {Friedrich, Tobias and Rothenberger, Ralf}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {ijcai year2019 tobiasfriedrich scalefree_sat ralfrothenberger}, pages = {6151-6155}, title = {Sharpness of the Satisfiability Threshold for Non-Uniform Random \(k\)-SAT.}, year = 2019 }
• 
  Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, AnnaGeometric Network Creation Games. Symposium on Parallelism in Algorithms and Architectures (SPAA) 2019: 323-332
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Network Creation Games are a well-known approach for explaining and analyzing the structure, quality and dynamics of real-world networks like the Internet and other infrastructure networks which evolved via the interaction of selfish agents without a central authority. In these games selfish agents which correspond to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games has only considered the creation of networks with unit-weight edges. In practice, e.g. when constructing a fiber-optic network, the choice of which nodes to connect and also the induced price for a link crucially depends on the distance between the involved nodes and such settings can be modeled via edge-weighted graphs. We incorporate arbitrary edge weights by generalizing the well-known model by Fabrikant et al.~[PODC'03] to edge-weighted host graphs and focus on the geometric setting where the weights are induced by the distances in some metric space. In stark contrast to the state-of-the-art for the unit-weight version, where the Price of Anarchy is conjectured to be constant and where resolving this is a major open problem, we prove a tight non-constant bound on the Price of Anarchy for the metric version and a slightly weaker upper bound for the non-metric case. Moreover, we analyze the existence of equilibria, the computational hardness and the game dynamics for several natural metrics. The model we propose can be seen as the game-theoretic analogue of a variant of the classical Network Design Problem. Thus, low-cost equilibria of our game correspond to decentralized and stable approximations of the optimum network design.
  @inproceedings{bil2019geometric, abstract = {Network Creation Games are a well-known approach for explaining and analyzing the structure, quality and dynamics of real-world networks like the Internet and other infrastructure networks which evolved via the interaction of selfish agents without a central authority. In these games selfish agents which correspond to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games has only considered the creation of networks with unit-weight edges. In practice, e.g. when constructing a fiber-optic network, the choice of which nodes to connect and also the induced price for a link crucially depends on the distance between the involved nodes and such settings can be modeled via edge-weighted graphs. We incorporate arbitrary edge weights by generalizing the well-known model by Fabrikant et al.&nbsp;[PODC'03] to edge-weighted host graphs and focus on the geometric setting where the weights are induced by the distances in some metric space. In stark contrast to the state-of-the-art for the unit-weight version, where the Price of Anarchy is conjectured to be constant and where resolving this is a major open problem, we prove a tight non-constant bound on the Price of Anarchy for the metric version and a slightly weaker upper bound for the non-metric case. Moreover, we analyze the existence of equilibria, the computational hardness and the game dynamics for several natural metrics. The model we propose can be seen as the game-theoretic analogue of a variant of the classical Network Design Problem. Thus, low-cost equilibria of our game correspond to decentralized and stable approximations of the optimum network design.}, author = {Bilò, Davide and Friedrich, Tobias and Lenzner, Pascal and Melnichenko, Anna}, booktitle = {Symposium on Parallelism in Algorithms and Architectures (SPAA)}, keywords = {davidebilo year2019 spaa tobiasfriedrich annamelnichenko pascallenzner}, pages = {323-332}, title = {Geometric Network Creation Games}, year = 2019 }
• 
  Friedrich, TobiasFrom Graph Theory to Network Science: The Natural Emergence of Hyperbolicity. Symposium Theoretical Aspects of Computer Science (STACS) 2019: 5:1–5:9
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Network science is driven by the question which properties large real-world networks have and how we can exploit them algorithmically. In the past few years, hyperbolic graphs have emerged as a very promising model for scale-free networks. The connection between hyperbolic geometry and complex networks gives insights in both directions: (1) Hyperbolic geometry forms the basis of a natural and explanatory model for real-world networks. Hyperbolic random graphs are obtained by choosing random points in the hyperbolic plane and connecting pairs of points that are geometrically close. The resulting networks share many structural properties for example with online social networks like Facebook or Twitter. They are thus well suited for algorithmic analyses in a more realistic setting. (2) Starting with a real-world network, hyperbolic geometry is well-suited for metric embeddings. The vertices of a network can be mapped to points in this geometry, such that geometric distances are similar to graph distances. Such embeddings have a variety of algorithmic applications ranging from approximations based on efficient geometric algorithms to greedy routing solely using hyperbolic coordinates for navigation decisions.
  @inproceedings{friedrich2019graph, abstract = {Network science is driven by the question which properties large real-world networks have and how we can exploit them algorithmically. In the past few years, hyperbolic graphs have emerged as a very promising model for scale-free networks. The connection between hyperbolic geometry and complex networks gives insights in both directions: (1) Hyperbolic geometry forms the basis of a natural and explanatory model for real-world networks. Hyperbolic random graphs are obtained by choosing random points in the hyperbolic plane and connecting pairs of points that are geometrically close. The resulting networks share many structural properties for example with online social networks like Facebook or Twitter. They are thus well suited for algorithmic analyses in a more realistic setting. (2) Starting with a real-world network, hyperbolic geometry is well-suited for metric embeddings. The vertices of a network can be mapped to points in this geometry, such that geometric distances are similar to graph distances. Such embeddings have a variety of algorithmic applications ranging from approximations based on efficient geometric algorithms to greedy routing solely using hyperbolic coordinates for navigation decisions.}, author = {Friedrich, Tobias}, booktitle = {Symposium Theoretical Aspects of Computer Science (STACS)}, keywords = {year2019 stacs tobiasfriedrich}, pages = {5:1–5:9}, title = {From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity}, year = 2019 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Sutton, Andrew M.On the Empirical Time Complexity of Scale-Free 3-SAT at the Phase Transition. Tools and Algorithms for the Construction and Analysis of Systems (TACAS) 2019: 117-134
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  The hardness of formulas at the solubility phase transition of random propositional satisfiability (SAT) has been intensely studied for decades both empirically and theoretically. Solvers based on stochastic local search (SLS) appear to scale very well at the critical threshold, while complete backtracking solvers exhibit exponential scaling. On industrial SAT instances, this phenomenon is inverted: backtracking solvers can tackle large industrial problems, where SLS-based solvers appear to stall. Industrial instances exhibit sharply different structure than uniform random instances. Among many other properties, they are often heterogeneous in the sense that some variables appear in many while others appear in only few clauses. We conjecture that the heterogeneity of SAT formulas alone already contributes to the trade-off in performance between SLS solvers and complete backtracking solvers. We empirically determine how the run time of SLS vs. backtracking solvers depends on the heterogeneity of the input, which is controlled by drawing variables according to a scale-free distribution. Our experiments reveal that the efficiency of complete solvers at the phase transition is strongly related to the heterogeneity of the degree distribution. We report results that suggest the depth of satisfying assignments in complete search trees is influenced by the level of heterogeneity as measured by a power-law exponent. We also find that incomplete SLS solvers, which scale well on uniform instances, are not affected by heterogeneity. The main contribution of this paper utilizes the scale-free random 3-SAT model to isolate heterogeneity as an important factor in the scaling discrepancy between complete and SLS solvers at the uniform phase transition found in previous works.
  @inproceedings{blasius2019empirical, abstract = {The hardness of formulas at the solubility phase transition of random propositional satisfiability (SAT) has been intensely studied for decades both empirically and theoretically. Solvers based on stochastic local search (SLS) appear to scale very well at the critical threshold, while complete backtracking solvers exhibit exponential scaling. On industrial SAT instances, this phenomenon is inverted: backtracking solvers can tackle large industrial problems, where SLS-based solvers appear to stall. Industrial instances exhibit sharply different structure than uniform random instances. Among many other properties, they are often heterogeneous in the sense that some variables appear in many while others appear in only few clauses. We conjecture that the heterogeneity of SAT formulas alone already contributes to the trade-off in performance between SLS solvers and complete backtracking solvers. We empirically determine how the run time of SLS vs. backtracking solvers depends on the heterogeneity of the input, which is controlled by drawing variables according to a scale-free distribution. Our experiments reveal that the efficiency of complete solvers at the phase transition is strongly related to the heterogeneity of the degree distribution. We report results that suggest the depth of satisfying assignments in complete search trees is influenced by the level of heterogeneity as measured by a power-law exponent. We also find that incomplete SLS solvers, which scale well on uniform instances, are not affected by heterogeneity. The main contribution of this paper utilizes the scale-free random 3-SAT model to isolate heterogeneity as an important factor in the scaling discrepancy between complete and SLS solvers at the uniform phase transition found in previous works.}, author = {Bläsius, Thomas and Friedrich, Tobias and Sutton, Andrew M.}, booktitle = {Tools and Algorithms for the Construction and Analysis of Systems (TACAS)}, keywords = {thomasblaesius year2019 tacas tobiasfriedrich scalefree_sat andrewmsutton}, pages = {117-134}, title = {On the Empirical Time Complexity of Scale-Free 3-SAT at the Phase Transition}, year = 2019 }
• 
  Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Schirneck, MartinUnderstanding the Effectiveness of Data Reduction in Public Transportation Networks. Workshop on Algorithms and Models for the Web Graph (WAW) 2019: 87-101
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Given a public transportation network of stations and connections, we want to find a minimum subset of stations such that each connection runs through a selected station. Although this problem is NP-hard in general, real-world instances are regularly solved almost completely by a set of simple reduction rules. To explain this behavior, we view transportation networks as hitting set instances and identify two characteristic properties, locality and heterogeneity. We then devise a randomized model to generate hitting set instances with adjustable properties. While the heterogeneity does influence the effectiveness of the reduction rules, the generated instances show that locality is the significant factor. Beyond that, we prove that the effectiveness of the reduction rules is independent of the underlying graph structure. Finally, we show that high locality is also prevalent in instances from other domains, facilitating a fast computation of minimum hitting sets.
  @inproceedings{blasius2019understanding, abstract = {Given a public transportation network of stations and connections, we want to find a minimum subset of stations such that each connection runs through a selected station. Although this problem is NP-hard in general, real-world instances are regularly solved almost completely by a set of simple reduction rules. To explain this behavior, we view transportation networks as hitting set instances and identify two characteristic properties, locality and heterogeneity. We then devise a randomized model to generate hitting set instances with adjustable properties. While the heterogeneity does influence the effectiveness of the reduction rules, the generated instances show that locality is the significant factor. Beyond that, we prove that the effectiveness of the reduction rules is independent of the underlying graph structure. Finally, we show that high locality is also prevalent in instances from other domains, facilitating a fast computation of minimum hitting sets.}, author = {Bläsius, Thomas and Fischbeck, Philipp and Friedrich, Tobias and Schirneck, Martin}, booktitle = {Workshop on Algorithms and Models for the Web Graph (WAW)}, keywords = {philippfischbeck thomasblaesius year2019 tobiasfriedrich waw martinschirneck}, pages = {87-101}, title = {Understanding the Effectiveness of Data Reduction in Public Transportation Networks}, year = 2019 }
• 
  Echzell, Hagen; Friedrich, Tobias; Lenzner, Pascal; Molitor, Louise; Pappik, Marcus; Schöne, Friedrich; Sommer, Fabian; Stangl, DavidConvergence and Hardness of Strategic Schelling Segregation. Web and Internet Economics (WINE) 2019: 156-170
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  The phenomenon of residential segregation was captured by Schelling's famous segregation model where two types of agents are placed on a grid and an agent is content with her location if the fraction of her neighbors which have the same type as her is at least \(\tau\), for some \(0<\tau<1\). Discontent agents simply swap their location with a randomly chosen other discontent agent or jump to a random empty cell. We analyze a generalized game-theoretic model of Schelling segregation which allows more than two agent types and more general underlying graphs modeling the residential area. For this we show that both aspects heavily influence the dynamic properties and the tractability of finding an optimal placement. We map the boundary of when improving response dynamics (IRD), i.e., the natural approach for finding equilibrium states, are guaranteed to converge. For this we prove several sharp threshold results where guaranteed IRD convergence suddenly turns into the strongest possible non-convergence result: a violation of weak acyclicity. In particular, we show such threshold results also for Schelling's original model, which is in contrast to the standard assumption in many empirical papers. Furthermore, we show that in case of convergence, IRD find an equilibrium in \(O(m)\) steps, where \(m\) is the number of edges in the underlying graph and show that this bound is met in empirical simulations starting from random initial agent placements.
  @inproceedings{echzell2019convergence, abstract = {The phenomenon of residential segregation was captured by Schelling's famous segregation model where two types of agents are placed on a grid and an agent is content with her location if the fraction of her neighbors which have the same type as her is at least \(\tau\), for some \(0<\tau<1\). Discontent agents simply swap their location with a randomly chosen other discontent agent or jump to a random empty cell. We analyze a generalized game-theoretic model of Schelling segregation which allows more than two agent types and more general underlying graphs modeling the residential area. For this we show that both aspects heavily influence the dynamic properties and the tractability of finding an optimal placement. We map the boundary of when improving response dynamics (IRD), i.e., the natural approach for finding equilibrium states, are guaranteed to converge. For this we prove several sharp threshold results where guaranteed IRD convergence suddenly turns into the strongest possible non-convergence result: a violation of weak acyclicity. In particular, we show such threshold results also for Schelling's original model, which is in contrast to the standard assumption in many empirical papers. Furthermore, we show that in case of convergence, IRD find an equilibrium in \(O(m)\) steps, where \(m\) is the number of edges in the underlying graph and show that this bound is met in empirical simulations starting from random initial agent placements.}, author = {Echzell, Hagen and Friedrich, Tobias and Lenzner, Pascal and Molitor, Louise and Pappik, Marcus and Schöne, Friedrich and Sommer, Fabian and Stangl, David}, booktitle = {Web and Internet Economics (WINE)}, keywords = {marcuspappik louisemolitor year2019 tobiasfriedrich pascallenzner wine}, pages = {156-170}, title = {Convergence and Hardness of Strategic Schelling Segregation}, year = 2019 }
• 
  FOGA ’19: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms. 2019ACM.

  Editorship
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
   
  The FOGA workshop series aims at advancing our understanding of the working principles behind evolutionary algorithms and related randomized search heuristics. FOGA is the premier event to discuss advances in the theoretical foundations of these algorithms, tools needed to analyze them, and different aspects of comparing algorithms' performance. FOGA XV has welcomed submissions covering the entire spectrum of work, ranging from rigorously derived mathematical results to carefully crafted empirical studies.
  @proceedings{DBLP:conf/foga/2019, abstract = {The FOGA workshop series aims at advancing our understanding of the working principles behind evolutionary algorithms and related randomized search heuristics. FOGA is the premier event to discuss advances in the theoretical foundations of these algorithms, tools needed to analyze them, and different aspects of comparing algorithms' performance. FOGA XV has welcomed submissions covering the entire spectrum of work, ranging from rigorously derived mathematical results to carefully crafted empirical studies.}, editor = {Friedrich, Tobias and Doerr, Carola and Arnold, Dirk V.}, keywords = {caroladoerr foga2019 dirkarnold tobiasfriedrich}, note = {Editorship}, publisher = {ACM}, title = {FOGA ’19: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms}, year = 2019 }
• 
  Theory of Randomized Optimization Heuristics. Dagstuhl Reports 2019: 61-94
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
   
  This report documents the activities of Dagstuhl Seminar 19431 on Theory of Randomized Optimization Heuristics. 46 researchers from Europe, Australia, Asia, and North America have come together to discuss ongoing research. This tenth edition of the seminar series had three focus topics: (1) relation between optimal control and heuristic optimization, (2) benchmarking optimization heuristics, and (3) the interfaces between continuous and discrete optimization. Several breakout sessions have provided ample opportunity to brainstorm on recent developments in the research landscape, to discuss and solve open problems, and to kick-start new research initiatives.
  @proceedings{DBLP:journals/dagstuhl-reports/DoerrFFY19, abstract = {This report documents the activities of Dagstuhl Seminar 19431 on Theory of Randomized Optimization Heuristics. 46 researchers from Europe, Australia, Asia, and North America have come together to discuss ongoing research. This tenth edition of the seminar series had three focus topics: (1) relation between optimal control and heuristic optimization, (2) benchmarking optimization heuristics, and (3) the interfaces between continuous and discrete optimization. Several breakout sessions have provided ample opportunity to brainstorm on recent developments in the research landscape, to discuss and solve open problems, and to kick-start new research initiatives.}, editor = {Doerr, Carola and Fonseca, Carlos M. and Friedrich, Tobias and Yao, Xin}, journal = {Dagstuhl Reports}, keywords = {year2019 tobiasfriedrich}, number = 10, pages = {61-94}, title = {Theory of Randomized Optimization Heuristics}, volume = 9, year = 2019 }

2018 [ nach oben ]

• 
  Bläsius, Thomas; Friedrich, Tobias; Krohmer, AntonCliques in Hyperbolic Random Graphs. Algorithmica 2018: 2324-2344
  [ 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 Krioukov et al. 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 \geq 3\) 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 n^{2.5})\) for all values of \(\beta\).
  @article{journals/algorithmica/Blasius0K18, 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 Krioukov et al. 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 \geq 3\) 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 n^{2.5})\) for all values of \(\beta\).}, author = {Bläsius, Thomas and Friedrich, Tobias and Krohmer, Anton}, journal = {Algorithmica}, keywords = {algorithmica thomasblaesius year2018 tobiasfriedrich antonkrohmer hyperbolic_analysis}, pages = {2324-2344}, title = {Cliques in Hyperbolic Random Graphs}, volume = 80, year = 2018 }
• 
  Bringmann, Karl; Friedrich, Tobias; Krohmer, AntonDe-anonymization of Heterogeneous Random Graphs in Quasilinear Time. Algorithmica 2018: 3397–3427
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  There are hundreds of online social networks with altogether billions of users. 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^\varepsilon\) seed nodes (for an arbitrarily small \(\varepsilon\)) 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.
  @article{DBLP:journals/algorithmica/BringmannFK18, abstract = {There are hundreds of online social networks with altogether billions of users. 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^\varepsilon\) seed nodes (for an arbitrarily small \(\varepsilon\)) 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}, journal = {Algorithmica}, keywords = {tobiasfriedrich antonkrohmer}, number = 11, pages = {3397–3427}, title = {De-anonymization of Heterogeneous Random Graphs in Quasilinear Time}, volume = 80, year = 2018 }
• 
  Friedrich, Tobias; Krohmer, AntonOn the diameter of hyperbolic random graphs. SIAM Journal on Discrete Mathematics 2018: 1314-1334
  [ Abstract ] [ BibTeX ] [ URL ] [ 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 is close to optimal (Boguñá, Papadopoulos, and Krioukov. Nature Communications, 1:62, 2010). This observation has 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 \(\beta\) 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))+1})\)(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)\). If \(\beta > 3\), we show that the latter bound is tight by proving an upper bound of \(O(\log n)\) for the diameter.
  @article{friedrich2018diameter, 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 is close to optimal (Boguñá, Papadopoulos, and Krioukov. Nature Communications, 1:62, 2010). This observation has 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 \(\beta\) 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))+1})\)(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)\). If \(\beta > 3\), we show that the latter bound is tight by proving an upper bound of \(O(\log n)\) for the diameter.}, author = {Friedrich, Tobias and Krohmer, Anton}, journal = {SIAM Journal on Discrete Mathematics}, keywords = {sidma year2018 tobiasfriedrich antonkrohmer hyperbolic_analysis}, number = 2, pages = {1314-1334}, publisher = {SIAM}, title = {On the diameter of hyperbolic random graphs}, volume = 32, year = 2018 }
• 
  Friedrich, Tobias; Katzmann, Maximilian; Krohmer, AntonUnbounded Discrepancy of Deterministic Random Walks on Grids. SIAM Journal on Discrete Mathematics 2018: 2441-2452
  [ Abstract ] [ BibTeX ] [ URL ] [ 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 \(\mathbb{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 \(\mathbb{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\geq1\) and arbitrary discrepancies~\(\ell \geq 0\), we construct configurations that reach a discrepancy of at least \(\ell\).
  @article{friedrich2018unbounded, 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 \(\mathbb{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 \(\mathbb{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\geq1\) and arbitrary discrepancies&nbsp;\(\ell \geq 0\), we construct configurations that reach a discrepancy of at least \(\ell\).}, author = {Friedrich, Tobias and Katzmann, Maximilian and Krohmer, Anton}, journal = {SIAM Journal on Discrete Mathematics}, keywords = {sidma year2018 tobiasfriedrich antonkrohmer maximiliankatzmann}, number = 4, pages = {2441-2452}, publisher = {SIAM}, title = {Unbounded Discrepancy of Deterministic Random Walks on Grids}, volume = 32, year = 2018 }
• 
  Dang, Duc-Cuong; Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Lehre, Per Kristian; Oliveto, Pietro S.; Sudholt, Dirk; Sutton, Andrew M.Escaping Local Optima Using Crossover with Emergent Diversity. Transactions on Evolutionary Computation 2018: 484-497
  [ 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.
  @article{dang2017escaping, 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 Kötzing, Timo and Krejca, Martin S. and Lehre, Per Kristian and Oliveto, Pietro S. and Sudholt, Dirk and Sutton, Andrew M.}, editor = {Tan, Kay Chen}, journal = {Transactions on Evolutionary Computation}, keywords = {martinskrejca timokoetzing year2018 tobiasfriedrich tevoc andrewmsutton}, month = {jun}, number = 3, pages = {484-497}, publisher = {IEEE}, title = {Escaping Local Optima Using Crossover with Emergent Diversity}, volume = 22, year = 2018 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton; Laue, SörenEfficient Embedding of Scale-Free Graphs in the Hyperbolic Plane. Transactions on Networking 2018: 920-933
  [ Abstract ] [ BibTeX ] [ URL ] [ 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 at least a quadratic runtime. 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.
  @article{journals/ton/BlasiusFKL18, 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 at least a quadratic runtime. 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}, journal = {Transactions on Networking}, keywords = {transnetw thomasblaesius year2018 tobiasfriedrich hyperbolic_embedding antonkrohmer}, number = {1-57570FN}, pages = {920-933}, publisher = {IEEE & ACM}, title = {Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane}, volume = 26, year = 2018 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, AntonHyperbolic Embeddings for Near-Optimal Greedy Routing. Algorithm Engineering and Experiments (ALENEX) 2018: 199-208
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Greedy routing computes paths between nodes in a network by successively moving to the neighbor closest to the target with respect to coordinates given by an embedding into some metric space. Its advantage is that only local information is used for routing decisions. We present different algorithms for generating graph embeddings into the hyperbolic plane that are well suited for greedy routing. In particular our embeddings guarantee that greedy routing always succeeds in reaching the target and we try to minimize the lengths of the resulting greedy paths. We evaluate our algorithm on multiple generated and real wold networks. For networks that are generally assumed to have a hidden underlying hyperbolic geometry, such as the Internet graph, we achieve near-optimal results, i.e., the resulting greedy paths are only slightly longer than the corresponding shortest paths. In the case of the Internet graph, they are only \(6\%\) longer when using our best algorithm, which greatly improves upon the previous best known embedding, whose creation required substantial manual intervention.
  @inproceedings{btkk2018hyperbolic, abstract = {Greedy routing computes paths between nodes in a network by successively moving to the neighbor closest to the target with respect to coordinates given by an embedding into some metric space. Its advantage is that only local information is used for routing decisions. We present different algorithms for generating graph embeddings into the hyperbolic plane that are well suited for greedy routing. In particular our embeddings guarantee that greedy routing always succeeds in reaching the target and we try to minimize the lengths of the resulting greedy paths. We evaluate our algorithm on multiple generated and real wold networks. For networks that are generally assumed to have a hidden underlying hyperbolic geometry, such as the Internet graph, we achieve near-optimal results, i.e., the resulting greedy paths are only slightly longer than the corresponding shortest paths. In the case of the Internet graph, they are only \(6\%\) longer when using our best algorithm, which greatly improves upon the previous best known embedding, whose creation required substantial manual intervention.}, author = {Bläsius, Thomas and Friedrich, Tobias and Katzmann, Maximilian and Krohmer, Anton}, booktitle = {Algorithm Engineering and Experiments (ALENEX)}, keywords = {alenex thomasblaesius year2018 tobiasfriedrich hyperbolic_embedding antonkrohmer maximiliankatzmann}, pages = {199-208}, title = {Hyperbolic Embeddings for Near-Optimal Greedy Routing}, year = 2018 }
• 
  Friedrich, Tobias; Quinzan, Francesco; Wagner, MarkusEscaping Large Deceptive Basins of Attraction with Heavy Mutation Operators. Genetic and Evolutionary Computation Conference (GECCO) 2018: 293-300
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  In many Evolutionary Algorithms (EAs), a parameter that needs to be tuned is that of the mutation rate, which determines the probability for each decision variable to be mutated. Typically, this rate is set to 1/n for the duration of the optimization, where n is the number of decision variables. This setting has the appeal that the expected number of mutated variables per iteration is one. In a recent theoretical study, it was proposed to sample the number of mutated variables from a power-law distribution. This results into a significantly higher probability on larger numbers of mutations, so that escaping local optima becomes more probable. In this paper, we propose another class of non-uniform mutation rates. We study the benefits of this operator in terms of average-case black-box complexity analysis and experimental comparison. We consider both pseudo-Boolean artificial landscapes and combinatorial problems (the Minimum Vertex Cover and the Maximum Cut). We observe that our non-uniform mutation rates significantly outperform the standard choices, when dealing with landscapes that exhibit large deceptive basins of attraction.
  @inproceedings{friedrich2018escaping, abstract = {In many Evolutionary Algorithms (EAs), a parameter that needs to be tuned is that of the mutation rate, which determines the probability for each decision variable to be mutated. Typically, this rate is set to 1/n for the duration of the optimization, where n is the number of decision variables. This setting has the appeal that the expected number of mutated variables per iteration is one. In a recent theoretical study, it was proposed to sample the number of mutated variables from a power-law distribution. This results into a significantly higher probability on larger numbers of mutations, so that escaping local optima becomes more probable. In this paper, we propose another class of non-uniform mutation rates. We study the benefits of this operator in terms of average-case black-box complexity analysis and experimental comparison. We consider both pseudo-Boolean artificial landscapes and combinatorial problems (the Minimum Vertex Cover and the Maximum Cut). We observe that our non-uniform mutation rates significantly outperform the standard choices, when dealing with landscapes that exhibit large deceptive basins of attraction.}, author = {Friedrich, Tobias and Quinzan, Francesco and Wagner, Markus}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {markuswagner year2018 GECCO francescoquinzan tobiasfriedrich}, pages = {293-300}, title = {Escaping Large Deceptive Basins of Attraction with Heavy Mutation Operators}, year = 2018 }
• 
  Friedrich, Tobias; Kötzing, Timo; Quinzan, Francesco; Sutton, Andrew M.Improving the Run Time of the (1+1) Evolutionary Algorithm with Luby Sequences. Genetic and Evolutionary Computation Conference (GECCO) 2018: 301-308
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  In the context of black box optimization, the most common way to handle deceptive attractors is to periodically restart the algorithm. In this paper, we explore the benefits of combining the simple \((1+1)\) Evolutionary Algorithm (EA) with the Luby Universal Strategy - the \((1+1)~EA_{\mathcal{U}}\), a meta-heuristic that does not require parameter tuning. We first consider two artificial pseudo-Boolean landscapes, on which the \((1+1)~EA\) exhibits exponential run time. We prove that the \((1+1)~EA_{\mathcal{U}}\) has polynomial run time on both instances. We then consider the Minimum Vertex Cover on two classes of graphs. Again, the \((1+1)~EA\) yields exponential run time on those instances, and the \((1+1)~EA_{\mathcal{U}}\) finds the global optimum in polynomial time. We conclude by studying the Makespan Scheduling. We consider an instance on which the \((1+1)~EA\) does not find a \((4/3-\epsilon)\)-approximation in polynomial time, and we show that the \((1+1)~EA_{\mathcal{U}}\) reaches a \((4/3-\epsilon)\)-approximation in polynomial time. We then prove that the \((1+1)~EA_{\mathcal{U}}\) serves as an Efficient Polynomial-time Approximation Scheme (EPTAS) for the Partition Problem, for a \((1+\epsilon)\)-approximation with \(\epsilon > 4/n\).
  @inproceedings{friedrich2018improving, abstract = {In the context of black box optimization, the most common way to handle deceptive attractors is to periodically restart the algorithm. In this paper, we explore the benefits of combining the simple \((1+1)\) Evolutionary Algorithm (EA) with the Luby Universal Strategy - the \((1+1)&nbsp;EA_{\mathcal{U}}\), a meta-heuristic that does not require parameter tuning. We first consider two artificial pseudo-Boolean landscapes, on which the \((1+1)&nbsp;EA\) exhibits exponential run time. We prove that the \((1+1)&nbsp;EA_{\mathcal{U}}\) has polynomial run time on both instances. We then consider the Minimum Vertex Cover on two classes of graphs. Again, the \((1+1)&nbsp;EA\) yields exponential run time on those instances, and the \((1+1)&nbsp;EA_{\mathcal{U}}\) finds the global optimum in polynomial time. We conclude by studying the Makespan Scheduling. We consider an instance on which the \((1+1)&nbsp;EA\) does not find a \((4/3-\epsilon)\)-approximation in polynomial time, and we show that the \((1+1)&nbsp;EA_{\mathcal{U}}\) reaches a \((4/3-\epsilon)\)-approximation in polynomial time. We then prove that the \((1+1)&nbsp;EA_{\mathcal{U}}\) serves as an Efficient Polynomial-time Approximation Scheme (EPTAS) for the Partition Problem, for a \((1+\epsilon)\)-approximation with \(\epsilon > 4/n\).}, author = {Friedrich, Tobias and Kötzing, Timo and Quinzan, Francesco and Sutton, Andrew M.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {timokoetzing year2018 GECCO francescoquinzan tobiasfriedrich andrewmsutton}, pages = {301-308}, title = {Improving the Run Time of the (1+1) Evolutionary Algorithm with Luby Sequences}, year = 2018 }
• 
  Gao, Wanru; Friedrich, Tobias; Neumann, Frank; Hercher, ChristianRandomized Greedy Algorithms for Covering Problems. Genetic and Evolutionary Computation Conference (GECCO) 2018: 309-315
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Greedy algorithms provide a fast and often also effective solution to many combinatorial optimization problems. However, it is well known that they sometimes lead to low quality solutions on certain instances. In this paper, we explore the use of randomness in greedy algorithms for the minimum vertex cover and dominating set problem and compare the resulting performance against their deterministic counterpart. Our algorithms are based on a parameter \(\gamma\) which allows to explore the spectrum between uniform and deterministic greedy selection in the steps of the algorithm and our theoretical and experimental investigations point out the benefits of incorporating randomness into greedy algorithms for the two considered combinatorial optimization problems.
  @inproceedings{gao2018randomized, abstract = {Greedy algorithms provide a fast and often also effective solution to many combinatorial optimization problems. However, it is well known that they sometimes lead to low quality solutions on certain instances. In this paper, we explore the use of randomness in greedy algorithms for the minimum vertex cover and dominating set problem and compare the resulting performance against their deterministic counterpart. Our algorithms are based on a parameter \(\gamma\) which allows to explore the spectrum between uniform and deterministic greedy selection in the steps of the algorithm and our theoretical and experimental investigations point out the benefits of incorporating randomness into greedy algorithms for the two considered combinatorial optimization problems.}, author = {Gao, Wanru and Friedrich, Tobias and Neumann, Frank and Hercher, Christian}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {year2018 wanrugao GECCO tobiasfriedrich frankneumann christianhercher}, pages = {309-315}, title = {Randomized Greedy Algorithms for Covering Problems}, year = 2018 }
• 
  Bläsius, Thomas; Freiberger, Cedric; Friedrich, Tobias; Katzmann, Maximilian; Montenegro-Retana, Felix; Thieffry, MarianneEfficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry. International Colloquium on Automata, Languages, and Programming (ICALP) 2018: 20:1-20:14
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  A common way to accelerate shortest path algorithms on graphs is the use of a bidirectional search, which simultaneously explores the graph from the start and the destination. It has been observed recently that this strategy performs particularly well on scale-free real-world networks. Such networks typically have a heterogeneous degree distribution (e.g., a power-law distribution) and high clustering (i.e., vertices with a common neighbor are likely to be connected themselves). These two properties can be obtained by assuming an underlying hyperbolic geometry. To explain the observed behavior of the bidirectional search, we analyze its running time on hyperbolic random graphs and prove that it is \(\tilde{O}(n\)\(^{2 - 1/ \alpha}+\)\(n^{1/(2\alpha)}\)\(+ \delta_{\max})\) with high probability, where \(\alpha\)\(\in\)\((0.5, 1)\) controls the power-law exponent of the degree distribution, and \(\delta_{\max}\) is the maximum degree. This bound is sublinear, improving the obvious worst-case linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it.
  @inproceedings{blasius2018efficient, abstract = {A common way to accelerate shortest path algorithms on graphs is the use of a bidirectional search, which simultaneously explores the graph from the start and the destination. It has been observed recently that this strategy performs particularly well on scale-free real-world networks. Such networks typically have a heterogeneous degree distribution (e.g., a power-law distribution) and high clustering (i.e., vertices with a common neighbor are likely to be connected themselves). These two properties can be obtained by assuming an underlying hyperbolic geometry. To explain the observed behavior of the bidirectional search, we analyze its running time on hyperbolic random graphs and prove that it is \(\tilde{O}(n\)\(^{2 - 1/ \alpha}+\)\(n^{1/(2\alpha)}\)\(+ \delta_{\max})\) with high probability, where \(\alpha\)\(\in\)\((0.5, 1)\) controls the power-law exponent of the degree distribution, and \(\delta_{\max}\) is the maximum degree. This bound is sublinear, improving the obvious worst-case linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it.}, author = {Bläsius, Thomas and Freiberger, Cedric and Friedrich, Tobias and Katzmann, Maximilian and Montenegro-Retana, Felix and Thieffry, Marianne}, booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)}, keywords = {thomasblaesius year2018 tobiasfriedrich mariannethieffry cedricfreiberger icalp maximiliankatzmann hyperbolic_analysis felixmontenegroretana}, pages = {20:1-20:14}, title = {Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry}, volume = 107, year = 2018 }
• 
  Friedrich, Tobias; Göbel, Andreas; Quinzan, Francesco; Wagner, MarkusHeavy-tailed Mutation Operators in Single-Objective Combinatorial Optimization. Parallel Problem Solving From Nature (PPSN) 2018: 134-145
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  A core feature of evolutionary algorithms is their mutation operator. Recently, much attention has been devoted to the study of mutation operators with dynamic and non-uniform mutation rates. Following up on this line of work, we propose a new mutation operator and analyze its performance on the (1+1) Evolutionary Algorithm (EA). Our analyses show that this mutation operator competes with pre-existing ones, when used by the (1+1)EA on classes of problems for which results on the other mutation operators are available. We present a jump function for which the performance of the (1+1)EA using any static uniform mutation and any restart strategy can be worse than the performance of the (1+1)EA using our mutation operator with no restarts. We show that the (1+1)EA using our mutation operator finds a (1/3)-approximation ratio on any non-negative submodular function in polynomial time. This performance matches that of combinatorial local search algorithms specifically designed to solve this problem. Finally, we evaluate experimentally the performance of the (1+1)EA using our operator, on real-world graphs of different origins with up to \(\sim\)37,000 vertices and \(\sim\)1.6 million edges. In comparison with uniform mutation and a recently proposed dynamic scheme our operator comes out on top on these instances.
  @inproceedings{friedrich2018heavytailed, abstract = {A core feature of evolutionary algorithms is their mutation operator. Recently, much attention has been devoted to the study of mutation operators with dynamic and non-uniform mutation rates. Following up on this line of work, we propose a new mutation operator and analyze its performance on the (1+1) Evolutionary Algorithm (EA). Our analyses show that this mutation operator competes with pre-existing ones, when used by the (1+1)EA on classes of problems for which results on the other mutation operators are available. We present a jump function for which the performance of the (1+1)EA using any static uniform mutation and any restart strategy can be worse than the performance of the (1+1)EA using our mutation operator with no restarts. We show that the (1+1)EA using our mutation operator finds a (1/3)-approximation ratio on any non-negative submodular function in polynomial time. This performance matches that of combinatorial local search algorithms specifically designed to solve this problem. Finally, we evaluate experimentally the performance of the (1+1)EA using our operator, on real-world graphs of different origins with up to \(\sim\)37\,000 vertices and \(\sim\)1.6 million edges. In comparison with uniform mutation and a recently proposed dynamic scheme our operator comes out on top on these instances.}, author = {Friedrich, Tobias and Göbel, Andreas and Quinzan, Francesco and Wagner, Markus}, booktitle = {Parallel Problem Solving From Nature (PPSN)}, keywords = {markuswagner year2018 andreasgoebel francescoquinzan tobiasfriedrich ppsn}, pages = {134-145}, title = {Heavy-tailed Mutation Operators in Single-Objective Combinatorial Optimization}, year = 2018 }
• 
  Friedrich, Tobias; Rothenberger, RalfSharpness of the Satisfiability Threshold for Non-Uniform Random k-SAT. Theory and Applications of Satisfiability Testing (SAT) 2018: 273-291

  Best Paper Award
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We study non-uniform random k-SAT on n variables with an arbitrary probability distribution p on the variable occurrences. The number \(t = t(n)\) of randomly drawn clauses at which random formulas go from asymptotically almost surely (a.a.s.) satisfiable to a.a.s. unsatisfiable is called the satisfiability threshold. Such a threshold is called sharp if it approaches a step function as n increases. We show that a threshold t(n) for random k-SAT with an ensemble \((p_n)_{n\in\mathbb{N}}\) of arbitrary probability distributions on the variable occurrences is sharp if \(\|p\|_2^2 = O_n(t^{-2/k})\) and \(\|p\|_\infty\) \(= o_n(t^-k/(2k-1) \log^{-(k-1)/(2k-1)(t))\). This result generalizes Friedgut’s sharpness result from uniform to non-uniform random k-SAT and implies sharpness for thresholds of a wide range of random k-SAT models with heterogeneous probability distributions, for example such models where the variable probabilities follow a power-law distribution.
  @inproceedings{friedrich2018sharpness, abstract = {We study non-uniform random k-SAT on n variables with an arbitrary probability distribution p on the variable occurrences. The number \(t = t(n)\) of randomly drawn clauses at which random formulas go from asymptotically almost surely (a.a.s.) satisfiable to a.a.s. unsatisfiable is called the satisfiability threshold. Such a threshold is called sharp if it approaches a step function as n increases. We show that a threshold t(n) for random k-SAT with an ensemble \((p_n)_{n\in\mathbb{N}}\) of arbitrary probability distributions on the variable occurrences is sharp if \(\|p\|_2^2 = O_n(t^{-2/k})\) and \(\|p\|_\infty\) \(= o_n(t^{-k/(2k-1)} \log^{-(k-1)/(2k-1)}(t))\). This result generalizes Friedgut’s sharpness result from uniform to non-uniform random k-SAT and implies sharpness for thresholds of a wide range of random k-SAT models with heterogeneous probability distributions, for example such models where the variable probabilities follow a power-law distribution.}, author = {Friedrich, Tobias and Rothenberger, Ralf}, booktitle = {Theory and Applications of Satisfiability Testing (SAT)}, keywords = {sat year2018 bestpaper tobiasfriedrich scalefree_sat ralfrothenberger}, note = {Best Paper Award}, pages = {273-291}, title = {Sharpness of the Satisfiability Threshold for Non-Uniform Random k-SAT}, year = 2018 }
• 
  Bläsius, Thomas; Eube, Jan; Feldtkeller, Thomas; Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rothenberger, Ralf; Severin, Julius; Sommer, Fabian; Trautmann, JustinMemory-restricted Routing With Tiled Map Data. Systems, Man, and Cybernetics (SMC) 2018: 3347-3354
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Modern routing algorithms reduce query time by depending heavily on preprocessed data. The recently developed Navigation Data Standard (NDS) enforces a separation between algorithms and map data, rendering preprocessing inapplicable. Furthermore, map data is partitioned into tiles with respect to their geographic coordinates. With the limited memory found in portable devices, the number of tiles loaded becomes the major factor for run time. We study routing under these restrictions and present new algorithms as well as empirical evaluations. Our results show that, on average, the most efficient algorithm presented uses more than 20 times fewer tile loads than a normal A*.
  @inproceedings{blasius2018memory, abstract = {Modern routing algorithms reduce query time by depending heavily on preprocessed data. The recently developed Navigation Data Standard (NDS) enforces a separation between algorithms and map data, rendering preprocessing inapplicable. Furthermore, map data is partitioned into tiles with respect to their geographic coordinates. With the limited memory found in portable devices, the number of tiles loaded becomes the major factor for run time. We study routing under these restrictions and present new algorithms as well as empirical evaluations. Our results show that, on average, the most efficient algorithm presented uses more than 20 times fewer tile loads than a normal A*.}, author = {Bläsius, Thomas and Eube, Jan and Feldtkeller, Thomas and Friedrich, Tobias and Krejca, Martin S. and Lagodzinski, J. A. Gregor and Rothenberger, Ralf and Severin, Julius and Sommer, Fabian and Trautmann, Justin}, booktitle = {Systems, Man, and Cybernetics (SMC)}, keywords = {gregorlagodzinski janeube juliusseverin thomasblaesius martinskrejca year2018 thomasfeldtkeller smc tobiasfriedrich justintrautmann fabiansommer ralfrothenberger}, month = 10, pages = {3347-3354}, title = {Memory-restricted Routing With Tiled Map Data}, year = 2018 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton; Striebel, JonathanTowards a Systematic Evaluation of Generative Network Models. Workshop on Algorithms and Models for the Web Graph (WAW) 2018: 99-114
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Generative graph models play an important role in network science. Unlike real-world networks, they are accessible for mathematical analysis and the number of available networks is not limited. The explanatory power of results on generative models, however, heavily depends on how realistic they are. We present a framework that allows for a systematic evaluation of generative network models. It is based on the question whether real-world networks can be distinguished from generated graphs with respect to certain graph parameters. As a proof of concept, we apply our framework to four popular random graph models (Erdős-Rényi, Barabási-Albert, Chung-Lu, and hyperbolic random graphs). Our experiments for example show that all four models are bad representations for Facebook's social networks, while Chung-Lu and hyperbolic random graphs are good representations for other networks, with different strengths and weaknesses.
  @inproceedings{blasius2018towards, abstract = {Generative graph models play an important role in network science. Unlike real-world networks, they are accessible for mathematical analysis and the number of available networks is not limited. The explanatory power of results on generative models, however, heavily depends on how realistic they are. We present a framework that allows for a systematic evaluation of generative network models. It is based on the question whether real-world networks can be distinguished from generated graphs with respect to certain graph parameters. As a proof of concept, we apply our framework to four popular random graph models (Erdős-Rényi, Barabási-Albert, Chung-Lu, and hyperbolic random graphs). Our experiments for example show that all four models are bad representations for Facebook's social networks, while Chung-Lu and hyperbolic random graphs are good representations for other networks, with different strengths and weaknesses.}, author = {Bläsius, Thomas and Friedrich, Tobias and Katzmann, Maximilian and Krohmer, Anton and Striebel, Jonathan}, booktitle = {Workshop on Algorithms and Models for the Web Graph (WAW)}, keywords = {jonathanstriebel thomasblaesius year2018 tobiasfriedrich antonkrohmer maximiliankatzmann waw}, pages = {99-114}, title = {Towards a Systematic Evaluation of Generative Network Models}, year = 2018 }

2017 [ nach oben ]

• 
  Anand, S.; Bringmann, Karl; Friedrich, Tobias; Garg, Naveen; Kumar, AmitMinimizing 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}, keywords = {algorithmica year2017 tobiasfriedrich}, number = 2, pages = {515-536}, title = {Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines}, volume = 77, year = 2017 }
• 
  Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M.The Compact Genetic Algorithm is Efficient under Extreme Gaussian Noise. Transactions on Evolutionary Computation 2017: 477-490
  [ Abstract ] [ BibTeX ] [ 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.
  @article{friedrich2017compact, 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.}, journal = {Transactions on Evolutionary Computation}, keywords = {martinskrejca timokoetzing year2017 tobiasfriedrich tevoc andrewmsutton}, number = 3, pages = {477-490}, publisher = {IEEE}, title = {The Compact Genetic Algorithm is Efficient under Extreme Gaussian Noise}, volume = 21, year = 2017 }
• 
  Friedrich, Tobias; Kötzing, Timo; Wagner, MarkusA Generic Bet-and-Run Strategy for Speeding Up Stochastic Local Search. Conference on 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 = {Conference on Artificial Intelligence (AAAI)}, keywords = {markuswagner timokoetzing year2017 tobiasfriedrich aaai}, pages = {801-807}, title = {A Generic Bet-and-Run Strategy for Speeding Up Stochastic Local Search}, year = 2017 }
• 
  Friedrich, Tobias; Krohmer, Anton; Rothenberger, Ralf; Sutton, Andrew M.Phase Transitions for Scale-Free SAT Formulas. Conference on 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 \geq 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 \geq 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 = {Conference on Artificial Intelligence (AAAI)}, keywords = {year2017 tobiasfriedrich aaai scalefree_sat antonkrohmer andrewmsutton ralfrothenberger}, pages = {3893-3899}, publisher = {AAAI Press}, title = {Phase Transitions for Scale-Free SAT Formulas}, year = 2017 }
• 
  Friedrich, Tobias; Neumann, FrankWhat's Hot in Evolutionary Computation. Conference on 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 = {Conference on Artificial Intelligence (AAAI)}, keywords = {year2017 adelaide tobiasfriedrich aaai frankneumann}, pages = {5064-5066}, title = {What's Hot in Evolutionary Computation}, year = 2017 }
• 
  Gao, Wanru; Friedrich, Tobias; Kötzing, Timo; Neumann, FrankScaling up Local Search for Minimum Vertex Cover in Large Graphs by Parallel Kernelization. Australasian Conference on Artificial Intelligence (AUSAI) 2017: 131-143
  [ Abstract ] [ BibTeX ] [ DOI ] [ 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)}, keywords = {timokoetzing wanrugao year2017 tobiasfriedrich ausai frankneumann}, pages = {131-143}, title = {Scaling up Local Search for Minimum Vertex Cover in Large Graphs by Parallel Kernelization}, year = 2017 }
• 
  Wagner, Markus; Friedrich, Tobias; Lindauer, MariusImproving local search in a minimum vertex cover solver for classes of networks. Congress on Evolutionary Computation (CEC) 2017: 1704-1711
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ 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)}, keywords = {markuswagner cec year2017 tobiasfriedrich}, pages = {1704-1711}, title = {Improving local search in a minimum vertex cover solver for classes of networks}, year = 2017 }
• 
  Friedrich, Tobias; Krohmer, Anton; Rothenberger, Ralf; Sauerwald, Thomas; Sutton, Andrew M.Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT. European Symposium on Algorithms (ESA) 2017: 37:1-37:15
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. The worst-case hardness of SAT lies at the core of computational complexity theory. The average-case analysis of SAT has triggered the development of sophisticated rigorous and non-rigorous techniques for analyzing random structures. Despite a long line of research and substantial progress, nearly all theoretical work on random SAT assumes a uniform distribution on the variables. In contrast, real-world instances often exhibit large fluctuations in variable occurrence. This can be modeled by a scale-free distribution of the variables, which results in distributions closer to industrial SAT instances. We study random \(k\)-SAT on \(n\) variables, \(m=\Theta(n)\) clauses, and a power law distribution on the variable occurrences with exponent \(\beta\). We observe a satisfiability threshold at \(\beta=(2k-1)/(k-1)\). This threshold is tight in the sense that instances with \( \beta\) \(< (2k-1)/(k-1)-\varepsilon\) for any constant \(\varepsilon>0\) are unsatisfiable with high probability (w.h.p.). For \(\beta\ge(2k-1)/(k-1)+\varepsilon\), the picture is reminiscent of the uniform case: instances are satisfiable w.h.p. for sufficiently small constant clause-variable ratios \(m/n\); they are unsatisfiable above a ratio \(m/n\) that depends on \(\beta\).
  @inproceedings{friedrich2017bounds, abstract = {Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. The worst-case hardness of SAT lies at the core of computational complexity theory. The average-case analysis of SAT has triggered the development of sophisticated rigorous and non-rigorous techniques for analyzing random structures. Despite a long line of research and substantial progress, nearly all theoretical work on random SAT assumes a uniform distribution on the variables. In contrast, real-world instances often exhibit large fluctuations in variable occurrence. This can be modeled by a scale-free distribution of the variables, which results in distributions closer to industrial SAT instances. We study random \(k\)-SAT on \(n\) variables, \(m=\Theta(n)\) clauses, and a power law distribution on the variable occurrences with exponent \(\beta\). We observe a satisfiability threshold at \(\beta=(2k-1)/(k-1)\). This threshold is tight in the sense that instances with \( \beta\) \(< (2k-1)/(k-1)-\varepsilon\) for any constant \(\varepsilon>0\) are unsatisfiable with high probability (w.h.p.). For \(\beta\ge(2k-1)/(k-1)+\varepsilon\), the picture is reminiscent of the uniform case: instances are satisfiable w.h.p. for sufficiently small constant clause-variable ratios \(m/n\); they are unsatisfiable above a ratio \(m/n\) that depends on \(\beta\).}, author = {Friedrich, Tobias and Krohmer, Anton and Rothenberger, Ralf and Sauerwald, Thomas and Sutton, Andrew M.}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {esa year2017 tobiasfriedrich scalefree_sat antonkrohmer andrewmsutton ralfrothenberger}, month = {sep}, pages = {37:1-37:15}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, series = {LIPIcs}, title = {Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT}, volume = 87, year = 2017 }
• 
  Friedrich, Tobias; Kötzing, Timo; Quinzan, Francesco; Sutton, Andrew MichaelResampling vs Recombination: a Statistical Run Time Estimation. Foundations of Genetic Algorithms (FOGA) 2017: 25-35
  [ 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)}, keywords = {foga timokoetzing year2017 francescoquinzan tobiasfriedrich andrewmsutton}, pages = {25-35}, title = {Resampling vs Recombination: a Statistical Run Time Estimation}, year = 2017 }
• 
  Pourhassan, Mojgan; Friedrich, Tobias; Neumann, FrankOn 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)}, keywords = {FOGA moganpourhassan year2017 adelaide tobiasfriedrich frankneumann}, pages = {37-44}, publisher = {ACM Press}, title = {On the Use of the Dual Formulation for Minimum Weighted Vertex Cover in Evolutionary Algorithms}, year = 2017 }
• 
  Friedrich, Tobias; Kötzing, Timo; Lagodzinski, J. A. Gregor; Neumann, Frank; Schirneck, MartinAnalysis 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)}, keywords = {gregorlagodzinski foga timokoetzing year2017 tobiasfriedrich frankneumann martinschirneck}, 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 }
• 
  Chauhan, Ankit; Friedrich, Tobias; Quinzan, FrancescoApproximating Optimization Problems using EAs on Scale-Free Networks. Genetic and Evolutionary Computation Conference (GECCO) 2017: 235-242
  [ Abstract ] [ BibTeX ] [ DOI ] [ 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(n^3)\) 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(n^3)\) 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)}, keywords = {year2017 francescoquinzan tobiasfriedrich gecco ankitchauhan}, pages = {235-242}, title = {Approximating Optimization Problems using EAs on Scale-Free Networks}, year = 2017 }
• 
  Friedrich, Tobias; Kötzing, Timo; Melnichenko, AnnaAnalyzing Search Heuristics with Differential Equations. Genetic and Evolutionary Computation Conference (GECCO) 2017: 313-314
  [ Abstract ] [ BibTeX ] [ DOI ] [ 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)}, keywords = {timokoetzing year2017 tobiasfriedrich gecco annamelnichenko}, pages = {313-314}, title = {Analyzing Search Heuristics with Differential Equations}, year = 2017 }
• 
  Doerr, Benjamin; Fischbeck, Philipp; Frahnow, Clemens; Friedrich, Tobias; Kötzing, Timo; Schirneck, MartinIsland Models Meet Rumor Spreading. Genetic and Evolutionary Computation Conference (GECCO) 2017: 1359-1366
  [ Abstract ] [ BibTeX ] [ DOI ] [ 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)}, keywords = {philippfischbeck timokoetzing year2017 tobiasfriedrich benjamindoerr gecco martinschirneck clemensfrahnow}, pages = {1359-1366}, title = {Island Models Meet Rumor Spreading}, year = 2017 }
• 
  Shi, Feng; Schirneck, Martin; Friedrich, Tobias; Kötzing, Timo; Neumann, FrankReoptimization Times of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints. Genetic and Evolutionary Computation Conference (GECCO) 2017: 1407-1414
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ 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 efficiently 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 efficiently 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)}, keywords = {timokoetzing year2017 fengshi tobiasfriedrich gecco frankneumann martinschirneck}, pages = {1407-1414}, title = {Reoptimization Times of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints}, year = 2017 }
• 
  Friedrich, Tobias; Ihde, Sven; Keßler, Christoph; Lenzner, Pascal; Neubert, Stefan; Schumann, DavidEfficient Best Response Computation for Strategic Network Formation under Attack. Symposium on Algorithmic Game Theory (SAGT) 2017: 199-211
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Inspired by real world examples, e.g. the Internet, researchers have introduced an abundance of strategic games to study natural phenomena in networks. Unfortunately, almost all of these games have the conceptual drawback of being computationally intractable, i.e. computing a best response strategy or checking if an equilibrium is reached is NP-hard. Thus, a main challenge in the field is to find tractable realistic network formation models. We address this challenge by investigating a very recently introduced model by Goyal et al. [WINE'16] which focuses on robust networks in the presence of a strong adversary who attacks (and kills) nodes in the network and lets this attack spread virus-like to neighboring nodes and their neighbors. Our main result is to establish that this natural model is one of the few exceptions which are both realistic and computationally tractable. In particular, we answer an open question of Goyal et al. by providing an efficient algorithm for computing a best response strategy, which implies that deciding whether the game has reached a Nash equilibrium can be done efficiently as well. Our algorithm essentially solves the problem of computing a minimal connection to a network which maximizes the reachability while hedging against severe attacks on the network infrastructure and may thus be of independent interest.
  @inproceedings{friedrich2017efficient, abstract = {Inspired by real world examples, e.g. the Internet, researchers have introduced an abundance of strategic games to study natural phenomena in networks. Unfortunately, almost all of these games have the conceptual drawback of being computationally intractable, i.e. computing a best response strategy or checking if an equilibrium is reached is NP-hard. Thus, a main challenge in the field is to find tractable realistic network formation models. We address this challenge by investigating a very recently introduced model by Goyal et al. [WINE'16] which focuses on robust networks in the presence of a strong adversary who attacks (and kills) nodes in the network and lets this attack spread virus-like to neighboring nodes and their neighbors. Our main result is to establish that this natural model is one of the few exceptions which are both realistic and computationally tractable. In particular, we answer an open question of Goyal et al. by providing an efficient algorithm for computing a best response strategy, which implies that deciding whether the game has reached a Nash equilibrium can be done efficiently as well. Our algorithm essentially solves the problem of computing a minimal connection to a network which maximizes the reachability while hedging against severe attacks on the network infrastructure and may thus be of independent interest.}, author = {Friedrich, Tobias and Ihde, Sven and Keßler, Christoph and Lenzner, Pascal and Neubert, Stefan and Schumann, David}, booktitle = {Symposium on Algorithmic Game Theory (SAGT)}, keywords = {svenihde year2017 christophkessler tobiasfriedrich davidschumann pascallenzner stefanneubert sagt}, pages = {199-211}, title = {Efficient Best Response Computation for Strategic Network Formation under Attack}, year = 2017 }
• 
  Friedrich, Tobias; Ihde, Sven; Keßler, Christoph; Lenzner, Pascal; Neubert, Stefan; Schumann, DavidBrief Announcement: Efficient Best Response Computation for Strategic Network Formation under Attack. Symposium on Parallelism in Algorithms and Architectures (SPAA) 2017: 321-323
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Inspired by real world examples, e.g. the Internet, researchers have introduced an abundance of strategic games to study natural phenomena in networks. Unfortunately, almost all of these games have the conceptual drawback of being computationally intractable, i.e. computing a best response strategy or checking if an equilibrium is reached is NP-hard. Thus, a main challenge in the field is to find tractable realistic network formation models. We address this challenge by establishing that the recently introduced model by Goyal et al.[WINE'16], which focuses on robust networks in the presence of a strong adversary, is a rare exception which is both realistic and computationally tractable. In particular, we sketch an efficient algorithm for computing a best response strategy, which implies that deciding whether the game has reached a Nash equilibrium can be done efficiently as well. Our algorithm essentially solves the problem of computing a minimal connection to a network which maximizes the reachability while hedging against severe attacks on the network infrastructure.
  @inproceedings{friedrich2017brief, abstract = {Inspired by real world examples, e.g. the Internet, researchers have introduced an abundance of strategic games to study natural phenomena in networks. Unfortunately, almost all of these games have the conceptual drawback of being computationally intractable, i.e. computing a best response strategy or checking if an equilibrium is reached is NP-hard. Thus, a main challenge in the field is to find tractable realistic network formation models. We address this challenge by establishing that the recently introduced model by Goyal et al.[WINE'16], which focuses on robust networks in the presence of a strong adversary, is a rare exception which is both realistic and computationally tractable. In particular, we sketch an efficient algorithm for computing a best response strategy, which implies that deciding whether the game has reached a Nash equilibrium can be done efficiently as well. Our algorithm essentially solves the problem of computing a minimal connection to a network which maximizes the reachability while hedging against severe attacks on the network infrastructure.}, 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)}, keywords = {svenihde year2017 christophkessler spaa tobiasfriedrich davidschumann pascallenzner stefanneubert}, pages = {321-323}, title = {Brief Announcement: Efficient Best Response Computation for Strategic Network Formation under Attack}, year = 2017 }

2016 [ nach oben ]

• 
  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 \log n)^2 \log 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 \log n)^2 \log n)))\), optimization will be successful.}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Sutton, Andrew M.}, journal = {Evolutionary Computation}, keywords = {martinskrejca timokoetzing year2016 tobiasfriedrich andrewmsutton EC}, number = 2, pages = {237-254}, title = {Robustness of Ant Colony Optimization to Noise}, volume = 24, year = 2016 }
• 
  Arndt, Tobias; Hafner, Danijar; Kellermeier, Thomas; Krogmann, Simon; Razmjou, Armin; Krejca, Martin S.; Rothenberger, Ralf; Friedrich, TobiasProbabilistic 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 Rothenberger, Ralf and Friedrich, Tobias}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {ESA tobiasarndt martinskrejca year2016 thomaskellermeier tobiasfriedrich arminrazmjou ralfrothenberger simonkrogmann danijarhafner}, pages = {6:1-6:13}, title = {Probabilistic Routing for On-Street Parking Search}, year = 2016 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Krohmer, AntonHyperbolic 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 - 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 - 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)}, keywords = {ESA thomasblaesius year2016 tobiasfriedrich antonkrohmer hyperbolic_analysis}, pages = {15:1-15:16}, title = {Hyperbolic Random Graphs: Separators and Treewidth}, year = 2016 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton; Laue, SörenEfficient Embedding of Scale-Free Graphs in the Hyperbolic Plane. European Symposium on Algorithms (ESA) 2016: 16:1-16:18

  EATCS Best Paper Award
  [ Abstract ] [ BibTeX ] [ URL ] [ 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)}, keywords = {ESA thomasblaesius bestpaper year2016 tobiasfriedrich hyperbolic_embedding antonkrohmer}, note = {EATCS Best Paper Award}, pages = {16:1-16:18}, title = {Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane}, year = 2016 }
• 
  Chauhan, Ankit; Friedrich, Tobias; Rothenberger, RalfGreed 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)}, keywords = {FSTTCS year2016 tobiasfriedrich ralfrothenberger ankitchauhan}, pages = {33:1-33:15}, title = {Greed is Good for Deterministic Scale-Free Networks}, 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)}, keywords = {timokoetzing year2016 GECCO francescoquinzan tobiasfriedrich andrewmsutton}, pages = {3-4}, title = {Ant Colony Optimization Beats Resampling on Noisy Functions}, 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)}, keywords = {martinskrejca timokoetzing year2016 tobiasfriedrich gecco andrewmsutton}, pages = {161-162}, title = {The Benefit of Recombination in Noisy Evolutionary Search}, year = 2016 }
• 
  Dang, Duc-Cuong; Friedrich, Tobias; Krejca, Martin S.; Kötzing, Timo; Lehre, Per Kristian; Oliveto, Pietro S.; Sudholt, Dirk; Sutton, Andrew MichaelEscaping 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)}, keywords = {martinskrejca timokoetzing year2016 tobiasfriedrich gecco andrewmsutton}, pages = {645-652}, publisher = {ACM Press}, title = {Escaping Local Optima with Diversity Mechanisms and Crossover}, year = 2016 }
• 
  Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Nallaperuma, Samadhi; Neumann, Frank; Schirneck, MartinFast 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)}, keywords = {samadhinallaperuma martinskrejca timokoetzing year2016 GECCO tobiasfriedrich frankneumann martinschirneck}, pages = {661-668}, publisher = {ACM Press}, title = {Fast Building Block Assembly by Majority Vote Crossover}, 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)}, keywords = {martinskrejca timokoetzing year2016 GECCO tobiasfriedrich}, pages = {1139-1146}, title = {{EDA}s cannot be Balanced and Stable}, year = 2016 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Schirneck, MartinThe 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}, keywords = {thomasblaesius ipec year2016 tobiasfriedrich martinschirneck}, pages = {6:1-6:13}, publisher = {Schloss Dagstuhl&ndash;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, TobiasScale-Free Networks, Hyperbolic Geometry, and Efficient Algorithms. Symposium on Mathematical Foundations of Computer Science (MFCS) 2016: 4:1-4:3

  Invited Talk
  [ 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)}, keywords = {year2016 tobiasfriedrich mfcs}, note = {Invited Talk}, pages = {4:1-4:3}, title = {Scale-Free Networks, Hyperbolic Geometry, and Efficient Algorithms}, year = 2016 }
• 
  Gao, Wanru; Friedrich, Tobias; Neumann, FrankFixed-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)}, keywords = {wanrugao year2016 tobiasfriedrich frankneumann 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.; 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)}, keywords = {martinskrejca timokoetzing year2016 tobiasfriedrich andrewmsutton PPSN}, pages = {761-770}, title = {Graceful Scaling on Uniform versus Steep-Tailed Noise}, 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)}, keywords = {timokoetzing year2016 tobiasfriedrich andrewmsutton PPSN}, pages = {771-781}, title = {On the Robustness of Evolving Populations}, 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)}, keywords = {martinskrejca timokoetzing tobiasfriedrich andrewmsutton PPSN}, pages = {890-900}, title = {Emergence of Diversity and its Benefits for Crossover in Genetic Algorithms}, year = 2016 }
• 
  Friedrich, Tobias; Neumann, Frank; Sutton, Andrew M.Proceedings of the 2016 on Genetic and Evolutionary Computation Conference, GECCO 2016, Denver, CO, USA, July 20 - 24, 2016. 2016ACM.

  Editorship
  [ BibTeX ] [ URL ] [ DOI ]
   
  @proceedings{DBLP:conf/gecco/2016, author = {Friedrich, Tobias and Neumann, Frank and Sutton, Andrew M.}, keywords = {year2016 tobiasfriedrich gecco frankneumann andrewmsutton}, note = {Editorship}, publisher = {ACM}, title = {Proceedings of the 2016 on Genetic and Evolutionary Computation Conference, GECCO 2016, Denver, CO, USA, July 20 - 24, 2016}, year = 2016 }
• 
  Friedrich, Tobias; Neumann, Frank; Sutton, Andrew M.Genetic and Evolutionary Computation Conference, GECCO 2016, Denver, CO, USA, July 20-24, 2016, Companion Material Proceedings. 2016ACM.

  Editorship
  [ BibTeX ] [ URL ] [ DOI ]
   
  @proceedings{DBLP:conf/gecco/2016c, author = {Friedrich, Tobias and Neumann, Frank and Sutton, Andrew M.}, keywords = {year2016 tobiasfriedrich gecco frankneumann andrewmsutton}, note = {Editorship}, publisher = {ACM}, title = {Genetic and Evolutionary Computation Conference, GECCO 2016, Denver, CO, USA, July 20-24, 2016, Companion Material Proceedings}, year = 2016 }

2015 [ nach oben ]

• 
  Friedrich, Tobias; Wagner, MarkusSeeding 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}, keywords = {imported asc year2015 tobiasfriedrich}, pages = {223-230}, title = {Seeding the initial population of multi-objective evolutionary algorithms: A computational study}, volume = 33, year = 2015 }
• 
  Friedrich, Tobias; Krohmer, AntonParameterized 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}, keywords = {imported year2015 tobiasfriedrich antonkrohmer dam}, pages = {130-138}, title = {Parameterized clique on inhomogeneous random graphs}, volume = 184, year = 2015 }
• 
  Wagner, Markus; Bringmann, Karl; Friedrich, Tobias; Neumann, FrankEfficient 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}, keywords = {markuswagner imported karlbringmann eor year2015 tobiasfriedrich frankneumann}, number = 2, pages = {465-479}, title = {Efficient optimization of many objectives by approximation-guided evolution}, volume = 243, year = 2015 }
• 
  Friedrich, Tobias; Neumann, Frank; Thyssen, ChristianMultiplicative 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 \(\mu\) 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 \(\mu\) 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}, keywords = {christianthyssen imported year2015 tobiasfriedrich frankneumann ec}, 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, FrankMaximizing 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}, keywords = {year2015 tobiasfriedrich frankneumann ec}, number = 4, pages = {543-558}, publisher = {MIT Press}, title = {Maximizing Submodular Functions under Matroid Constraints by Evolutionary Algorithms}, volume = 23, year = 2015 }
• 
  Berenbrink, Petra; Cooper, Colin; Friedetzky, Tom; Friedrich, Tobias; Sauerwald, ThomasRandomized diffusion for indivisible loads. Journal of Computer and System Sciences 2015: 159-185
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We present a new randomized diffusion-based algorithm for balancing indivisible tasks (tokens) on a network. Our aim is to minimize the discrepancy between the maximum and minimum load. The algorithm works as follows. Every vertex distributes its tokens as evenly as possible among its neighbors and itself. If this is not possible without splitting some tokens, the vertex redistributes its excess tokens among all its neighbors randomly (without replacement). In this paper we prove several upper bounds on the load discrepancy for general networks. These bounds depend on some expansion properties of the network, that is, the second largest eigenvalue, and a novel measure which we refer to as refined local divergence. We then apply these general bounds to obtain results for some specific networks. For constant-degree expanders and torus graphs, these yield exponential improvements on the discrepancy bounds compared to the algorithm of Rabani, Sinclair, and Wanka. For hypercubes we obtain a polynomial improvement. In contrast to previous papers, our algorithm is vertex-based and not edge-based. This means excess tokens are assigned to vertices instead to edges, and the vertex reallocates all of its excess tokens by itself. This approach avoids nodes having "negative loads", but causes additional dependencies for the analysis.
  @article{DBLP:journals/jcss/BerenbrinkCFFS15, abstract = {We present a new randomized diffusion-based algorithm for balancing indivisible tasks (tokens) on a network. Our aim is to minimize the discrepancy between the maximum and minimum load. The algorithm works as follows. Every vertex distributes its tokens as evenly as possible among its neighbors and itself. If this is not possible without splitting some tokens, the vertex redistributes its excess tokens among all its neighbors randomly (without replacement). In this paper we prove several upper bounds on the load discrepancy for general networks. These bounds depend on some expansion properties of the network, that is, the second largest eigenvalue, and a novel measure which we refer to as refined local divergence. We then apply these general bounds to obtain results for some specific networks. For constant-degree expanders and torus graphs, these yield exponential improvements on the discrepancy bounds compared to the algorithm of Rabani, Sinclair, and Wanka. For hypercubes we obtain a polynomial improvement. In contrast to previous papers, our algorithm is vertex-based and not edge-based. This means excess tokens are assigned to vertices instead to edges, and the vertex reallocates all of its excess tokens by itself. This approach avoids nodes having "negative loads", but causes additional dependencies for the analysis.}, author = {Berenbrink, Petra and Cooper, Colin and Friedetzky, Tom and Friedrich, Tobias and Sauerwald, Thomas}, journal = {Journal of Computer and System Sciences}, keywords = {noabstract jcss year2015 tobiasfriedrich}, number = 1, pages = {159-185}, title = {Randomized diffusion for indivisible loads}, volume = 81, year = 2015 }
• 
  Friedrich, Tobias; Hercher, ChristianOn 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) 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) 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}, keywords = {imported jda year2015 tobiasfriedrich christianhercher}, pages = {128-136}, title = {On the kernel size of clique cover reductions for random intersection graphs}, volume = 34, 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á, BarboraToward 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}, keywords = {JTB year2015 tobiasfriedrich andrewmsutton}, pages = {28-43}, publisher = {Elsevier}, title = {Toward a unifying framework for evolutionary processes}, volume = 383, year = 2015 }
• 
  Friedrich, Tobias; He, Jun; Jansen, Thomas; Moraglio, AlbertoGenetic and Evolutionary Computation. Theoretical Computer Science 2015: 1-2
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Evolutionary computation and other nature-inspired search heuristics are known and applied on a daily basis for 50 years. They remain an important tool in situations where difficult problems need to be solved and no good problem-specific solution is available. Thanks to continuous efforts directed at a theoretical foundation of this broad and complex set of heuristics we have a much improved understanding of their properties, strengths and limitations. This special issue contains a collection of theoretical analyses of quite different nature-inspired heuristics, all presented in preliminary form either at the field’s largest conference, the Genetic and Evolutionary Computation Conference (GECCO 2013), or at a small and specialized workshop on Theory of Randomized Search Heuristics (ThRaSH 2013) that provides an opportunity for theoreticians in the field to meet and discuss their work since 2007. All articles presented here have been reworked and significantly expanded beyond their initial presentation and they all witness that theory is now developed well beyond the understanding of very simple evolutionary algorithms on simple example functions.
  @article{DBLP:journals/tcs/FriedrichHJM15, abstract = {Evolutionary computation and other nature-inspired search heuristics are known and applied on a daily basis for 50 years. They remain an important tool in situations where difficult problems need to be solved and no good problem-specific solution is available. Thanks to continuous efforts directed at a theoretical foundation of this broad and complex set of heuristics we have a much improved understanding of their properties, strengths and limitations. This special issue contains a collection of theoretical analyses of quite different nature-inspired heuristics, all presented in preliminary form either at the field’s largest conference, the Genetic and Evolutionary Computation Conference (GECCO 2013), or at a small and specialized workshop on Theory of Randomized Search Heuristics (ThRaSH 2013) that provides an opportunity for theoreticians in the field to meet and discuss their work since 2007. All articles presented here have been reworked and significantly expanded beyond their initial presentation and they all witness that theory is now developed well beyond the understanding of very simple evolutionary algorithms on simple example functions.}, author = {Friedrich, Tobias and He, Jun and Jansen, Thomas and Moraglio, Alberto}, journal = {Theoretical Computer Science}, keywords = {tcs noabstract year2015 tobiasfriedrich}, pages = {1-2}, title = {Genetic and Evolutionary Computation}, volume = 561, year = 2015 }
• 
  Fountoulakis, Nikolaos; Friedrich, Tobias; Hermelin, DannyOn 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 ErdHo}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\H{o}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}, keywords = {imported tcs year2015 tobiasfriedrich}, pages = {18-29}, title = {On the average-case complexity of parameterized clique}, volume = 576, year = 2015 }
• 
  Bringmann, Karl; Friedrich, Tobias; Klitzke, PatrickEfficient 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 cdot \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 \cdot \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)}, keywords = {imported cec year2015 tobiasfriedrich}, pages = {970-977}, title = {Efficient computation of two-dimensional solution sets maximizing the epsilon-indicator}, 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

  Best-Paper Award (ACO/SI Track)
  [ 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)}, keywords = {imported first martinskrejca timokoetzing bestpaper year2015 tobiasfriedrich gecco andrewmsutton}, note = {Best-Paper Award (ACO/SI Track)}, pages = {17-24}, title = {Robustness of Ant Colony Optimization to Noise}, year = 2015 }
• 
  Bringmann, Karl; Friedrich, Tobias; Hoefer, Martin; Rothenberger, Ralf; Sauerwald, ThomasUltra-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((log~log~n)^2)\) steps. It does not need to know the exponent \(2<\beta<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((log&nbsp;log&nbsp;n)^2)\) steps. It does not need to know the exponent \(2<\beta<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)}, keywords = {imported year2015 tobiasfriedrich icalp ralfrothenberger}, pages = {516-527}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Ultra-Fast Load Balancing on Scale-Free Networks}, volume = 9135, year = 2015 }
• 
  Friedrich, Tobias; Krohmer, AntonOn 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 (Boguna, 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 \(\beta\) 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)\). If the average degree is bounded from above by some constant, we show that the latter bound is tight by proving an upper bound of \(O(\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 (Boguna, 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 \(\beta\) 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)\). If the average degree is bounded from above by some constant, we show that the latter bound is tight by proving an upper bound of \(O(\log n)\).}, author = {Friedrich, Tobias and Krohmer, Anton}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {imported year2015 tobiasfriedrich antonkrohmer icalp hyperbolic_analysis}, pages = {614-625}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {On the Diameter of Hyperbolic Random Graphs}, volume = 9135, year = 2015 }
• 
  Friedrich, Tobias; Krohmer, AntonCliques 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, Boguna, 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 \(\gamma = 3\). More precisely, for \(\gamma\) \(\in\) \((2,3)\) we prove \(E[K_k] = \)\(n^{k(3-\gamma)/2}\)\(\Theta(k)^{-k}\) and \(\omega(G) = \)\(\Theta(\)\(n^{(3-\gamma)/2})\) while for \(\gamma \ge 3\) we prove \(E[K_k] = n \Theta(k)^{-k}\) and \(\omega(G) = \Theta(\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, Boguna, 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 \(\gamma = 3\). More precisely, for \(\gamma\) \(\in\) \((2,3)\) we prove \(E[K_k] = \)\(n^{k(3-\gamma)/2}\)\(\Theta(k)^{-k}\) and \(\omega(G) = \)\(\Theta(\)\(n^{(3-\gamma)/2})\) while for \(\gamma \ge 3\) we prove \(E[K_k] = n \Theta(k)^{-k}\) and \(\omega(G) = \Theta(\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)}, keywords = {imported infocom year2015 tobiasfriedrich antonkrohmer hyperbolic_analysis}, pages = {1544-1552}, title = {Cliques in Hyperbolic Random Graphs}, 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}, keywords = {isaac martinskrejca timokoetzing year2015 tobiasfriedrich andrewmsutton}, pages = {140-150}, publisher = {Springer Berlin Heidelberg}, title = {The Benefit of Recombination in Noisy Evolutionary Search}, year = 2015 }
• 
  Friedrich, Tobias; Katzmann, Maximilian; Krohmer, AntonUnbounded 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 \(\mathbb{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 \(\mathbb{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 \(\mathbb{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 \(\mathbb{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)}, keywords = {imported isaac year2015 tobiasfriedrich antonkrohmer maximiliankatzmann}, pages = {212-222}, series = {Lecture Notes in Computer Science}, title = {Unbounded Discrepancy of Deterministic Random Walks on Grids}, volume = 9472, year = 2015 }

2014 [ nach oben ]

• 
  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}, keywords = {noabstract tobiasfriedrich year2014}, pages = 1, title = {Genetic and Evolutionary Computation}, volume = 545, year = 2014 }
• 
  Doerr, Benjamin; Friedrich, Tobias; Sauerwald, ThomasQuasirandom 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, 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 = {Transactions on Algorithms}, keywords = {imported talg tobiasfriedrich year2014}, number = 2, pages = {9:1-9:35}, title = {Quasirandom Rumor Spreading}, volume = 11, year = 2014 }
• 
  Bringmann, Karl; Friedrich, TobiasConvergence of Hypervolume-Based Archiving Algorithms. 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 = {Transactions on Evolutionary Computation}, keywords = {imported tobiasfriedrich year2014 tevoc}, number = 5, pages = {643-657}, publisher = {IEEE}, title = {Convergence of Hypervolume-Based Archiving Algorithms}, volume = 18, year = 2014 }
• 
  Bringmann, Karl; Friedrich, Tobias; Krohmer, AntonDe-anonymization of Heterogeneous Random Graphs in Quasilinear Time. European 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 = {imported esa tobiasfriedrich year2014 antonkrohmer}, 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 }
• 
  Bringmann, Karl; Friedrich, Tobias; Klitzke, PatrickTwo-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 \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 = {imported tobiasfriedrich year2014 gecco}, pages = {589-596}, publisher = {{ACM}}, title = {Two-dimensional subset selection for hypervolume and epsilon-indicator}, year = 2014 }
• 
  Bringmann, Karl; Friedrich, Tobias; Klitzke, PatrickGeneric Postprocessing via Subset Selection for Hypervolume and Epsilon-Indicator. Parallel 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 tobiasfriedrich year2014 ppsn}, 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, FrankMaximizing Submodular Functions under Matroid Constraints by Multi-objective Evolutionary Algorithms. Parallel 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 = {imported tobiasfriedrich year2014 frankneumann ppsn}, 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 }

2013 [ nach oben ]

• 
  Friedrich, Tobias; Sauerwald, Thomas; Stauffer, AlexandreDiameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions. Algorithmica 2013: 65-88
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  A random geometric graph (RGG) is defined by placing \(n\) points uniformly at random in \([0,n^{1/d}]^d\), and joining two points by an edge whenever their Euclidean distance is at most some fixed \(r\). We assume that \(r\) is larger than the critical value for the emergence of a connected component with \(\Omega(n)\) nodes. We show that, with high probability (w.h.p.), for any two connected nodes with a Euclidean distance of \(\omega(\log n / r^{d-1})\), their graph distance is only a constant factor larger than their Euclidean distance. This implies that the diameter of the largest connected component is \(\Theta(n^{1/d}/r)\) w.h.p. We also prove that the condition on the Euclidean distance above is essentially tight. We also analyze the following randomized broadcast algorithm on RGGs. At the beginning, only one node from the largest connected component of the RGG is informed. Then, in each round, each informed node chooses a neighbor independently and uniformly at random and informs it. We prove that w.h.p. this algorithm informs every node in the largest connected component of an RGG within \(\Theta(n^1/d/r+\log n)\) rounds.
  @article{DBLP:journals/algorithmica/FriedrichSS13, abstract = {A random geometric graph (RGG) is defined by placing \(n\) points uniformly at random in \([0,n^{1/d}]^d\), and joining two points by an edge whenever their Euclidean distance is at most some fixed \(r\). We assume that \(r\) is larger than the critical value for the emergence of a connected component with \(\Omega(n)\) nodes. We show that, with high probability (w.h.p.), for any two connected nodes with a Euclidean distance of \(\omega(\log n / r^{d-1})\), their graph distance is only a constant factor larger than their Euclidean distance. This implies that the diameter of the largest connected component is \(\Theta(n^{1/d}/r)\) w.h.p. We also prove that the condition on the Euclidean distance above is essentially tight. We also analyze the following randomized broadcast algorithm on RGGs. At the beginning, only one node from the largest connected component of the RGG is informed. Then, in each round, each informed node chooses a neighbor independently and uniformly at random and informs it. We prove that w.h.p. this algorithm informs every node in the largest connected component of an RGG within \(\Theta(n^{1/d}/r+\log n)\) rounds.}, author = {Friedrich, Tobias and Sauerwald, Thomas and Stauffer, Alexandre}, journal = {Algorithmica}, keywords = {algorithmica noabstract tobiasfriedrich year2013}, number = 1, pages = {65-88}, title = {Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions}, volume = 67, year = 2013 }
• 
  Bringmann, Karl; Friedrich, Tobias; Igel, Christian; Voß, ThomasSpeeding up many-objective optimization by Monte Carlo approximations. Artificial Intelligence 2013: 22-29
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Many state-of-the-art evolutionary vector optimization algorithms compute the contributing hypervolume for ranking candidate solutions. However, with an increasing number of objectives, calculating the volumes becomes intractable. Therefore, although hypervolume-based algorithms are often the method of choice for bi-criteria optimization, they are regarded as not suitable for many-objective optimization. Recently, Monte Carlo methods have been derived and analyzed for approximating the contributing hypervolume. Turning theory into practice, we employ these results in the ranking procedure of the multi-objective covariance matrix adaptation evolution strategy (MO-CMA-ES) as an example of a state-of-the-art method for vector optimization. It is empirically shown that the approximation does not impair the quality of the obtained solutions given a budget of objective function evaluations, while considerably reducing the computation time in the case of multiple objectives. These results are obtained on common benchmark functions as well as on two design optimization tasks. Thus, employing Monte Carlo approximations makes hypervolume-based algorithms applicable to many-objective optimization.
  @article{DBLP:journals/ai/BringmannFIV13, abstract = {Many state-of-the-art evolutionary vector optimization algorithms compute the contributing hypervolume for ranking candidate solutions. However, with an increasing number of objectives, calculating the volumes becomes intractable. Therefore, although hypervolume-based algorithms are often the method of choice for bi-criteria optimization, they are regarded as not suitable for many-objective optimization. Recently, Monte Carlo methods have been derived and analyzed for approximating the contributing hypervolume. Turning theory into practice, we employ these results in the ranking procedure of the multi-objective covariance matrix adaptation evolution strategy (MO-CMA-ES) as an example of a state-of-the-art method for vector optimization. It is empirically shown that the approximation does not impair the quality of the obtained solutions given a budget of objective function evaluations, while considerably reducing the computation time in the case of multiple objectives. These results are obtained on common benchmark functions as well as on two design optimization tasks. Thus, employing Monte Carlo approximations makes hypervolume-based algorithms applicable to many-objective optimization.}, author = {Bringmann, Karl and Friedrich, Tobias and Igel, Christian and Voß, Thomas}, journal = {Artificial Intelligence}, keywords = {imported tobiasfriedrich year2013}, pages = {22-29}, title = {Speeding up many-objective optimization by Monte Carlo approximations}, volume = 204, year = 2013 }
• 
  Bringmann, Karl; Friedrich, TobiasApproximation quality of the hypervolume indicator. Artificial Intelligence 2013: 265-290
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  In order to allow a comparison of (otherwise incomparable) sets, many evolutionary multi-objective optimizers use indicator functions to guide the search and to evaluate the performance of search algorithms. The most widely used indicator is the hypervolume indicator. It measures the volume of the dominated portion of the objective space bounded from below by a reference point. Though the hypervolume indicator is very popular, it has not been shown that maximizing the hypervolume indicator of sets of bounded size is indeed equivalent to the overall objective of finding a good approximation of the Pareto front. To address this question, we compare the optimal approximation ratio with the approximation ratio achieved by two-dimensional sets maximizing the hypervolume indicator. We bound the optimal multiplicative approximation ratio of \(n\) points by \(1+\Theta(1/n)\) for arbitrary Pareto fronts. Furthermore, we prove that the same asymptotic approximation ratio is achieved by sets of \(n\) points that maximize the hypervolume indicator. However, there is a provable gap between the two approximation ratios which is even exponential in the ratio between the largest and the smallest value of the front. We also examine the additive approximation ratio of the hypervolume indicator in two dimensions and prove that it achieves the optimal additive approximation ratio apart from a small ratio.
  @article{DBLP:journals/ai/BringmannF13, abstract = {In order to allow a comparison of (otherwise incomparable) sets, many evolutionary multi-objective optimizers use indicator functions to guide the search and to evaluate the performance of search algorithms. The most widely used indicator is the hypervolume indicator. It measures the volume of the dominated portion of the objective space bounded from below by a reference point. Though the hypervolume indicator is very popular, it has not been shown that maximizing the hypervolume indicator of sets of bounded size is indeed equivalent to the overall objective of finding a good approximation of the Pareto front. To address this question, we compare the optimal approximation ratio with the approximation ratio achieved by two-dimensional sets maximizing the hypervolume indicator. We bound the optimal multiplicative approximation ratio of \(n\) points by \(1+\Theta(1/n)\) for arbitrary Pareto fronts. Furthermore, we prove that the same asymptotic approximation ratio is achieved by sets of \(n\) points that maximize the hypervolume indicator. However, there is a provable gap between the two approximation ratios which is even exponential in the ratio between the largest and the smallest value of the front. We also examine the additive approximation ratio of the hypervolume indicator in two dimensions and prove that it achieves the optimal additive approximation ratio apart from a small ratio.}, author = {Bringmann, Karl and Friedrich, Tobias}, journal = {Artificial Intelligence}, keywords = {imported ai tobiasfriedrich year2013}, pages = {265-290}, title = {Approximation quality of the hypervolume indicator}, volume = 195, year = 2013 }
• 
  Friedrich, Tobias; Kroeger, Trent; Neumann, FrankWeighted preferences in evolutionary multi-objective optimization. Machine Learning and Cybernetics 2013: 139-148
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Evolutionary algorithms have been widely used to tackle multi-objective optimization problems. Incorporating preference information into the search of evolutionary algorithms for multi-objective optimization is of great importance as it allows one to focus on interesting regions in the objective space. Zitzler et al. have shown how to use a weight distribution function on the objective space to incorporate preference information into hypervolume-based algorithms. We show that this weighted information can easily be used in other popular EMO algorithms as well. Our results for NSGA-II and SPEA2 show that this yields similar results to the hypervolume approach and requires less computational effort.
  @article{DBLP:journals/mlc/FriedrichKN13, abstract = {Evolutionary algorithms have been widely used to tackle multi-objective optimization problems. Incorporating preference information into the search of evolutionary algorithms for multi-objective optimization is of great importance as it allows one to focus on interesting regions in the objective space. Zitzler et al. have shown how to use a weight distribution function on the objective space to incorporate preference information into hypervolume-based algorithms. We show that this weighted information can easily be used in other popular EMO algorithms as well. Our results for NSGA-II and SPEA2 show that this yields similar results to the hypervolume approach and requires less computational effort.}, author = {Friedrich, Tobias and Kroeger, Trent and Neumann, Frank}, journal = {Machine Learning and Cybernetics}, keywords = {imported mlc trentkroeger tobiasfriedrich year2013 frankneumann}, number = 2, pages = {139-148}, title = {Weighted preferences in evolutionary multi-objective optimization}, volume = 4, year = 2013 }
• 
  Friedrich, Tobias; Levine, LionelFast simulation of large-scale growth models. Random Structures and Algorithms 2013: 185-213
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We give an algorithm that computes the final state of certain growth models without computing all intermediate states. Our technique is based on a "least action principle" which characterizes the odometer function of the growth process. Starting from an approximation for the odometer, we successively correct under- and overestimates and provably arrive at the correct final state. The degree of speedup depends on the accuracy of the initial guess. Determining the size of the boundary fluctuations in growth models like internal diffusion-limited aggregation (IDLA) is a long-standing open problem in statistical physics. As an application of our method, we calculate the size of fluctuations over two orders of magnitude beyond previous simulations.
  @article{DBLP:journals/rsa/FriedrichL13, abstract = {We give an algorithm that computes the final state of certain growth models without computing all intermediate states. Our technique is based on a "least action principle" which characterizes the odometer function of the growth process. Starting from an approximation for the odometer, we successively correct under- and overestimates and provably arrive at the correct final state. The degree of speedup depends on the accuracy of the initial guess. Determining the size of the boundary fluctuations in growth models like internal diffusion-limited aggregation (IDLA) is a long-standing open problem in statistical physics. As an application of our method, we calculate the size of fluctuations over two orders of magnitude beyond previous simulations.}, author = {Friedrich, Tobias and Levine, Lionel}, journal = {Random Structures and Algorithms}, keywords = {noabstract tobiasfriedrich year2013 rsa}, number = 2, pages = {185-213}, title = {Fast simulation of large-scale growth models}, volume = 42, year = 2013 }
• 
  Vladislavleva, Ekaterina; Friedrich, Tobias; Neumann, Frank; Wagner, MarkusPredicting the Energy Output of Wind Farms Based on Weather Data: Important Variables and their Correlation. Renewable Energy 2013: 236-243
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Wind energy plays an increasing role in the supply of energy world wide. The energy output of a wind farm is highly dependent on the weather conditions present at its site. If the output can be predicted more accurately, energy suppliers can coordinate the collaborative production of different energy sources more efficiently to avoid costly overproduction. In this paper, we take a computer science perspective on energy prediction based on weather data and analyze the important parameters as well as their correlation on the energy output. To deal with the interaction of the different parameters, we use symbolic regression based on the genetic programming tool DataModeler. Our studies are carried out on publicly available weather and energy data for a wind farm in Australia. We report on the correlation of the different variables for the energy output. The model obtained for energy prediction gives a very reliable prediction of the energy output for newly supplied weather data.
  @article{RE1, abstract = {Wind energy plays an increasing role in the supply of energy world wide. The energy output of a wind farm is highly dependent on the weather conditions present at its site. If the output can be predicted more accurately, energy suppliers can coordinate the collaborative production of different energy sources more efficiently to avoid costly overproduction. In this paper, we take a computer science perspective on energy prediction based on weather data and analyze the important parameters as well as their correlation on the energy output. To deal with the interaction of the different parameters, we use symbolic regression based on the genetic programming tool DataModeler. Our studies are carried out on publicly available weather and energy data for a wind farm in Australia. We report on the correlation of the different variables for the energy output. The model obtained for energy prediction gives a very reliable prediction of the energy output for newly supplied weather data.}, author = {Vladislavleva, Ekaterina and Friedrich, Tobias and Neumann, Frank and Wagner, Markus}, journal = {Renewable Energy}, keywords = {markuswagner RE ekatarinavladislavleva tobiasfriedrich year2013 frankneumann}, pages = {236-243}, publisher = {Elsevier}, title = {Predicting the Energy Output of Wind Farms Based on Weather Data: Important Variables and their Correlation}, volume = 50, year = 2013 }
• 
  Fellows, Michael R.; Friedrich, Tobias; Hermelin, Danny; Narodytska, Nina; Rosamond, Frances A.Constraint satisfaction problems: Convexity makes AllDifferent constraints tractable. Theoretical Computer Science 2013: 81-89
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We examine the complexity of constraint satisfaction problems that consist of a set of AllDiff constraints. Such CSPs naturally model a wide range of real-world and combinatorial problems, like scheduling, frequency allocations, and graph coloring problems. As this problem is known to be NP-complete, we investigate under which further assumptions it becomes tractable. We observe that a crucial property seems to be the convexity of the variable domains and constraints. Our main contribution is an extensive study of the complexity of Multiple AllDiff CSPs for a set of natural parameters, like maximum domain size and maximum size of the constraint scopes. We show that, depending on the parameter, convexity can make the problem tractable even though it is provably intractable in general. Interestingly, the convexity of constraints is the key property in achieving fixed parameter tractability, while the convexity of domains does not usually make the problem easier.
  @article{DBLP:journals/tcs/FellowsFHNR13, abstract = {We examine the complexity of constraint satisfaction problems that consist of a set of AllDiff constraints. Such CSPs naturally model a wide range of real-world and combinatorial problems, like scheduling, frequency allocations, and graph coloring problems. As this problem is known to be NP-complete, we investigate under which further assumptions it becomes tractable. We observe that a crucial property seems to be the convexity of the variable domains and constraints. Our main contribution is an extensive study of the complexity of Multiple AllDiff CSPs for a set of natural parameters, like maximum domain size and maximum size of the constraint scopes. We show that, depending on the parameter, convexity can make the problem tractable even though it is provably intractable in general. Interestingly, the convexity of constraints is the key property in achieving fixed parameter tractability, while the convexity of domains does not usually make the problem easier.}, author = {Fellows, Michael R. and Friedrich, Tobias and Hermelin, Danny and Narodytska, Nina and Rosamond, Frances A.}, journal = {Theoretical Computer Science}, keywords = {imported tcs tobiasfriedrich year2013}, pages = {81-89}, title = {Constraint satisfaction problems: Convexity makes AllDifferent constraints tractable}, volume = 472, year = 2013 }
• 
  Wagner, Markus; Friedrich, TobiasEfficient parent selection for Approximation-Guided Evolutionary multi-objective optimization. Congress on Evolutionary Computation (CEC) 2013: 1846-1853
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  The Pareto front of a multi-objective optimization problem is typically very large and can only be approximated. Approximation-Guided Evolution (AGE) is a recently presented evolutionary multi-objective optimization algorithm that aims at minimizing iteratively the approximation factor, which measures how well the current population approximates the Pareto front. It outperforms state-of-the-art algorithms for problems with many objectives. However, AGE's performance is not competitive on problems with very few objectives. We study the reason for this behavior and observe that AGE selects parents uniformly at random, which has a detrimental effect on its performance. We then investigate different algorithm-specific selection strategies for AGE. The main difficulty here is finding a computationally efficient selection scheme which does not harm AGEs linear runtime in the number of objectives. We present several improved selections schemes that are computationally efficient and substantially improve AGE on low-dimensional objective spaces, but have no negative effect in high-dimensional objective spaces.
  @inproceedings{DBLP:conf/cec/WagnerF13, abstract = {The Pareto front of a multi-objective optimization problem is typically very large and can only be approximated. Approximation-Guided Evolution (AGE) is a recently presented evolutionary multi-objective optimization algorithm that aims at minimizing iteratively the approximation factor, which measures how well the current population approximates the Pareto front. It outperforms state-of-the-art algorithms for problems with many objectives. However, AGE's performance is not competitive on problems with very few objectives. We study the reason for this behavior and observe that AGE selects parents uniformly at random, which has a detrimental effect on its performance. We then investigate different algorithm-specific selection strategies for AGE. The main difficulty here is finding a computationally efficient selection scheme which does not harm AGEs linear runtime in the number of objectives. We present several improved selections schemes that are computationally efficient and substantially improve AGE on low-dimensional objective spaces, but have no negative effect in high-dimensional objective spaces.}, author = {Wagner, Markus and Friedrich, Tobias}, booktitle = {Congress on Evolutionary Computation (CEC)}, keywords = {imported tobiasfriedrich year2013}, pages = {1846-1853}, title = {Efficient parent selection for Approximation-Guided Evolutionary multi-objective optimization}, year = 2013 }
• 
  Bringmann, Karl; Friedrich, TobiasParameterized average-case complexity of the hypervolume indicator. Genetic and Evolutionary Computation Conference (GECCO) 2013: 575-582

  Nominated for Best Paper Award (EMO Track)
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  The hypervolume indicator (HYP) is a popular measure for the quality of a set of \(n\) solutions in \(\mathbb{R}^d\). We discuss its asymptotic worst-case runtimes and several lower bounds depending on different complexity-theoretic assumptions. Assuming that P \(\neq\) NP, there is no algorithm with runtime \(poly(n,d)\). Assuming the exponential time hypothesis, there is no algorithm with runtime \(n^{o(d)}\). In contrast to these worst-case lower bounds, we study the average-case complexity of HYP for points distributed i.i.d. at random on a \(d\)-dimensional simplex. We present a general framework which translates any algorithm for HYP with worst-case runtime \(n^{f(d)}\) to an algorithm with worst-case runtime \(n^{f(d) +1}\) and fixed-parameter-tractable (FPT) average-case runtime. This can be used to show that HYP can be solved in expected time \(O(d^{d^2/2 n + d n^2)\), which implies that HYP is FPT on average while it is W1-hard in the worst-case. For constant dimension \(d\) this gives an algorithm for HYP with runtime \(O(n^2)\) on average. This is the first result proving that HYP is asymptotically easier in the average case. It gives a theoretical explanation why most HYP algorithms perform much better on average than their theoretical worst-case runtime predicts.
  @inproceedings{DBLP:conf/gecco/BringmannF13, abstract = {The hypervolume indicator (HYP) is a popular measure for the quality of a set of \(n\) solutions in \(\mathbb{R}^d\). We discuss its asymptotic worst-case runtimes and several lower bounds depending on different complexity-theoretic assumptions. Assuming that P \(\neq\) NP, there is no algorithm with runtime \(poly(n,d)\). Assuming the exponential time hypothesis, there is no algorithm with runtime \(n^{o(d)}\). In contrast to these worst-case lower bounds, we study the average-case complexity of HYP for points distributed i.i.d. at random on a \(d\)-dimensional simplex. We present a general framework which translates any algorithm for HYP with worst-case runtime \(n^{f(d)}\) to an algorithm with worst-case runtime \(n^{f(d) +1}\) and fixed-parameter-tractable (FPT) average-case runtime. This can be used to show that HYP can be solved in expected time \(O(d^{d^2/2} n + d n^2)\), which implies that HYP is FPT on average while it is W1-hard in the worst-case. For constant dimension \(d\) this gives an algorithm for HYP with runtime \(O(n^2)\) on average. This is the first result proving that HYP is asymptotically easier in the average case. It gives a theoretical explanation why most HYP algorithms perform much better on average than their theoretical worst-case runtime predicts.}, author = {Bringmann, Karl and Friedrich, Tobias}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {imported tobiasfriedrich gecco year2013}, note = {Nominated for Best Paper Award (EMO Track)}, pages = {575-582}, title = {Parameterized average-case complexity of the hypervolume indicator}, year = 2013 }
• 
  Anand, S.; Bringmann, Karl; Friedrich, Tobias; Garg, Naveen; Kumar, AmitMinimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines. International Colloquium on Automata, Languages and Programming (ICALP) 2013: 13-24
  [ Abstract ] [ BibTeX ] [ 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.
  @inproceedings{DBLP:conf/icalp/0002BFGK13, 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}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {imported tobiasfriedrich year2013}, pages = {13-24}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines}, volume = 7965, year = 2013 }
• 
  Bringmann, Karl; Friedrich, TobiasExact and Efficient Generation of Geometric Random Variates and Random Graphs. International Colloquium on Automata, Languages, and Programming (ICALP) 2013: 267-278
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  The standard algorithm for fast generation of ErdHo}s-Rényi random graphs only works in the Real RAM model. The critical point is the generation of geometric random variates \(Geo(p)\), for which there is no algorithm that is both exact and efficient in any bounded precision machine model. For a RAM model with word size \(w=\Omega(\log\log(1/p))\), we show that this is possible and present an exact algorithm for sampling \(Geo(p)\) in optimal expected time \(O(1 + \log(1/p) / w)\). We also give an exact algorithm for sampling \(\min\{n, Geo(p)\}\) in optimal expected time \(O(1 + \log(\min\{1/p,n\})/w)\). This yields a new exact algorithm for sampling ErdHo}s-Rényi and Chung-Lu random graphs of \(n\) vertices and \(m\) (expected) edges in optimal expected runtime \(O(n + m)\) on a RAM with word size \(w=\Theta(\log n)\).
  @inproceedings{DBLP:conf/icalp/BringmannF13, abstract = {The standard algorithm for fast generation of Erd\H{o}s-Rényi random graphs only works in the Real RAM model. The critical point is the generation of geometric random variates \(Geo(p)\), for which there is no algorithm that is both exact and efficient in any bounded precision machine model. For a RAM model with word size \(w=\Omega(\log\log(1/p))\), we show that this is possible and present an exact algorithm for sampling \(Geo(p)\) in optimal expected time \(O(1 + \log(1/p) / w)\). We also give an exact algorithm for sampling \(\min\{n, Geo(p)\}\) in optimal expected time \(O(1 + \log(\min\{1/p,n\})/w)\). This yields a new exact algorithm for sampling Erd\H{o}s-Rényi and Chung-Lu random graphs of \(n\) vertices and \(m\) (expected) edges in optimal expected runtime \(O(n + m)\) on a RAM with word size \(w=\Theta(\log n)\).}, author = {Bringmann, Karl and Friedrich, Tobias}, booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)}, keywords = {imported tobiasfriedrich year2013 icalp}, pages = {267-278}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Exact and Efficient Generation of Geometric Random Variates and Random Graphs}, volume = 7965, year = 2013 }

2012 [ nach oben ]

• 
  Doerr, Benjamin; Fouz, Mahmoud; Friedrich, TobiasWhy rumors spread so quickly in social networks. Communications of the ACM 2012: 70-75
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Understanding structural and algorithmic properties of complex networks is an important task, not least because of the huge impact of the internet. Our focus is to analyze how news spreads in social networks. We simulate a simple information spreading process in different network topologies and demonstrate that news spreads much faster in existing social network topologies. We support this finding by analyzing information spreading in the mathematically defined preferential attachment network topology, which is a common model for real-world networks. We prove that here a sublogarithmic time suffices to spread a news to all nodes of the network. All previously studied network topologies need at least a logarithmic time. Surprisingly, we observe that nodes with few neighbors are crucial for the fast dissemination. Social networks like Facebook and Twitter are reshaping the way people take collective actions. They have played a crucial role in the recent uprisings of the 'Arab Spring' and the 'London riots'. It has been argued that the 'instantaneous nature' of these networks influenced the speed at which the events were unfolding [4]. It is quite remarkable that social networks spread news so fast. Both the structure of social networks and the process that distributes the news are not designed with this purpose in mind. On the contrary, they are not designed at all, but have evolved in a random and decentralized manner. So is our view correct that social networks ease the spread of information ("rumors"), and if so, what particular properties of social networks are the reason for this? To answer these questions, we simulate a simple rumor spreading process on several graphs having the structure of existing large social networks. We see, for example, that a rumor started at a random node of the Twitter network in average reaches 45.6 million of the total of 51.2 million members within only eight rounds of communication. We also analyze this process on an abstract model of social networks, the so-called preferential attachment graphs introduced by Baraba si and Albert [3]. In [17], we obtain a mathematical proof that rumors in such networks spread much faster than in many other network topologies-even faster than in networks having a communication link between any two nodes (complete graphs). As an explanation, we observe that nodes of small degree build a short-cut between those having large degree (hubs), which due to their large number of possible communication partners less often talk to each other directly.
  @article{DBLP:journals/cacm/DoerrFF12, abstract = {Understanding structural and algorithmic properties of complex networks is an important task, not least because of the huge impact of the internet. Our focus is to analyze how news spreads in social networks. We simulate a simple information spreading process in different network topologies and demonstrate that news spreads much faster in existing social network topologies. We support this finding by analyzing information spreading in the mathematically defined preferential attachment network topology, which is a common model for real-world networks. We prove that here a sublogarithmic time suffices to spread a news to all nodes of the network. All previously studied network topologies need at least a logarithmic time. Surprisingly, we observe that nodes with few neighbors are crucial for the fast dissemination. Social networks like Facebook and Twitter are reshaping the way people take collective actions. They have played a crucial role in the recent uprisings of the 'Arab Spring' and the 'London riots'. It has been argued that the 'instantaneous nature' of these networks influenced the speed at which the events were unfolding [4]. It is quite remarkable that social networks spread news so fast. Both the structure of social networks and the process that distributes the news are not designed with this purpose in mind. On the contrary, they are not designed at all, but have evolved in a random and decentralized manner. So is our view correct that social networks ease the spread of information ("rumors"), and if so, what particular properties of social networks are the reason for this? To answer these questions, we simulate a simple rumor spreading process on several graphs having the structure of existing large social networks. We see, for example, that a rumor started at a random node of the Twitter network in average reaches 45.6 million of the total of 51.2 million members within only eight rounds of communication. We also analyze this process on an abstract model of social networks, the so-called preferential attachment graphs introduced by Baraba si and Albert [3]. In [17], we obtain a mathematical proof that rumors in such networks spread much faster than in many other network topologies-even faster than in networks having a communication link between any two nodes (complete graphs). As an explanation, we observe that nodes of small degree build a short-cut between those having large degree (hubs), which due to their large number of possible communication partners less often talk to each other directly.}, author = {Doerr, Benjamin and Fouz, Mahmoud and Friedrich, Tobias}, journal = {Communications of the ACM}, keywords = {imported cacm tobiasfriedrich year2012}, number = 6, pages = {70-75}, title = {Why rumors spread so quickly in social networks}, volume = 55, year = 2012 }
• 
  Alcaraz, Nicolas; Friedrich, Tobias; Kötzing, Timo; Krohmer, Anton; Müller, Joachim; Pauling, Josch; Baumbach, JanEfficient Key Pathway Mining: Combining Networks and OMICS Data. Integrative Biology 2012: 756-764
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Systems biology has emerged over the last decade. Driven by the advances in sophisticated measurement technology the research community generated huge molecular biology data sets. This comprises rather static data on the interplay of biological entities, for instance protein-protein interaction network data, as well as quite dynamic data collected for studying the behavior of individual cells or tissues in accordance to changing environmental conditions, such as DNA microarrays or RNA sequencing. Here we bring the two different data types together in order to gain higher level knowledge. We introduce a significantly improved version of the KeyPathwayMiner software framework. Given a biological network modelled as graph and a set of expression studies, KeyPathwayMiner efficiently finds and visualizes connected sub-networks where most components are expressed in most cases. It finds all maximal connected sub-networks where all nodes but k exceptions are expressed in all experimental studies but at least l exceptions. We demonstrate the power of the new approach by comparing it to similar approaches with gene expression data previously used to study Huntington's disease. In addition, we demonstrate KeyPathwayMiner's flexibility and applicability to non-array data by analyzing genome-scale DNA methylation profiles from colorectal tumor cancer patients. KeyPathwayMiner release 2 is available as a Cytoscape plugin and online at http://keypathwayminer.mpi-inf.mpg.de.
  @article{alcaraz2012efficient, abstract = {Systems biology has emerged over the last decade. Driven by the advances in sophisticated measurement technology the research community generated huge molecular biology data sets. This comprises rather static data on the interplay of biological entities, for instance protein-protein interaction network data, as well as quite dynamic data collected for studying the behavior of individual cells or tissues in accordance to changing environmental conditions, such as DNA microarrays or RNA sequencing. Here we bring the two different data types together in order to gain higher level knowledge. We introduce a significantly improved version of the KeyPathwayMiner software framework. Given a biological network modelled as graph and a set of expression studies, KeyPathwayMiner efficiently finds and visualizes connected sub-networks where most components are expressed in most cases. It finds all maximal connected sub-networks where all nodes but k exceptions are expressed in all experimental studies but at least l exceptions. We demonstrate the power of the new approach by comparing it to similar approaches with gene expression data previously used to study Huntington's disease. In addition, we demonstrate KeyPathwayMiner's flexibility and applicability to non-array data by analyzing genome-scale DNA methylation profiles from colorectal tumor cancer patients. KeyPathwayMiner release 2 is available as a Cytoscape plugin and online at http://keypathwayminer.mpi-inf.mpg.de.}, author = {Alcaraz, Nicolas and Friedrich, Tobias and Kötzing, Timo and Krohmer, Anton and Müller, Joachim and Pauling, Josch and Baumbach, Jan}, journal = {Integrative Biology}, keywords = {timokoetzing tobiasfriedrich antonkrohmer year2012 ACO}, number = 7, pages = {756-764}, title = {Efficient Key Pathway Mining: Combining Networks and OMICS Data}, volume = 4, year = 2012 }
• 
  Friedrich, Tobias; Gairing, Martin; Sauerwald, ThomasQuasirandom Load Balancing. SIAM Journal on Computing 2012: 747-771
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We propose a simple distributed algorithm for balancing indivisible tokens on graphs. The algorithm is completely deterministic, though it tries to imitate (and enhance) a randomized algorithm by keeping the accumulated rounding errors as small as possible. Our new algorithm, surprisingly, closely approximates the idealized process (where the tokens are divisible) on important network topologies. On \(d\)-dimensional torus graphs with \(n\) nodes it deviates from the idealized process only by an additive constant. In contrast, the randomized rounding approach of Friedrich and Sauerwald [Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 121-130] can deviate up to \(\Omega(\text{polylog(n))\), and the deterministic algorithm of Rabani, Sinclair, and Wanka [Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 1998, pp. 694-705] has a deviation of \(\Omega(n^{1/d})\). This makes our quasirandom algorithm the first known algorithm for this setting, which is optimal both in time and achieved smoothness. We further show that on the hypercube as well, our algorithm has a smaller deviation from the idealized process than the previous algorithms. To prove these results, we derive several combinatorial and probabilistic results that we believe to be of independent interest. In particular, we show that first-passage probabilities of a random walk on a path with arbitrary weights can be expressed as a convolution of independent geometric probability distributions.
  @article{DBLP:journals/siamcomp/FriedrichGS12, abstract = {We propose a simple distributed algorithm for balancing indivisible tokens on graphs. The algorithm is completely deterministic, though it tries to imitate (and enhance) a randomized algorithm by keeping the accumulated rounding errors as small as possible. Our new algorithm, surprisingly, closely approximates the idealized process (where the tokens are divisible) on important network topologies. On \(d\)-dimensional torus graphs with \(n\) nodes it deviates from the idealized process only by an additive constant. In contrast, the randomized rounding approach of Friedrich and Sauerwald [Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 121-130] can deviate up to \(\Omega(\text{polylog}(n))\), and the deterministic algorithm of Rabani, Sinclair, and Wanka [Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 1998, pp. 694-705] has a deviation of \(\Omega(n^{1/d})\). This makes our quasirandom algorithm the first known algorithm for this setting, which is optimal both in time and achieved smoothness. We further show that on the hypercube as well, our algorithm has a smaller deviation from the idealized process than the previous algorithms. To prove these results, we derive several combinatorial and probabilistic results that we believe to be of independent interest. In particular, we show that first-passage probabilities of a random walk on a path with arbitrary weights can be expressed as a convolution of independent geometric probability distributions.}, author = {Friedrich, Tobias and Gairing, Martin and Sauerwald, Thomas}, journal = {SIAM Journal on Computing}, keywords = {imported sicomp tobiasfriedrich year2012}, number = 4, pages = {747-771}, publisher = {SIAM}, title = {Quasirandom Load Balancing}, volume = 41, year = 2012 }
• 
  Berghammer, Rudolf; Friedrich, Tobias; Neumann, FrankConvergence of Set-Based Multi-Objective Optimization, Indicators and Deteriorative Cycles. Theoretical Computer Science 2012: 2-17
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Multi-objective optimization deals with the task of computing a set of solutions that represents possible trade-offs with respect to a given set of objective functions. Set-based approaches such as evolutionary algorithms are very popular for solving multi-objective optimization problems. Convergence of set-based approaches for multi-objective optimization is essential for their success. We take an order-theoretic view on the convergence of set-based multi-objective optimization and examine how the use of indicator functions can help to direct the search towards Pareto optimal sets. In doing so, we point out that set-based multi-objective optimization working on the dominance relation of search points has to deal with a cyclic behavior that may lead to worsening with respect to the Pareto-dominance relation defined on sets. Later on, we show in which situations well-known binary and unary indicators can help to avoid this cyclic behavior and therefore guarantee convergence of the algorithm. We also study the impact of deteriorative cycles on the runtime behavior and give an example in which they provably slow down the optimization process.
  @article{DBLP:journals/tcs/BerghammerFN12, abstract = {Multi-objective optimization deals with the task of computing a set of solutions that represents possible trade-offs with respect to a given set of objective functions. Set-based approaches such as evolutionary algorithms are very popular for solving multi-objective optimization problems. Convergence of set-based approaches for multi-objective optimization is essential for their success. We take an order-theoretic view on the convergence of set-based multi-objective optimization and examine how the use of indicator functions can help to direct the search towards Pareto optimal sets. In doing so, we point out that set-based multi-objective optimization working on the dominance relation of search points has to deal with a cyclic behavior that may lead to worsening with respect to the Pareto-dominance relation defined on sets. Later on, we show in which situations well-known binary and unary indicators can help to avoid this cyclic behavior and therefore guarantee convergence of the algorithm. We also study the impact of deteriorative cycles on the runtime behavior and give an example in which they provably slow down the optimization process.}, author = {Berghammer, Rudolf and Friedrich, Tobias and Neumann, Frank}, journal = {Theoretical Computer Science}, keywords = {imported tcs rudolfberghammer tobiasfriedrich frankneumann year2012}, pages = {2-17}, title = {Convergence of Set-Based Multi-Objective Optimization, Indicators and Deteriorative Cycles}, volume = 456, year = 2012 }
• 
  Bringmann, Karl; Friedrich, TobiasApproximating the least hypervolume contributor: NP-hard in general, but fast in practice. Theoretical Computer Science 2012: 104-116
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  The hypervolume indicator is an increasingly popular set measure to compare the quality of two Pareto sets. The basic ingredient of most hypervolume indicator based optimization algorithms is the calculation of the hypervolume contribution of single solutions regarding a Pareto set. We show that exact calculation of the hypervolume contribution is \(\#P\)-hard while its approximation is NP-hard. The same holds for the calculation of the minimal contribution. We also prove that it is NP-hard to decide whether a solution has the least hypervolume contribution. Even deciding whether the contribution of a solution is at most \((1 +\epsilon)\) times the minimal contribution is NP-hard. This implies that it is neither possible to efficiently find the least contributing solution (unless P = NP) nor to approximate it (unless NP = BPP). Nevertheless, in the second part of the paper we present a very fast approximation algorithm for this problem. We prove that for arbitrarily given \(\epsilon, \delta > 0\) it calculates a solution with contribution at most \((1+\epsilon)\) times the minimal contribution with probability at least \((1 -\delta)\). Though it cannot run in polynomial time for all instances, it performs extremely fast on various benchmark datasets. The algorithm solves very large problem instances which are intractable for exact algorithms (e.g., 10000 solutions in 100 dimensions) within a few seconds.
  @article{DBLP:journals/tcs/BringmannF12, abstract = {The hypervolume indicator is an increasingly popular set measure to compare the quality of two Pareto sets. The basic ingredient of most hypervolume indicator based optimization algorithms is the calculation of the hypervolume contribution of single solutions regarding a Pareto set. We show that exact calculation of the hypervolume contribution is \(\#P\)-hard while its approximation is NP-hard. The same holds for the calculation of the minimal contribution. We also prove that it is NP-hard to decide whether a solution has the least hypervolume contribution. Even deciding whether the contribution of a solution is at most \((1 +\epsilon)\) times the minimal contribution is NP-hard. This implies that it is neither possible to efficiently find the least contributing solution (unless P = NP) nor to approximate it (unless NP = BPP). Nevertheless, in the second part of the paper we present a very fast approximation algorithm for this problem. We prove that for arbitrarily given \(\epsilon, \delta > 0\) it calculates a solution with contribution at most \((1+\epsilon)\) times the minimal contribution with probability at least \((1 -\delta)\). Though it cannot run in polynomial time for all instances, it performs extremely fast on various benchmark datasets. The algorithm solves very large problem instances which are intractable for exact algorithms (e.g., 10000 solutions in 100 dimensions) within a few seconds.}, author = {Bringmann, Karl and Friedrich, Tobias}, journal = {Theoretical Computer Science}, keywords = {imported tcs tobiasfriedrich year2012}, pages = {104-116}, title = {Approximating the least hypervolume contributor: NP-hard in general, but fast in practice}, volume = 425, year = 2012 }
• 
  Baumbach, Jan; Friedrich, Tobias; Kötzing, Timo; Krohmer, Anton; Müller, Joachim; Pauling, JoschEfficient Algorithms for Extracting Biological Key Pathways with Global Constraints. Genetic and Evolutionary Computation Conference (GECCO) 2012: 169-176
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  The integrated analysis of data of different types and with various interdependencies is one of the major challenges in computational biology. Recently, we developed KeyPathwayMiner, a method that combines biological networks modeled as graphs with disease-specific genetic expression data gained from a set of cases (patients, cell lines, tissues, etc.). We aimed for finding all maximal connected sub-graphs where all nodes but K are expressed in all cases but at most L, i.e. key pathways. Thereby, we combined biological networks with OMICS data, instead of analyzing these data sets in isolation. Here we present an alternative approach that avoids a certain bias towards hub nodes: We now aim for extracting all maximal connected sub-networks where all but at most K nodes are expressed in all cases but in total (!) at most L, i.e. accumulated over all cases and all nodes in a solution. We call this strategy GLONE (global node exceptions); the previous problem we call INES (individual node exceptions). Since finding GLONE-components is computationally hard, we developed an Ant Colony Optimization algorithm and implemented it with the KeyPathwayMiner Cytoscape framework as an alternative to the INES algorithms. KeyPathwayMiner 3.0 now offers both the INES and the GLONE algorithms. It is available as plugin from Cytoscape and online at http://keypathwayminer.mpi-inf.mpg.de.
  @inproceedings{DBLP:conf/gecco/BaumbachFKKMP12, abstract = {The integrated analysis of data of different types and with various interdependencies is one of the major challenges in computational biology. Recently, we developed KeyPathwayMiner, a method that combines biological networks modeled as graphs with disease-specific genetic expression data gained from a set of cases (patients, cell lines, tissues, etc.). We aimed for finding all maximal connected sub-graphs where all nodes but K are expressed in all cases but at most L, i.e. key pathways. Thereby, we combined biological networks with OMICS data, instead of analyzing these data sets in isolation. Here we present an alternative approach that avoids a certain bias towards hub nodes: We now aim for extracting all maximal connected sub-networks where all but at most K nodes are expressed in all cases but in total (!) at most L, i.e. accumulated over all cases and all nodes in a solution. We call this strategy GLONE (global node exceptions); the previous problem we call INES (individual node exceptions). Since finding GLONE-components is computationally hard, we developed an Ant Colony Optimization algorithm and implemented it with the KeyPathwayMiner Cytoscape framework as an alternative to the INES algorithms. KeyPathwayMiner 3.0 now offers both the INES and the GLONE algorithms. It is available as plugin from Cytoscape and online at http://keypathwayminer.mpi-inf.mpg.de.}, author = {Baumbach, Jan and Friedrich, Tobias and Kötzing, Timo and Krohmer, Anton and Müller, Joachim and Pauling, Josch}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {timokoetzing tobiasfriedrich gecco antonkrohmer year2012 ACO}, pages = {169-176}, title = {Efficient Algorithms for Extracting Biological Key Pathways with Global Constraints}, year = 2012 }
• 
  Bringmann, Karl; Friedrich, TobiasConvergence of hypervolume-based archiving algorithms ii: competitiveness. Genetic and Evolutionary Computation Conference (GECCO) 2012: 457-464
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]