When dealing with optimization of real-world numerical models, it is often unfeasible to perform correlation via direct methods. This is the case of the thermal analysis of bespoke electro-mechanical systems for extreme harsh environments, such as actuators and wireless sensors. Evolutionary Algorithms (EAs) are generic population-based optimization algorithms, useful to approach such problems.

Even though in the last decade theoretical results have been presented regarding the running time of EAs, there is still little understanding of the interplay between the operators of randomized search heuristics and explicit noise-handling techniques, such as statistical resampling. 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-off between noise reduction and the computational cost of resampling. We 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 observe how the optimal parameter depends on the noise intensity for the different algorithms. 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. We find that EDA-like algorithms require no resampling, and can handle noise implicitly. Interestingly, we observe that all tested algorithms exhibit high variance for increasing noise. We plan to combine the latter observation with rigorous analysis to define the optimal re-start strategy, with the hope of further improving performance.

In recent years, there is a lot of attention on machine learning. More specifically, deep learning achieved state of the art results in multiple fields. Deep learning uses artificial neural networks with many layers, which are loosely inspired by biological neural networks. These networks can be trained to solve a large variety of tasks. The current standard of training artificial neural networks is stochastic gradient descent through backpropagation. However, there are many other known optimization techniques, such as evolutionary algorithms, which are inspired by biological evolution. The combination of evolutionary algorithms and artificial neural networks is called neuroevolution.

In this talk I will give a brief introduction to the concepts of machine learning, artificial neural networks and evolutionary algorithms. Furthermore, I will shortly explain the set of used neuroevolution algorithms. The main part of the talk will discuss the results of these algorithms on multiple classification and reinforcement learning tasks and compare them to the current standard of stochastic gradient descent. I will conclude the talk with the strengths and weaknesses of the tested neuroevolution algorithms and discuss possible improvements for neuroevolution and the benchmark.

Ipe is a drawing editor for creating figures in PDF or (encapsulated) Postscript format. It supports making small figures for inclusion into LaTeX-documents as well as making multi-page PDF presentations that can be shown on-line with Acrobat Reader.

One of the main applications of Markov chains is to simulate random sampling from a specific probability distribution. Such sampling methods are required in many probabilistic algorithms for a wide variety of problems. The efficieny of the resulting algorithms depends crucially on the mixing time of the underlying Markov chain.

Estimates for the mixing rate focus on the second-largest eigenvalue in absolute value of the transition matrix of a Markov chain. There are several analytic tools for estimating the mixing time, which have been successfully applied to simple Markov chains with a regular structure. The method of canonical paths as well as multicommodity flows are techniques that can also be applied to more complex Markov chains. The graph of the Markov chain is interpreted as a flow network. The idea is to transport flow quantities between each ordered pair of distinct states so that no edge is „overloaded“. If the choice of paths have to overload one or more edges this signals slow convergence and great mixing time.

Both methods can be formulated as a linear program. However, there are exponentially many path variables. This poses a real challenge because they can not be traded except for very small graphs. Column generation makes it possible to start with a small subset of variables and add additional variables only if they are actually needed.

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 = Θ(n) clauses, and a power-law distribution on the variable occurrences with exponent β. We observe a satisfiability threshold at β = (2k −1)/(k −1). This threshold is tight in the sense that instances with β ≤ (2k −1)/(k −1)−ε for any constant ε > 0 are unsatisfiable with high probability (w. h. p.). For β ≥ (2k−1)/(k−1)+ε 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 β.

This is joint work with Tobias Friedrich, Anton Krohmer, Thomas Sauerwald and Andrew Sutton.

Optimization problems are everywhere: whether we want to find a fast way to work or whether expensive industrial machinery needs to be tuned to give optimal performance, we have it in our hands to save time and or money.

Typical optimization problems come with many side constraints and contradictory goals, sometimes measuring quality can only be achieved by simulations. Only rarely can one find a straightforward specific algorithm, such as, for example, Dijkstra's Algorithm for finding shortest paths. Sometimes it is possible to remodel a problem as a linear program (LP) or in terms of satisfiability (SAT). For these types of problems strong solvers are known; however, in most cases problems are too hard to be easily tractable. This is when black-box optimization proves beneficial: these general-purpose optimizers can be applied to any given problem without requiring problem-specific information. This latter approach has the significant advantage that development costs are very low, while applicability is very high. Understanding these algorithms is a challenge of ongoing research, providing insights which lead to new and more powerful optimization algorithms.

In this talk we will review this evolution of problem solving and show how modern heuristics can give very efficient algorithms. We discuss examples where optimization algorithms were applied very successfully, both in research domains (such as bio-informatics or human-computer interaction) and industrial domains (such as path finding and design optimization).

Large real-world networks typically follow a power-law degree distribution. To study such networks, numerous random graph models have been proposed. However, real networks are not drawn at random. In fact, the behavior of real-world networks and random graph models can be completely opposite, depending on the property we look at. 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 distri- bution of degrees 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 like transitive closure, maximum matching, determinant, PageRank, matrix inverse, counting triangles and maximum clique.

We complement the work of Brach et al. by showing that a number of well-studied random graph classes exhibit both aforementioned 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, Geometric Inhomogeneous Random Graphs and Hyperbolic Random Graphs. All results of Brach et al. therefore also hold with high probability for these random graph classes.

