Conference: International Conference on Intelligent Data Engineering and Automated Learning 2023

Speaker: Sarel Cohen

Abstract:In large cities, a considerable amount of traffic congestion is caused by drivers actively looking for unoccupied parking spots, leading to reduced average velocities on the streets, reduced air quality, and an increase in sound pollution. A parking space map helps drivers to find vacant parking spaces more easily and helps minimising search time, fuel and energy consumption. We introduce a machine learning framework to detect occupied and empty parking spaces using airborne images. Our approach is based on three steps. First, we present novel ways to include observations from outside the visible spectrum (RGB) to delineate vegetation in urban environments. We remove roads on the images to minimise interference from moving vehicles and use a mask-RCNN to detect vacant parking spaces on the processed images. Third, we propose to use a logistic regression model (LRM) as a post-processing step in order to better filter true positives. From our experiments we conclude that Red-Green-NIR (RG-NIR) spectrum contains the most important information for training Faster-Region-based Convolutional Neural Network with Feature Pyramid Network (RCNN FPN) for vehicle detection. Our empirical studies on aerial images of Berlin, Germany, show that our framework can be employed successfully to create trustworthy parking space maps. Our best model obtain an accuracy of 97.7% and an F1-score of 0.645 for detecting both occupied and vacant on-street packing.

This is joint work with Bashini K. Mahaarachchi, Bodo Bookhagen, Vanja Doskoč and Tobias Friedrich.

Conference: Symposium on Document Engineering 2022

Speaker: Philipp Hildebrandt

Abstract:Recognizing disturbed text in real-life images is a difficult problem, as information that is missing due to low resolution or out-of-focus text has to be recreated. Combining text super-resolution and optical character recognition deep learning models can be a valuable tool to enlarge and enhance text images for better readability, as well as recognize text automatically afterwards. We achieve improved peak signal-to-noise ratio and text recognition accuracy scores over a state-of-the-art text super-resolution model TBSRN on the real-world low-resolution dataset TextZoom while having a smaller theoretical model size due to the usage of quantization techniques. In addition, we show how different training strategies influence the performance of the resulting model.

This is joint work with Maximilian Schulze, Sarel Cohen, Vanja Doskoč, Raid Saabni and Tobias Friedrich.

Conference: Innovations in Theoretical Computer Science Conference 2022

Speaker: Martin Schirneck

Abstract:A distance sensitivity oracle (DSO) with sensitivity \(f\) is a data structure that reports the pair-wise distances in a given graph, even when up to \(f\) specified edges fail. A parameterized decision problem is said to be fixed-parameter tractable (FPT) if, on \(n\)-vertex graphs with parameter \(k\), the problem can be solved in time \(O(g(k) \cdot poly(n))\) for some function \(g\). We combine both ideas and introduce sensitivity oracles for FPT graph problems. Such data structures preprocess the input in time \(O(g(f,k) \cdot poly(n))\) and report the answer to the graph problem in the presence of up to \(f\) edge failures in time significantly faster than merely re-running the fastest known FPT algorithm on the respective subgraph. As examples, we present multiple oracles for the \(k\)-Path and the Vertex Cover problem, respectively. Our solutions involve careful trade-offs between the parameters \(f\) and \(k\), the space requirement, preprocessing time, as well as the query time.

This is joint work with Davide Bilò, Katrin Casel, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Gregor Lagodzinski, and Simon Wietheger.

Conference: European Symposium on Algorithms 2021

Speaker: Maximilian Katzmann

