Research Seminar (Summer Term 2016)

Organizers

Prof. Dr. Tobias Friedrich, Ralf Rothenberger

Description

A series of talks on current research and interesting topics in algorithm engineering and theoretical computer science. Everyone is welcome to attend talks.

If you want to give a talk about a topic in algorithm engineering or theoretical computer science, please write an e-mail to Prof. Dr. Tobias Friedrich or to Ralf Rothenberger.

Announcements

For announcements of talks, subscribe to our mailing list.

Talks (click on title to show abstract)

Date	Room	Speaker	Title
21.4. 15:15	A-1.1	Martin Krejca	A General View of EDAs Estimation of Distribution Algorithms (EDAs) work by iteratively updating a distribution over the search space with the help of samples from each iteration. We propose a new framework for EDAs that captures the idea of several known optimizers including PBIL, UMDA, λ-MMAS_IB, cGA, and (1, λ)-EA. Our focus is on 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 discuss these features with the help of the functions OneMax and LeadingOnes.
28.4. 15:15	A-1.2	Christian Gießen	Optimal Mutation Rates for the (1+λ) EA We study the (1+λ) EA with mutation probability c/n, where c>0 is a constant, on the OneMax problem. Using an improved variable drift theorem, we show that upper and lower bounds on the expected runtime of the (1+λ) EA obtained from variable drift theorems are at most apart by a small lower order term if the exact drift is known. This reduces the analysis of expected optimization time to finding an exact expression for the drift. We then give an exact closed-form expression for the drift and develop a method to approximate it very efficiently, enabling us to determine approximate optimal mutation rates for the (1+λ) EA for various parameter settings of c and λ and also for moderate sizes of n. This makes the need for potentially lengthy and costly experiments in order to optimize the parameters unnecessary. Interestingly, even for moderate n and not too small λ it turns out that mutation rates up to 10% larger than the asymptotically optimal rate 1/n minimize the expected runtime. However, in absolute terms the expected runtime does not change by much when replacing 1/n with the optimal mutation rate.
12.5. 15:00	A-1.2	Anton Krohmer	Encoding Arguments In this talk, we explore the concept of encoding arguments. In their most basic form, an encoding argument proves an upper bound on the probability of an event using the fact that a uniformly random choice from a set of size n cannot be encoded with fewer than log n bits on average. We show three applications of this technique: Bounding the size of the largest clique in a graph, proving the Lovasz local lemma, and examining percolation on the two-dimensional torus.
18.5. 15:15	H-2.57	Ankit Chauhan	Deterministic model for Real-World Networks It was experimentally observed that the majority of real-world networks are scale free and follow almost power law degree distribution. In my seminar, I will talk about the deterministic conditions for checking whether graph has power law degree distribution. Also, using these deterministic conditions I will give theoretical explanation why some algorithms are more efficient on real-world networks.
19.5. 15:15	A-1.2	Frank Neumann	Packing While Traveling: Mixed Integer Programming for a Class of Nonlinear Knapsack Problems Packing and vehicle routing problems play an important role in the area of supply chain management. We introduce a non-linear knapsack problem that occurs when packing items along a fixed route and taking into account travel time. We investigate constrained and unconstrained versions of the problem and show that both are NP-hard. In order to solve the problems, we provide a pre-processing scheme as well as exact and approximate mixed integer programming (MIP) solutions. Our experimental results show the effectiveness of the MIP solutions and in particular point out that the approximate MIP approach often leads to near optimal results within far less computation time than the exact approach. joint work with Sergey Polyakovskiy
25.5. 17:00	A-1.1	Winnie Poel	Linking spatio-temporal dynamics to the topology: A study of mesoscale network motifs of coupled Stuart-Landau oscillators Motivated by the interdisciplinary use of dynamical networks in the description of complex systems this talk aims to understand the interconnection between the topology of a network of nonlinear oscillators and the spatio-temporal patterns of partial synchronization (PS) and partial amplitude death (PAD) it can exhibit. Both phenomena, synchronization and oscillation quenching, have been extensively investigated on their own but a systematic study of their simultaneous presence in a network could not be found in literature. The talk studies all small (up to five nodes) undirected networks (motifs) with local dynamics given by the generic Stuart-Landau oscillator and a linear symmetric and instantaneous coupling. Its main achievement is the development of socalled `eigensolutions' as a new concept to analytically predict the coexistence and stability of partial in-phase and anti-phase synchronization with partial amplitude death from the network's topology. In this concept the connection between topology and dynamics becomes clearly visible and analytically accessible.
26.5. 15:15	A-1.2	Timo Kötzing	Building Potential Functions for Effective Drift Analysis The method of Drift Analysis is a modern tool for analyzing random processes, in particular also randomized algorithms. Crucial for the application of a drift theorem is always to find a suitable potential function, a mapping of the random process (for example the state of the algorithm) to the real numbers. This is necessary for two reasons: first, drift theorems typically require random processes on the real numbers; second, this mapping can be used to improve the bounds that can be obtained with a drift theorem. In this talk I will show some interesting potential functions that came up in my recent work on multi-valued decision variables to illustrate these methods and to exemplify their power.
2.6. 15:15	A-1.2	Ralf Rothenberger	Phase Transitions for Scale-Free SAT Formulas 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 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 = Θ(n) clauses, and a power-law distributionon 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.
9.6. 15:15	A-1.2	Thomas Bläsius	Hyperbolic Random Graphs: Separators and Treewidth Hyperbolic random graphs share many common properties with complex real-world networks; e.g., small diameter and average distance, large clustering coefficient, and a power-law degree sequence with adjustable exponent β. Thus, when analyzing algorithms for large networks, potentially more realistic results can be achieved by assuming the input to be a hyperbolic random graph of size n. 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). Though many structural properties of hyperbolic random graphs have been studied, almost no algorithmic results are known. 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 they can be expected to have balanced separator hierarchies with separators of size O(n^(3−β)/2), O(log n), and O(1) if 2 < β < 3, β = 3, and 3 < β, respectively. We infer that these graphs have whp a treewidth of O(n^(3−β)/2), O(log² n), and O(log n), respectively. For 2 < β < 3, this matches a known lower bound. This is joint work with Tobias Friedrich and Anton Krohmer.
24.6. 10:00	A-1.1	Dominik Müller	Neuroevolution - Training Artificial Neural Networks with Evolutionary Algorithms In recent years, the field of machine learning is getting more and more attention. Especially, deep learning, which focuses on learning multi-layer artificial neural networks, has helped to achieve ground breaking results in tasks like image classification or speech recognition. While these networks are usually trained using gradient descent with backpropagation there are different learning techniques that can be applied. In this talk I will give a general introduction to neural network. Furthermore, I will show multiple ways to train them using evolutionary algorithms and compare these to the standard of gradient descent with backpropagation.
28.6. 11:00	A-1.1	Franziska Wegner	Algorithms in Control Systems and Power Grids Smart grids is a young research topic including divers areas apart from computer science like economic sciences, electrical engineering and legal sciences. It comprises the control of the power grid, i.e., energy production, energy storage, consumer and the transmission network between them, and the data collection, processing, analyses and usage. I have been working in “energy informatics”, which targets the redesign of the whole power grid and automation of processes in all parts of the power grid focusing on computer science problem formulations and solutions. Graph-theoretic approaches to solve problems in power grids are currently almost nonexistent in literature. Thus, I have done a first investigation to examine possibilities of graph-theoretic approaches and algorithm engineering to tackle problems in the today’s and future power grids.
28.6. 13:30	A-2.1	Jan Ladleif, David Schumann	Algorithmic Gems Jan Ladleif: "On Computable Numbers, with an Application to the Entscheidungsproblem" by Alan Turing David Schumann: "New Directions in Cryptography" by Whitfield Diffie and Martin Hellman
29.6. 11:00	H-E.52	Pascal Lenzner	An explorative journey into Evolutionary Game Theory Evolutionary Game Theory is a classical subfield of Game Theory which focusses on the application of game-theoretic ideas to evolving populations of lifeforms. This talk will contain a brief introduction to some core-concepts of Evolutionary Game Theory and an exploration of its connections to Algorithmic Game Theory and Evolutionary Computation.
12.7. 11:30	A-2.1	Vahan Mkrtchyan	Partial vertex covers and clusterings of graphs We will consider the partial vertex cover problem in the class of bipartite graphs. We will also consider a clustering problem on directed acyclic graphs. Our main goal is to address these problems from the perspective of exact and approximate solvability. We will present some new results in these directions.
13.7. 16:00	A-1.1	Martin Krejca	EDAs cannot be Balanced and Stable 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, λ-MMAS_IB, cGA, and (1,λ)-EA. Our focus is on analyzing two core features of EDAs: abalanced 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 Ο(n log n).
13.7. 16:30	A-1.1	Timo Kötzing	The Right Mutation Strength for Multi-Valued Decision Variables The most common representation in evolutionary computation are bit strings. This is ideal to model binary decision variables, but less useful for variables taking more values. With very little theoretical work existing on how to use evolutionary algorithms for such optimization problems, we study the run time of simple evolutionary algorithms on a variety of OneMax-like functions defined over Ω = {0,1,...,r-1}ⁿ. For such problems we see a crucial difference on how we extend the standard-bit mutation operator to these multi-valued domains. While it is natural to select each position of the solution vector to be changed independently with probability 1/n, there are various ways to then change such a position. If we change each selected position to a random value different from the original one, we get an expected run time of θ(nr log n). If we change each selected position by either +i or -i (random choice), the optimization time reduces to θ(nr+nlog n). If we use a random mutation strength i ∈ {1,...,r-1}ⁿ with probability inversely proportional to i and change the selected position by either +i or -i (random choice), then the optimization time becomes θ(n log(r)(log(n)+log(r)))ing down the dependence on r from linear to polylogarithmic.
13.7. 17:00	A-1.1	Martin Schirneck	Fast Building Block Assembly by Majority Vote Crossover 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 + δ, we require only Ο(log δ^-1 + 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 Ο(n log n)) even for jump sizes as large as Ο(n^{1/2 - ε}). 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.
13.7. 17:30	A-1.1	Andrew Sutton	Escaping Local Optima with Diversity - Mechanisms and Crossover 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 (μ + 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 = Ο(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 μ, 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 μ: Ο(n^k-1) for duplicate elimination/minimisation, Ο(n²log n) for maximising the convex hull, Ο(n log n) for det. crowding (assuming p_c = k/n), Ο(n log n) for maximising the Hamming distance, Ο(n log n) for fitness sharing, Ο(n log n) for the single-receiver island model. This proves a sizeable advantage of all variants of the (μ + 1) GA compared to the (1+1) EA, which requires θ(n^k). In a short empirical study we confirm that the asymptotic differences can also be observed experimentally.
28.7. 13:30	A-1.1	Tobias Arndt, Danijar Hafner, Tobias Kellermeier, Simon Krogmann, Armin Razmdjou	Presentation of Bachelor Theses
17.8. 13:30	A-2.1	Thomas Kellermeier	Probabilistic Routing for On-Street Parking Search An estimated 30% of urban traffic is caused by search for parking spots. Suggesting routes along highly probable parking spots could reduce traffic. 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.
18.8. 15:15	A-1.2	Tobias Friedrich	Scale-Free Networks, Hyperbolic Geometry, and Efficient Algorithms 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.
29.8 13:30	A-2.1	Per Kristian Lehre	Self-adapting Evolutionary Algorithms Evolutionary algorithms (EAs) are optimisation methods inspired by the principles of natural selection. The parameters of the optimisation problem are encoded in artificial genomes. Populations of genomes are then evolved over a number of generations subject to natural selection and mutation. EAs have been successfully applied to many domains, such as search based software engineering. The effectiveness of Evolutionary Algorithms often depends on appropriate settings of their parameters for the optimisation problem at hand, such as the rate of mutation. Due to the high cost of manual tuning of the parameters, there have been several efforts in developing schemes adapting the parameters automatically to the problem. One appealing idea, so-called self-adaptation, is to let the parameter settings of the EA themselves be subject to natural selection and mutation. In this talk, we provide theoretical evidence demonstrating that when executed correctly, this bold idea can be highly effective. In particular, we describe settings where self-adapting evolutionary algorithm can fine-tune mutation rates appropriately, and where fixed mutation rates settings fail. The work will be presented at the PPSN conference in Edingburgh in September 2016. Joint work with Duc-Cuong Dang.
30.8. 11:30	A-2.1	Pedro Maristany de las Casas	Cost-Minimal Aircraft Trajectories While there are many physical and operational restrictions influencing the feasibility of a commercial flight trajectory, the costs for an airline for flying along such a route are the sum of fuel- and overflight-costs. Each region/country is allowed to choose its own cost-model to charge fees to airlines overflying its airspace. Thus finding a cost-minimal route between two airports results in a bicriterial optimization-task, in which both cost-functions influence each other in a way that changes from airspace to airspace. E.g.: european countries charge overflight-costs according to the distance between entry- and exit-point, regardless of the flown distance within the airspace itself. We will see an overview of the complexity of the described problem depending on the different cost-models and geographical distribution of airspaces. After this theoretical part, we will discuss how today's most relevant cost-models can be handled using polynomial algorithms. However the runtime of these algorithms does not meet the requirements of the airline industry, which motivates the last part of the talk: how to connect fuel- and overflight-costs in a consistent way, such that the solution of the new monocriterial shortest-path problem is a good approximation to the optimal original route.
6.9. 13:30	A-1.2	Anna Melnichenko	On Selfish Creation of Robust Networks Networks are everywhere and we crucially rely on their functionality. And robustness is one of the key properties of nowadays networks. To investigate this phenomenon we present the first simple model for selfish network creation which explicitly incorporates agents striving for a central position in the network while at the same time protecting themselves against random edge-failure. We show that networks in our model are diverse and we prove the versatility of our model by adapting various properties and techniques from the non-robust versions. Moreover, we analyze the computational hardness of finding best possible strategies and investigate the game dynamics of our model.
6.9. 15:15	A-2.1	Sebastian Wild	Dual-Pivot Quicksort and Beyond [slides] Quicksort is one of most well-understood algorithms both theoretically and in practice. An implementation of Quicksort is part of almost every programming library. After excessive experimenting and engineering in the 1970s, the tuning efforts seemed to have converged to a stable state; but now, there is again excitement within the algorithms community, triggered by the success of a new dual-pivot Quicksort used in the Java 7 runtime library. I will introduce the new algorithm and present analytical evidence for my hypothesis why (a) dual-pivot Quicksort is faster than the previously used (classic) Quicksort and (b) why this basic improvement was not already found much earlier. We will then explore the potential of using even more pivots. In passing, I try to give the intuition behind my favorite mathematical tools for the analysis of algorithms.
7.9. 13:30	A-1.2	diverse	Best of ALGO 2016 A short review of the best talks from this year's ALGO by our group's attendees.
28.9. 13:30	A-2.1	Danny Hermelin	Loss minimization for geometric scheduling problems In geometric scheduling, jobs are represented as geometric objects, and two jobs can be simultaneously scheduled together (on the same machine) if and only if their corresponding geometric objects do not intersect. The classical example in this area is interval scheduling where the intervals represent the timeline of each job, and two jobs can be simultaneously scheduled if and only if their timelines are disjoint. In loss minimization scheduling, our goal is to remove the minimum (weight or size) subset of jobs so that the remaining jobs can be scheduled together. Apart from the interval case, most loss minimization variants of geometric scheduling problems are NP-hard. In this talk I will present a generic framework for deriving efficient approximation algorithms for such problems, and exemplify this framework on three concrete examples.
5.10. 13:30	A-1.1	Andreas Göbel	Amplifiers for the Moran process The Moran process, as studied by Lieberman, Hauert and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlying graph where individuals correspond to vertices. Initially, one vertex (chosen uniformly at random) possesses a mutation, with fitness r > 1. All other individuals have fitness 1. During each step of the algorithm, an individual is chosen with probability proportional to its fitness, and its state (mutant or non-mutant) is passed on to an out-neighbour which is chosen uniformly at random. If the underlying graph is strongly connected then the algorithm will eventually reach fixation, in which all individuals are mutants, or extinction, in which no individuals are mutants. An infinite family of directed graphs is said to be strongly amplifying if, for every r > 1, the extinction probability tends to 0 as the number of vertices increases. Strong amplification is a rather surprising property — it means that in such graphs, the fixation probability of a uniformly- placed initial mutant tends to 1 even though the initial mutant only has a fixed selective advantage of r > 1 (independently of n). The name “strongly amplifying” comes from the fact that this selective advantage is “amplified”. Strong amplifiers have received quite a bit of attention, and Lieberman et al. proposed two potentially strongly-amplifying families — superstars and metafunnels. Heuristic arguments have been published, arguing that there are infinite families of superstars that are strongly amplifying. The same has been claimed for metafunnels. In this paper, we give the first rigorous proof that there is an infinite family of directed graphs that is strongly amplifying. We call the graphs in the family “megastars”. When the algorithm is run on an n-vertex graph in this family, starting with a uniformly-chosen mutant, the extinction probability is roughly n^−1/2 (up to logarithmic factors). We prove that all infinite families of superstars and metafunnels have larger extinction probabilities (as a function of n). Finally, we prove that our analysis of megastars is fairly tight — there is no infinite family of megastars such that the Moran algorithm gives a smaller extinction probability (up to logarithmic factors). This is joint work with Andreas Galanis, Leslie Ann Goldberg, John Lapinskas and David Richerby.

Research Seminar (Summer Term 2016)

Organizers

Description

Announcements

Talks (click on title to show abstract)

Algorithm Engineering

News

13.09.2024 | Best Paper awarded at IPEC

11.09.2024 | PhD awarded to Philipp Fischbeck

05.09.2024 | Two Papers accepted at RANDOM and ESA

01.08.2024 | PhD awarded to Gregor Lagodzinski

17.07.2024 | Two Papers accepted at FOCS and PPSN

31.05.2024 | Two Papers accepted at SAND and IWOCA

Contact

Apply