In the second part of this work we study three classical NP-hard combinatorial optimization problems on deterministic PLB networks. It is known that on general graphs with maximum degree ∆, a greedy algorithm, which chooses nodes in the order of their degree, only achieves a Ω(ln ∆)-approximation for Minimum Vertex Cover and Minimum Dominating Set, and a Ω(∆)-approximation for Maximum Independent Set. We prove that the PLB-U property suffices such that the greedy approach achieves a constant-factor approximation for all three problems. We also show that a PTAS cannot be expected, even if all three PLB-properties hold. For all three combinatorial optimization problems we prove APX-completeness for graphs with PLB-U, PLB-L and PLB-N property.

Noise is pervasive in real-world optimization, but there is still little understanding of the interplay between the operators of randomised search heuristics and explicit noise-handling techniques such as statistical resampling. In this paper, we report several statistical models and theoretical results that help to clarify this interplay for a collection of randomised search heuristics on a noisy function.

We consider the optimization of pseudo-Boolean functions under additive posterior Gaussian noise and explore the trade-off between noise reduction and 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, and an ant colony optimisation algorithm. We then observe how the optimal parameter depends on the noise intensity for the different algorithms. Finally, we perform experiments to locate the point where resampling costs more than it is worth in terms of running time. We find that the mutation-only EA requires the highest number of resamples to obtain the best speed-up, whereas using 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 in this setting implicitly.

In this talk, we will discuss the complexity of some fundamental polynomial-time problems using the lens of conditional lower bounds. In particular, we address the question why, despite much effort, no algorithm is known that determines a longest common subsequence (LCS) of two strings x and y in time O((|x| \cdot |y|)^{1-\eps}). We will discuss recent work that gives a conditional answer: finding such a subquadratic algorithm is impossible without refuting the Strong Exponential Time Hypothesis (SETH) [Abboud, Backurs, Vassilevska-Williams FOCS'15; Bringmann, K\"unnemann FOCS'15].

However, notwithstanding the lack of improvement in the worst case, a long and successful line of research identified and exploited parameters of the input strings, achieving strongly subquadratic running times for highly relevant special cases, e.g., comparing large, but similar files (diff). The questions arise whether (i) the best known LCS algorithms have an optimal parameter dependence (up to lower order factors, assuming SETH) and whether (ii) some parameter constellations admit faster algorithms than currently known (without refuting SETH). We answer these questions by providing a systematic study of the (conditional) multivariate complexity of LCS: we take into account all parameters previously discussed in the LCS literature and give an optimal running time bound (up to lower order factors and assuming SETH) in these parameters.

A set A of natural numbers is said to be sum-free if it does not contain x, y and z such that x + y = z. Sum-free sets have been studied extensively in additive combinatorics (Paul Erdős was particularly interested in these sets) but algorithmic questions relating to sum-free sets have thus far received very little attention. We consider the problem, given a set A, of determining whether A contains a sum-free subset of size at least k. We show that this problem is NP-complete in general, but is tractable with respect to certain parameterizations; in the cases where the decision problem is tractable, we also consider the complexity of counting all sum-free subsets of size exactly k.

This is joint work with Andrew Treglown (University of Birmingham).

Many computational problems are NP-hard and are therefore generally believed not to be solvable in polynomial time. Additional assumptions on the inputs are necessary to solve such problems efficiently. Two typical approaches are (i) parameterized complexity where we assume that a certain parameter of the instances is small, and (ii) average-case complexity where we assume a certain probability distribution on the inputs. There is a vast literature on both approaches, but very little about their intersection. Nevertheless, combining these two approaches seems natural and potentially useful in practice. The talk presents the following line of results:

• A hierarchy of parameterized average-case complexity classes [2].
• The W[1]-complete problem k-Clique drops to an average-case analog of FPT for homogeneous Erdős-Rényi random graphs of all densities [2] and for inhomogeneous Chung-Lu random graphs with power-law exponent γ > 2 [4, 5].
• The bounded search tree paradigm allows analyzing average-case run times for a very relaxed graph model that only assumes stochastic independence of the edges. This is demonstrated for the parameterized problems k-Clique, Vertex Cover, and Hitting Set [unpublished].
• The Edge Cover Problem has no kernel of subexponential size in the worst- case (unless P=NP). We study a well-known set of reduction rules and prove that random intersection graphs are reduced completely by these rules [3].
• The geometric problem of computing the hypervolume indicator is W[1]- hard in the worst-case, but can be solved in expected FPT-time if the input is distributed at random on a d-dimensional simplex [1].

References

[1] Karl Bringmann and Tobias Friedrich. Parameterized average-case complex- ity of the hypervolume indicator. In Genetic and Evolutionary Computation Conference (GECCO), pages 575–582. ACM, 2013.

[2] Nikolaos Fountoulakis, Tobias Friedrich, and Danny Hermelin. On the average-case complexity of parameterized clique. Theoretical Computer Science, 576:18-29, 2015.

[3] Tobias Friedrich and Christian Hercher. On the kernel size of clique cover reductions for random intersection graphs. Journal of Discrete Algorithms, 34:128-136, 2015.

[4] Tobias Friedrich and Anton Krohmer. Parameterized clique on scale-free networks. In International Symposium on Algorithms and Computation (ISAAC), volume 7676 of Lecture Notes in Computer Science, pages 659-668. Springer, 2012.

[5] Tobias Friedrich and Anton Krohmer. Parameterized clique on inhomogeneous random graphs. Discrete Applied Mathematics, 184:130-138, 2015.