Abstract: Finding a minimum vertex cover in a network is a fundamental NP-complete graph problem. One way to deal with its computational hardness, is to trade the qualitative performance of an algorithm (allowing non-optimal outputs) for an improved running time. For the vertex cover problem, there is a gap between theory and practice when it comes to understanding this tradeoff. On the one hand, it is known that it is NP-hard to approximate a minimum vertex cover within a factor of \(\sqrt{2}\). On the other hand, a simple greedy algorithm yields close to optimal approximations in practice.
A promising approach towards understanding this discrepancy is to recognize the differences between theoretical worst-case instances and real-world networks. Following this direction, we close the gap between theory and practice by providing an algorithm that efficiently computes nearly optimal vertex cover approximations on hyperbolic random graphs; a network model that closely resembles real-world networks in terms of degree distribution, clustering, and the small-world property. More precisely, our algorithm computes a \((1 + o(1))\)-approximation, asymptotically almost surely, and has a running time of \(\mathcal{O}(m \log(n))\).
The proposed algorithm is an adaption of the successful greedy approach, enhanced with a procedure that improves on parts of the graph where greedy is not optimal. This makes it possible to introduce a parameter that can be used to tune the tradeoff between approximation performance and running time. Our empirical evaluation on real-world networks shows that this allows for improving over the near-optimal results of the greedy approach.

This is joined work with Thomas Bläsius and Tobias Friedrich.

Conference: European Symposium on Algorithms 2021

Speaker: Martin Schirneck

Abstract: A single-source distance sensitivity oracle (single-source DSO) preprocesses a given graph \(G\) with a distinguished source vertex \(s\) into a data structure. When queried with a target vertex \(t\) and an edge \(e\), the structure reports the replacement distance \(d_{G-e}(s,t)\) in case \(e\) fails. In the closely related single-source replacement paths (SSRP) problem, we are given \(G\) and \(s\) and have to enumerate all distances \(d_{G-e}(s,t)\).
We present deterministic single-source DSOs for undirected graphs with \(\widetilde{O}(1)\) query time. For unweighted graphs, we give a combinatorial preprocessing algorithm running in time \(\widetilde{O}(m \sqrt{n} + n^2)\), resulting in a data structure taking \(O(n^{3/2})\) space. For graphs with integer edge weights in the range \([1,M]\) and when using fast matrix multiplication, we get a preprocessing time of \(\widetilde{O}(Mn^{\omega})\), and the oracle takes \(O(M^{1/2}n^{3/2})\) space. Here, \(\omega < 2.373\) denotes the matrix multiplication exponent. Both preprocessing times improve over previous constructions by polynomial factors. We further show that the space requirement is optimal up to the size of a machine word. Finally, we give a randomized preprocessing algorithm that breaks the quadratic barrier on sufficiently sparse graphs.
We obtain our oracles by derandomizing known SSRP algorithms by Chechik & Cohen [SODA'19] as well as Grandoni & Vassilevska Williams [FOCS'12] and combining them with a novel compression scheme for replacement distances.

This is joined work with Davide Bilò, Sarel Cohen and Tobias Friedrich.

Conference: European Symposium on Algorithms 2021

Speaker: Ziena Zeif

Abstract: We introduce the balanced crown decomposition that captures the structure imposed on graphs by their connected induced subgraphs of a given size. Such subgraphs are a popular modeling tool in various application areas, where the non-local nature of the connectivity condition usually results in very challenging algorithmic tasks. The balanced crown decomposition is a combination of a crown decomposition and a balanced partition which makes it applicable to graph editing as well as graph packing and partitioning problems. We illustrate this by deriving improved approximation algorithms and kernelization for a variety of such problems.
In particular, through this structure, we obtain the first constant-factor approximation for the Balanced Connected Partition (BCP) problem, where the task is to partition a vertex-weighted graph into k connected components of approximately equal weight. We derive a 3-approximation for the two most commonly used objectives of maximizing the weight of the lightest component or minimizing the weight of the heaviest component.

This is joined work with Katrin Casel, Tobias Friedrich, Davis Issac and Aikaterini Niklanovits.

Conference: World Congress of the Game Theory Society 2021

Speaker: Anna Melnichenko

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 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.

This is joined work with Hagen Echzell, Tobias Friedrich and Pascal Lenzner.

Conference: World Congress of the Game Theory Society 2021

Speaker: Louise Molitor

Abstract: Residential segregation is a wide-spread phenomenon that can be observed in almost every major city. In these urban areas residents with different racial or socioeconomic background tend to form homogeneous clusters. Schelling’s famous agent-based model for residential segregation explains how such clusters can form even if all agents are tolerant, i.e., if they agree to live in mixed neighborhoods. For segregation to occur, all it needs is a slight bias towards agents preferring similar neighbors. Very recently, Schelling’s model has been investigated from a game-theoretic point of view with selfish agents that strategically select their residential location. In these games, agents can improve on their current location by performing a location swap with another agent who is willing to swap. We significantly deepen these investigations by studying the influence of the underlying topology modeling the residential area on the existence of equilibria, the Price of Anarchy and on the dynamic properties of the resulting strategic multi-agent system. Moreover, as a new conceptual contribution, we also consider the influence of locality, i.e., if the location swaps are restricted to swaps of neighboring agents. We give improved almost tight bounds on the Price of Anarchy for arbitrary underlying graphs and we present (almost) tight bounds for regular graphs, paths and cycles. Moreover, we give almost tight bounds for grids, which are commonly used in empirical studies. For grids we also show that locality has a severe impact on the game dynamics.

This is joined work with Davide Bilò, Vittorio Bilò and Pascal Lenzner.

Conference: The Genetic and Evolutionary Computation Conference 2021

Speaker: Maximilian Böther

Abstract: Traffic congestion is a major issue that can be solved by suggesting drivers alternative routes they are willing to take. This concept has been formalized as a strategic routing problem in which a single alternative route is suggested to an existing one. We extend this formalization and introduce the Multiple-Routes problem, which is given a start and destination and aims at finding up to n different routes that the drivers strategically disperse over, minimizing the overall travel time of the system. Due to the NP-hard nature of the problem, we introduce the Multiple-Routes evolutionary algorithm (MREA) as a heuristic solver. We study several mutation and crossover operators and evaluate them on real-world data of Berlin, Germany. We find that a combination of all operators yields the best result, improving the overall travel time by a factor between 1.8 and 3, in the median, compared to all drivers taking the fastest route. For the base case n = 2, we compare our MREA to the highly tailored optimal solver by Bläsius et al. [ATMOS 2020] and show that, in the median, our approach finds solutions of quality at least 99.69 % of an optimal solution while only requiring 40 % of the time.

This is joined work with Philipp Fischbeck, Tobias Friedrich, Martin S. Krejca, Louise Molitor and Leon Schiller.

Conference: The Genetic and Evolutionary Computation Conference 2021

Speaker: Timo Kötzing

Abstract: One of the first and easy to use techniques for proving run time bounds for evolutionary algorithms is the so-called method of fitness levels by Wegener. It uses a partition of the search space into a sequence of levels which are traversed by the algorithm in increasing order, possibly skipping levels. An easy, but often strong upper bound for the run time can then be derived by adding the reciprocals of the probabilities to leave the levels (or upper bounds for these). Unfortunately, a similarly effective method for proving lower bounds has not yet been established. The strongest such method, proposed by Sudholt (2013), requires a careful choice of the viscosity parameters \(\gamma_{i,j}\), \(0 \le i < j \le n\).
In this paper we present two new variants of the method, one for upper and one for lower bounds. Besides the level leaving probabilities, they only rely on the probabilities that levels are visited at all. We show that these can be computed or estimated without greater difficulties and apply our method to reprove the following known results in an easy and natural way. (i) The precise run time of the (1+1) EA on LeadingOnes. (ii) A lower bound for the run time of the (1+1) EA on OneMax, tight apart from an \(O(n)\) term. (iii) A lower bound for the run time of the (1+1) EA on long \(k\)-paths.

This is joined work with Benjamin Doerr.

Conference: International Colloquium on Automata, Languages and Programming 2021

Speaker: Gregor Lagodzinski

Abstract: We study the problem of counting the number of homomorphisms from an input graph \(G\) to a fixed (quantum) graph \(\bar{H}\) in any finite field of prime order \(\mathbb{Z}_p\). The subproblem with graph \(H\) was introduced by Faben and Jerrum [ToC'15] and its complexity is still uncharacterised despite active research, e.g. the very recent work of Focke, Goldberg, Roth, and Zivný [SODA'21]. Our contribution is threefold.
First, we introduce the study of quantum graphs to the study of modular counting homomorphisms. We show that the complexity for a quantum graph \(\bar{H}\) collapses to the complexity criteria found at dimension 1: graphs. Second, in order to prove cases of intractability we establish a further reduction to the study of bipartite graphs. Lastly, we establish a dichotomy for all bipartite \((K_{3,3}\setminus\{e\}, {domino}))\)-free graphs by a thorough structural study incorporating both local and global arguments. This result subsumes all results on bipartite graphs known for all prime moduli and extends them significantly. Even for the subproblem with \(p=2\) this establishes new results.

This is joined work with Andreas Göbel, Katrin Casel and Tobias Friedrich.

Conference: International Colloquium on Automata, Languages and Programming 2021

Speaker: Marcus Pappik

Abstract: The hard-sphere model is one of the most extensively studied models in statistical physics. It describes the continuous distribution of spherical particles, governed by hard-core interactions. An important quantity of this model is the normalizing factor of this distribution, called the partition function. We propose a Markov chain Monte Carlo algorithm for approximating the grand-canonical partition function of the hard-sphere model in \(d\) dimensions. Up to a fugacity of \( \lambda < \text{e}/2^d\), the runtime of our algorithm is polynomial in the volume of the system. This covers the entire known real-valued regime for the uniqueness of the Gibbs measure.
Key to our approach is to define a discretization that closely approximates the partition function of the continuous model. This results in a discrete hard-core instance that is exponential in the size of the initial hard-sphere model. Our approximation bound follows directly from the correlation decay threshold of an infinite regular tree with degree equal to the maximum degree of our discretization. To cope with the exponential blow-up of the discrete instance we use clique dynamics, a Markov chain that was recently introduced in the setting of abstract polymer models. We prove rapid mixing of clique dynamics up to the tree threshold of the univariate hard-core model. This is achieved by relating clique dynamics to block dynamics and adapting the spectral expansion method, which was recently used to bound the mixing time of Glauber dynamics within the same parameter regime.

This is joined work with Tobias Friedrich, Andreas Göbel and Martin S. Krejca.

Conference: International Joint Conference on Artificial Intelligence 2021

Speaker: Simon Krogmann

Abstract: We consider non-cooperative facility location games where both facilities and clients act strategically and heavily influence each other. This contrasts established game-theoretic facility location models with non-strategic clients that simply select the closest opened facility. In our model, every facility location has a set of attracted clients and each client has a set of shopping locations and a weight that corresponds to her spending capacity. Facility agents selfishly select a location for opening their facility to maximize the attracted total spending capacity, whereas clients strategically decide how to distribute their spending capacity among the opened facilities in their shopping range. We focus on a natural client behavior similar to classical load balancing: our selfish clients aim for a distribution that minimizes their maximum waiting times for getting serviced, where a facility's waiting time corresponds to its total attracted client weight.
We show that subgame perfect equilibria exist and give almost tight constant bounds on the Price of Anarchy and the Price of Stability, which even hold for a broader class of games with arbitrary client behavior. Since facilities and clients influence each other, it is crucial for the facilities to anticipate the selfish clients' behavior when selecting their location. For this, we provide an efficient algorithm that also implies an efficient check for equilibrium. Finally, we show that computing a socially optimal facility placement is NP-hard and that this result holds for all feasible client weight distributions.

This is joined work with Pascal Lenzner, Louise Molitor and Alexander Skopalik.

Conference: Machine Learning for Quantum 2021

Speaker: Timo Kötzing

Abstract: The performance of modern algorithms in computer science typically depends on a number of parameters which govern the behavior of the algorithm. Setting these parameters just right is a complex task, typically dependent on the exact area of application of the algorithm, i.e. on the data to be given to the algorithm. Traditionally, algorithm designers might play with these parameters some, using their detailed knowledge of the inner workings of the algorithm, in order to find good parameter settings. However, more and more this process can be automated by parameter tuning algorithms which explore the space of available parameter settings, evaluating possible choices along the way. One way to explore is Heuristic Search, iteratively generating more and more possible parameter settings similar to previous promising settings.
Regarding calibrating multi-qubit circuits, the general structure of the problem is the same as for tuning the parameters of algorithms: There is a set of allowed settings for the parameters, each of these settings has an associated quality (which might suffer from noise). In order to find an element of good quality in this search space, the same principles (exploration vs. exploitation trade-off, search adaptation, surrogate models, hardware in the loop, …) would also be applicable in this setting. Thus, I want to present some of these ideas to you and discuss possibilities and limitations.

Conference: International Conference on Operations Research 2021

Speaker: Anna Melnichenko

Abstract: Network Design problems typically ask for a minimum cost sub-network from a given host network. This classical point-of-view assumes a central authority enforcing the optimum solution. But how should networks be designed to cope with selfish agents that own parts of the network? In this setting, minimum cost networks may be very unstable in that agents will deviate from a proposed solution if this decreases their individual cost. Hence, designed networks should be both efficient in terms of total cost and stable in terms of the agents' willingness to accept the network.
We study this novel type of Network Design problem by investigating the creation of \((\beta,\gamma)\)-networks, that are in \(\beta\)-approximate Nash equilibrium and have a total cost of at most \(\gamma\) times the optimal cost, for the recently proposed Euclidean Generalized Network Creation Game by Bilò et al. [SPAA 2019]. There, $n$ agents corresponding to points in Euclidean space create costly edges among themselves to optimize their centrality in the created network. Our main result is a simple \(\mathcal{O}(n^2)\)-time algorithm that computes a \((\beta,\beta)\)-network with low \(\beta\) for any given set of points. Moreover, on integer grid point sets or random point sets our algorithm achieves a low constant \(\beta\). Besides these results for the Euclidean model, we discuss a generalization of our algorithm to instances with arbitrary, even non-metric, edge lengths. Moreover, in contrast to these algorithmic results, we show that no such positive results are possible when focusing on either optimal networks, i.e., \((\beta,1)\)-networks, or perfectly stable networks, i.e., \((1,\gamma)\)-networks, as in both cases NP-hard problems arise, there exist instances with very unstable optimal networks, and there are instances for perfectly stable networks with high total cost. Along the way, we significantly improve several results from Bilò et al. and we asymptotically resolve their conjecture about the Price of Anarchy by providing a tight bound.

This is joined work with Wilhelm Friedemann, Tobias Friedrich, Hans Gawendowicz, Pascal Lenzner, Jannik Peters, Daniel Stephan and Michael Vaichenker.

Conference: International Conference on Operations Research 2021

Speaker: Louise Molitor

Abstract: Schelling’s classical segregation model gives a coherent explanation for the wide-spread phenomenon of residential segregation. We introduce an agent-based saturated open-city variant, the Flip Schelling Process (FSP), in which agents, placed on a graph, have one out of two types and, based on the predominant type in their neighborhood, decide whether to change their types; similar to a new agent arriving as soon as another agent leaves the vertex.
We investigate the probability that an edge {u, v} is monochrome, i.e., that both vertices u and v have the same type in the FSP, and we provide a general framework for analyzing the influence of the underlying graph topology on residential segregation. In particular, for two adjacent vertices, we show that a highly decisive common neighborhood, i.e., a common neighborhood where the absolute value of the difference between the number of vertices with different types is high, supports segregation and, moreover, that large common neighborhoods are more decisive.
As an application, we study the expected behavior of the FSP on two common random graph models with and without geometry: (1) For random geometric graphs, we show that the existence of an edge {u, v} makes a highly decisive common neighborhood for u and v more likely. Based on this, we prove the existence of a constant c > 0 such that the expected fraction of monochrome edges after the FSP is at least 1/2 + c. (2) For Erdős–Rényi graphs we show that large common neighborhoods are unlikely and that the expected fraction of monochrome edges after the FSP is at most 1/2 + o (1). Our results indicate that the cluster structure of the underlying graph has a significant impact on the obtained segregation strength.

This is joined work with Thomas Bläsius, Tobias Friedrich and Martin S. Krejca.

Conference: International Conference on Theory and Applications of Satisfiability Testing 2021

Speaker: Ralf Rothenberger

Abstract: Recently, there has been an interest in studying non-uniform random k-satisfiability (k-SAT) models in order to address the non-uniformity of formulas arising from real-world applications. While uniform random k-SAT has been extensively studied from both a theoretical and experimental perspective, understanding the algorithmic complexity of heterogeneous distributions is still an open challenge. When a sufficiently dense formula is guaranteed to be satisfiable by conditioning or a planted assignment, it is well-known that uniform random k-SAT is easy on average. We generalize this result to the broad class of non-uniform random k-SAT models that are characterized only by an ensemble of distributions over variables with a mild balancing condition. This balancing condition rules out extremely skewed distributions in which nearly half the variables occur less frequently than a small constant fraction of the most frequent variables, but generalizes recently studied non-uniform k-SAT distributions such as power-law and geometric formulas. We show that for all formulas generated from this model of at least logarithmic densities, a simple greedy algorithm can find a solution with high probability.
As a side result we show that the total variation distance between planted and filtered (conditioned on satisfiability) models is o(1) once the planted model produces formulas with a unique solution with probability 1-o(1). This holds for all random k-SAT models where the signs of variables are drawn uniformly and independently at random.

This is joined work with Tobias Friedrich, Frank Neumann and Andrew M. Sutton.

Conference: Algorithmic Approaches for Transportation Modelling, Optimization, and Systems 2020

Speaker: Maximilian Böther

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.

This is joined work with Thomas Bläsius, Philipp Fischbeck, Tobias Friedrich, Alina Gries, Falk Hüffner, Otto Kißig, Pascal Lenzner, Louise Molitor, Leon Schiller, Armin Wells and Simon Witheger.

Conference: European Symposium on Algorithms 2020

Speaker: Martin Schirneck

Abstract: In non-uniform hypergraphs there exists a phenomenon unknown to graphs: some edge may be contained in another, with edges even forming chains of inclusions. In many algorithmic applications we are only interested in the collection of inclusion-wise minimal edges, called the minimization of the hypergraph.

In the video we highlight our recent results on the minization of maximum-entropy hypergraphs with a prescribed number of edges and expected edge size. We give tigh bounds on the expected number of minimal edges and briefly touch on the tools used in the proofs. The most important technical contribution is an improvement of the Chernoff-Hoeffding theorem on the tail of the binomial distribution. In particular, we show that for a random variable \(X \sim \mathrm{Bin}(n,p)\) and any \(0 < x < p\), it holds that \(\mathrm{P}[X \le xn] = \Theta( 2^{-\mathrm{D}(x \,{\|}\, p) n}/\sqrt{n})\), where \(\mathrm{D}\) is the Kullback-Leibler divergence from information theory.

This is joined work with Thomas Bläsius and Tobias Friedrich.

Conference: European Conference on Evolutionary Computation in Combinatorial Optimisation 2020

Speaker: Martin S. Krejca

Abstract: In their recent work, Lehre and Nguyen (FOGA 2019) show that the univariate marginal distribution algorithm (UMDA) needs time exponential in the parent populations size to optimize the DeceivingLeadingBlocks (DLB) problem. They conclude from this result that univariate EDAs have difficulties with deception and epistasis. In this work, we show that this negative finding is caused by an unfortunate choice of the parameters of the UMDA. When the population sizes are chosen large enough to prevent genetic drift, then the UMDA optimizes the DLB problem with high probability with at most \(\lambda(\frac{n}{2} + 2 e \ln n)\) fitness evaluations. Since an offspring population size \(\lambda\) of order \(n \log n\) can prevent genetic drift, the UMDA can solve the DLB problem with \(O(n^2 \log n)\) fitness evaluations. In contrast, for classic evolutionary algorithms no better run time guarantee than \(O(n^3)\) is known, so our result rather suggests that the UMDA can cope well with deception and epistatis. Together with the result of Lehre and Nguyen, our result for the first time rigorously proves that running EDAs in the regime with genetic drift can lead to drastic performance losses.

This is joined work with Benjamin Doerr.

Conference: International Conference on Neural Information Processing 2020

Speaker: Arthur Zahn

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 (μ+λ) 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.

This is joined work with Tobias Friedrich, Martin S. Krejca, Gregor Lagodzinski, and Manuel Rizzo.

Conference: International Joint Conference on Artificial Intelligence 2020

Speaker: Hagen Echzell

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 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.

This is joined work with Tobias Friedrich, Pascal Lenzner and Anna Melnichenko.

Conference: International Symposium on Parameterized and Exact Computation 2020

Speaker: Davis Issac

Abstract: We develop an FPT algorithm and a compression for the Weighted Edge Clique Partition (WECP) problem, where a graph with \(n\) vertices and integer edge weights is given together with an integer \(k\), and the aim is to find \(k\) cliques, such that every edge appears in exactly as many cliques as its weight. The problem has been previously only studied in the unweighted version called Edge Clique Partition (ECP), where the edges need to be partitioned into \(k\) cliques. It was shown that ECP admits a kernel with \(k^2\) vertices [Mujuni and Rosamond, 2008], but this kernel does not extend to WECP. The previously fastest algorithm known for ECP has a runtime of \(2^{O(k^2)}n^{O(1)}\) [Issac, 2019 (PhD Thesis)]. For WECP we develop a compression (to a slightly more general problem called Annotated WECP) with at most \(4^k\) vertices, and an algorithm with runtime \(2^{O(k^{3/2}w^{1/2}\log(k/w))}n^{O(1)}\), where \(w\) is the maximum edge weight. The latter in particular improves the runtime for ECP to \(2^{O(k^{3/2}\log k)}n^{O(1)}\).

This is joined work with Andreas Emil Feldmann and Ashutosh Rai.

Conference: International Conference on Very Large Data Bases 2020

Speaker: Thomas Bläsius

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 video, 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.

This is joined work with Johann Birnick, Tobias Friedrich, Felix Naumann, Thorsten Papenbrock, and Martin Schirneck.

Conference: Workshop on Approximation and Online Algorithms 2020

Speaker: Ardalan Khazraei

Abstract: The cost-distance Steiner tree problem asks for a Steiner tree in a graph that minimizes the total cost plus a weighted sum of path delays from the root to the sinks. We present an improved approximation for the uniform cost-distance Steiner tree problem, where the delay of a path corresponds to the sum of edge costs along that path. Previous approaches deploy a bicriteria approximation algorithm for the length-bounded variant that does not take the actual delay weights into account. Our algorithm modifies a similar algorithm for the single-sink buy-at-bulk problem by Guha et al. [2009], allowing a better approximation factor for our problem. In contrast to the bicriteria algorithms it considers delay weights explicitly. Thereby, we achieve an approximation factor of (1+ \(\beta\) ), where \(\beta\) is the approximation factor for the Steiner tree problem. This improves the previously best known approximation factor for the uniform cost-distance Steiner tree problem from 2:87 to 2:39. This algorithm can be extended to the problem where the ratio of edge costs to edge delays throughout the graph is bounded from above and below. In particular, this shows that a previous inapproximability result (Chuzhoy et al. [2008]) requires large variations between edge delays and costs. Finally, we present an important application of our new algorithm in chip design. The cost-distance Steiner tree problem occurs as a Lagrangean subproblem when optimizing millions of Steiner trees with mutually depending path length bounds. We show how to quickly approximate a continuous relaxation of this problem with our new algorithm.

This is joined work with Stephan Held.

Talk: PhD Defense 2017

Speaker: Anton Krohmer