10.04. 11:00  A1.1  Martin Gairing  The Price of Stability of Weighted Congestion Games
We give exponential lower bounds on the Price of Stability (PoS) of weighted congestion games with polynomial cost functions. In particular, for any positive integer \(d\) we construct rather simple games with cost functions of degree at most \(d\) which have a PoS of at least \(\varOmega(\Phi_d)^{d+1}\), where \(\Phi_d\sim d/\ln d\) is the unique positive root of equation \(x^{d+1}=(x+1)^d\). This asymptotically closes the huge gap between \(\varTheta(d)\) and \(\Phi_d^{d+1}\) and matches the Price of Anarchy upper bound. We further show that the PoS remains exponential even for singleton games.
More generally, we also provide a lower bound of \(\varOmega((1+1/\alpha)^d/d)\) on the PoS of \(\alpha\)approximate Nash equilibria. All our lower bounds extend to network congestion and hold for mixed and correlated equilibria as well.
On the positive side, we give a general upper bound on the PoS of approximate Nash equilibria, which is sensitive to the range \(W\) of the player weights.
We do this by explicitly constructing a novel approximate potential function, based on Faulhaber's formula, that generalizes Rosenthal's potential in a continuous, analytic way. From the general theorem, we deduce two interesting corollaries. First, we derive the existence of an approximate pure Nash equilibrium with PoS at most \((d+3)/2\); the equilibrium's approximation parameter ranges from \(\varTheta(1)\) to \(d+1\) in a smooth way with respect to \(W\). Secondly, we show that for unweighted congestion games, the PoS of \(\alpha\)approximate Nash equilibria is at most \((d+1)/\alpha\).

13.04. 10:00  Campus Golm House 9, Room 2.09.0.13  Tobias Friedrich  The Intrinsic Geometry of ScaleFree Networks
The node degrees of large realworld networks often follow a powerlaw distribution. Such scalefree networks can be social networks, internet topologies or many other networks. There is, however, no established and simple network model,which also has a high clustering of vertices as typically observed in real data. This talk will present several mathematical models of scalefree networks and introduce hyperbolic random graphs as a natural model that fulfils most properties of real world networks.

16.04. 11:00  HE.52  David Schumann  Exploring Game Theoretic Models for Generating Real World Networks
In the past 20 years the field of network science has made a large step forward through the discovery of scalefree properties in many real world networks.
Graph generation processes like the Barabasi Albert model or the hyperbolic random graph model strive to generate graphs with properties observed in the real world.
Some of these models also offer plausible theories on how these properties emerge by providing simple and realistic rule sets which could be believed be present in the natural processes observed.
Still no model exists, which both generates all observed properties and at the same time offers a convincing explanation for them.
In the real world, networks are usually not designed by a central entity but result from the actions of multiple independent selfish agents.
In order to understand these natural processes it is therefore desirable to find models with simple, realistic rules and a high explanatory power.
Here we derive multiple network creation games from the agentbased network formation model recently proposed by Chauhan et al.
In order to show that our models generate realistic graphs, and that we can influence their properties, we explore the effect different configurations have on the resulting equilibrium graphs both by theoretical proofs and practical experiments using a large high performance computing cluster.
We show here that the equilibrium graphs in these network creation games mimic real world networks.
They contain a node degree distribution following a power law, a high clustering coefficient, a small diameter and they are sparse.
We furthermore manage to influence these properties by adjusting the game's cost function, the player's strategy changes, the game's starting configuration and other game mechanics.
Our results offer a new understanding on how real world networks form and which processes are involved in their shaping.

19.04. 11:00  A1.1  Alexander Skopalik  Simple, distributed, and powerful  improving local search for distributed resource allocation and equilibrium computation
Congestion games constitute an important class of games to model resource allocation by different users such as in traffic networks. We study the approximation ratio of local optima in these games. However, we allow for that the cost functions used during the local search procedure may be different from the overall objective function. Our analysis exhibits an interesting method to choose these cost functions to obtain a number of different results:
1. As computing an exact or even approximate pure Nash equilibrium is in
general PLScomplete, Caragiannis et al. [FOCS 2011] presented
a polynomialtime algorithm that computes \((2 + \varepsilon)\)approximate pure
Nash equilibria for games with linear cost functions and further results for polynomial cost functions. We show that this factor can be improved to \(1.67+\varepsilon\) by a seemingly simple modification of their algorithm using our technique.
2. Bilo and Vinci [EC 2016] presented an algorithm to compute load depended taxes the improve the price of anarchy e.g. for linear game from 2.5 to 2. Our methods yield slightly weaker results, e.g., 2.1 for linear games. However, our tax functions are locally computable an independent of the actually instance of the game. There algorithm is a centralized algorithm and sensitive to changes of the instance such as e.g. the number of players.
3. Computing an optimal allocation in congestion games is NPhard. The best known centralized approximation algorithm is due to Makarychev and Srividenko [FOCS14]. Again, our technique does not quite match there bounds but offers a modified local search procedure as a much simpler alternative which can easily be implemented in a distributed fashion.

23.04. 15:15  A2.1  Frank Neumann  Exact Approaches for Packing While Traveling and the Traveling Thief Problem
Multicomponent problems play a crucial role in realworld applications, especially in the area of supply chain management. Recently, the traveling thief problem (TTP) has been introduced to study multicomponent problems in a systematic way and many heuristic search algorithms have been proposed for the TTP. Although a lot of algorithmic advances have been made on this problem, determining an optimal solution, even for small instances, is very challenging. In this talk, I will present exact approaches for this problem. I start by investigating the already NPhard Packing While Traveling (PWT) problem which results from TTP when the TSP tour is fixed. I present an exact dynamic programming approach for PWT and give a fully polynomial time approximation scheme (FPTAS) for PWT over its baseline travel cost. Afterwards, I extend the approach to give a dynamic programming approach for TTP and report on some experimental results.
Joint work with Sergey Polyakovskiy, Martin Skutella, Leen Stougie, Junhua Wu, Markus Wagner

25.04. 15:15  H2.57  Ankit Chauhan  Efficiency of local search on realworld networks
Many realworld networks follow structural properties like powerlaw degree distribution, high clustering coefficient, smallworld etc. It has been observed that the very simple local search algorithms are based on searching in the kexchange neighborhood perform very well on realworld instances. In this work, we make an attempt to understand the nice behavior of local search algorithms on realworld networks.

26.04. 11:00  A1.1  Aneta Neumann  Evolutionary Image Composition Using Feature Covariance Matrices
Evolutionary algorithms have recently been used to create a wide range of artistic work. In this paper, we propose a new approach for the composition of new images from existing ones, that retain some salient features of the original images. We introduce evolutionary algorithms that create new images based on a fitness function that incorporates feature covariance matrices associated with different parts of the images. This approach is very flexible in that it can work with a wide range of features and enables targeting specific regions in the images. For the creation of the new images, we propose a populationbased evolutionary algorithm with mutation and crossover operators based on random walks. Our experimental results reveal a spectrum of aesthetically pleasing images that can be obtained with the aid of our evolutionary process.

15.05. 11:00  A1.1  Maximilian Katzmann  Towards a Systematic Evaluation of Generative Network Models
Generative graph models play an important role in network science.
Unlike realworld 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 realworld 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ősRényi, BarabásiAlbert, ChungLu, and hyperbolic
random graphs). Our experiments for example show that all four models
are bad representations for Facebook's social networks, while ChungLu
and hyperbolic random graphs are good representations for other
networks, with different strengths and weaknesses.

17.05. 11:00  A1.1  Luca San Mauro  How to Model Trial and Error Reasoning in Mathematics
Formal systems represent mathematical theories in a rather
static way, in which axioms of the represented theory
have to be defined from the beginning, and no further modification is
permitted. As is clear, this representation is not
comprehensive of all aspects of real mathematical theories. For
instance, when defining a new theory, a mathematician might
choose axioms through some trial and error process, instead of fixing
them once for all at the initial stage. One way of
characterizing such cases is provided by dialetical systems, introduced
by Magari in the 1970's.
The basic ingredients of a dialectical system are a number c, encoding a
contradiction; a deduction operator H, that tells
us how to derive consequences from a finite set of statements D; and a
proposing function f, that proposes statements to be
accepted or rejected as provisional theses of the system. We study
dialectical systems and compare them with two novel classes
of systems: pdialectical systems and qdialectical systems.

28.05. 15:15  A2.1  Martin Schirneck  On the Enumeration of Minimal Hitting Sets in Lexicographical Order
It is a longstanding open problem whether there exists an outputpolynomial algorithm enumerating all minimal hitting sets of a hypergraph. A stronger requirement is to ask for an algorithm that outputs them in lexicographical order. Although there is no incrementalpolynomial algorithm for this task in general, unless P = NP, we present a method with delay O(H^(k*+2) V^2), where k* is the rank of the transversal hypergraph. On classes of hypergraphs for which k* is bounded the delay is polynomial. Additionally, we identify the extension problem of minimal hitting sets as one of only a few problems complete for the parameterized class W[3]. We give an algorithm that is optimal under ETH.

31.05. 11:00  A1.1  Timo Kötzing  TeacherLearner Models
While a lot of research on learning theory focuses on making sense of adversarial or random data, teacherlearner models try to capture the difficulty of learning when examples are chosen benevolently by a teacher. The question is now how much data is still necessary to learn a concept from a given class? In this talk I will review three different models for modeling this setting, give sample results and relate these models to other complexity measures of concept classes, for example the VCDimension.

26.06. 11:00  A1.1  Louise Molitor  Schelling Segregation with Strategic Agents
Schelling’s segregation model is a landmark model in sociology. It shows the counterintuitive phenomenon that residential segregation between individuals of different groups can emerge even when all involved individuals are tolerant. Although the model is widely studied, no pure gametheoretic version where rational agents strategically choose their location exists. We close this gap by introducing and analyzing generalized gametheoretic models of Schelling segregation, where the agents can also have individual location preferences. For our models we investigate the convergence behavior and the efficiency of their equilibria. In particular, we prove guaranteed convergence to an equilibrium in the version which is closest to Schelling’s original model. Moreover, we provide tight bounds on the Price of Anarchy.

26.06. 11:30  A1.1  Ralf Rothenberger  Sharpness of the Satisfiability Threshold for NonUniform Random kSAT
We study nonuniform random kSAT 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 kSAT 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\_∞ = o_n(t^{k/(2k1)} \log^{(k1)/(2k1)}(t))\).
This result generalizes Friedgut’s sharpness result from uniform to nonuniform random kSAT and implies sharpness for thresholds of a wide range of random kSAT models with heterogeneous probability distributions, for example such models where the variable probabilities follow a powerlaw distribution.

28.06. 11:00  A1.1  Stefan Neubert  Mechanisms for Network Creation
We introduce and analyze the possibilities of a new model for network creation by autonomous selfish agents: Unlike in typical network formation games such as the wellknown model of Fabrikant et al. [PODC'03], the final network is not directly shaped by the players of a game. Instead, we design mechanisms that take edge preferences of agents as input for a social choice function and return a network that respects those preferences. In addition, it caters for compliance with global restrictions on the network topology and tries to establish several properties, such as global efficiency, maximizing the individual utility of agents, and building stable networks, especially in comparison to the result of an anarchic network formation. The mechanism also aims to produce Nash equilibria and encourages agents to honestly declare their preferences instead of playing strategically.
The mechanism approach is a true superset of both centralized network design and uncoordinated network creation games. To the best of our knowledge this is the first attempt to explore the realm inbetween those extremes.

05.07. 11:00  A1.1  Thomas Bläsius  Efficient Shortest Paths in ScaleFree Networks with Underlying Hyperbolic Geometry
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 scalefree realworld networks. Such npetworks typically have a heterogeneous degree distribution (e.g., a powerlaw 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. The bound we obtain is sublinear, improving the obvious worstcase linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it.

10.07. 11:00  A1.1  Francesco Quinzan  Improving the Run Time of the (1+1) Evolutionary Algorithm with Luby Sequences
In the context of black box optimization, one of the most common ways 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)EAu, a metaheuristic that does not require parameter tuning.
We first consider two artificial pseudoBoolean landscapes, on which the (1+1)EA exhibits exponential run time. We prove that the (1+1)EAu 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)EAu 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ε)approximation in polynomial time, and we show that the (1+1)EAu reaches a (4/3ε)approximation in polynomial time. We then prove that the (1+1)EAu serves as an Efficient Polynomialtime Approximation Scheme (EPTAS) for the Partition Problem, for a (1+ε)approximation with ε > 4/n.

10.07. 11:30  A1.1  Martin Krejca  Significancebased EstimationofDistribution Algorithms
Estimationofdistribution algorithms (EDAs) are randomized search heuristics that maintain a stochastic model of the solution space. This model is updated from iteration to iteration based on the quality of the solutions sampled according to the model. As previous works show, this shortterm perspective can lead to erratic updates of the model, in particular, to bit frequencies approaching a random boundary value. This can lead to significant performance losses.
In order to overcome this problem, we propose a new EDA that takes into account a longer history of samples and updates its model only with respect to information which it classifies as statistically significant. We prove that this significancebased compact genetic algorithm (sigcGA) optimizes the common benchmark functions OneMax and LeadingOnes both in O(n log n) time, a result shown for no other EDA or evolutionary algorithm so far. For the recently proposed scGA – an EDA that tries to prevent erratic model updates by imposing a bias to the uniformly distributed model – we prove that it optimizes OneMax only in a time exponential in the hypothetical population size 1/ρ.

19.07. 11:00  A1.1  Karen Seidel  Learning from Labeled Data: Relations between Learning Success Criteria
Concerning learning from positive and negative information, being one of the models for human and machine learning introduced by Gold, naturally arising questions about this learning setting are answered.
By a carefully arranged argument learners can be assumed to only change their hypothesis in case it is inconsistent with the data. The deduced main theorem states the relations between the most important delayable learning success criteria, being the ones not ruined by a delayed in time hypothesis output. Additionally, our investigations concerning the nondelayable requirement of consistent learning underpin the claim for delayability being the right structural property to gain a deeper understanding concerning the nature of learning success criteria.
Moreover, we obtain a hierarchy when allowing for an increasing finite number of anomalies of the hypothesized language by the learner compared with the language to be learned, and observe a duality, depending on whether infinitely many vacillations between different (almost) correct hypotheses are still considered a successful learning behavior.

02.08. 14:00  A1.2  Benjamin Feldmann, Ahmed Rekik  Visualizing Networks in Hyperbolic SpaceThe Euclidean space has always been considered to be the standard
rendering real estate for various objects and structures, but despite
this conventional wisdom the Euclidean plane may show its limits when
representing networks. If the graph is not planar, crossings may occur
in various kinds and if the graph is dense, drawing edges can make the
visualization cluttered and recognizing the structure of the network
becomes almost impossible.
One approach to overcome this issue suggests to embed graphs in the
hyperbolic space instead of the Euclidean one. The main reason is that
the hyperbolic space provides more space to represent the network’s
vertices due to its exponential expansion. Since many realworld
networks have properties that make them fit nicely into the hyperbolic
plane, one can make use of this exponential expansion to obtain better
network visualizations. Projecting this hyperbolic visualization into
an Euclidean canvas then leads to a fisheye view. On the one hand,
the fisheye view highlights what is shown in the centre of the
projection. On the other hand, it maintains some sense of the larger
structure of the graph.
In the scope of our master project, we implemented a visualization
tool for graphs with an underlying hyperbolic geometry that is suited
for all common browsers. By exploiting the power of modern graphics
cards, it allows the user to fluidly navigate through hyperbolic
visualizations of networks with more than 10.000 nodes.

09.08. 11:00  A1.1  Timo Kötzing  Best of CiE
Last week I was at CiE. With this talk I want to give you a taste of what they do at CiE and show how this relates to the work we do in our group. I will also present one result in a bit more detail relating to actually computing tree width on realistic instances.

21.08. 15:00  A1.1  Gregor Lagodzinski  Counting Homomorphisms to Trees Modulo a Prime
Many important graph theoretic notions can be encoded as counting graph homomorphism problems, such as partition functions in statistical physics, in particular independent sets and colourings.
We study the complexity of \(\#_p{\rm H{\scriptsize OMS}T{\scriptsize O}}H\), the problem of counting graph homomorphisms from an input graph to a graph \(H\) modulo a prime number \(p\).
Dyer and Greenhill proved a dichotomy stating that the tractability of nonmodular counting graph homomorphisms depends on the structure of the target graph.
Many intractable cases in nonmodular counting become tractable in modular counting due to the common phenomenon of cancellation.
In subsequent studies on counting modulo \(2\), however, the influence of the structure of \(H\) on the tractability was shown to persist, which yields similar dichotomies.
Our main result states that for every tree \(H\) and every prime \(p\) the problem \(\#_p{\rm H{\scriptsize OMS}T{\scriptsize O}}H\) is either polynomial time computable or \(\#_p\mathsf{P}\)complete.
This relates to the conjecture of Faben and Jerrum stating that this dichotomy holds for every graph \(H\) when counting modulo 2.
In contrast to previous results on modular counting, the tractable cases of \(\#_p{\rm H{\scriptsize OMS}T{\scriptsize O}}H\) are essentially the same for all values of the modulo when \(H\) is a tree.
We are going to provide insights by first introducing the line of research and then use a proofbyexample approach to the various steps of the proof.

22.08. 15:00  A1.1  Isabel Amon, Hans Gawendowicz, Julius Lischeid, Lennart Salabarria, Jonas Umland  Bachelor Theses of the Summer Term 2018
The participants of the Bachelor Project 2017 will present their Bachelor Theses.
Isabel Amon:
Application of evolutionary algorithms for skillbased project scheduling
Hans Gawendowicz:
Analysis of simple Evolutionary Algorithms on the Maximum Cardinality Matching Problem
Julius Lischeid:
Lexicographic Enumeration of Hitting Sets in Hypergraphs
Lennart Salabarri:
Exploration of local agentbased optimization strategies
Jonas Umland:
Skillbased Employee Scheduling Using Integer Linear Programming

23.08. 11:00  A1.1  Clemens Frahnow  Ring Migration Topology Helps Bypassing Local Optima In Evolutionary Computation
Running several evolutionary algorithms in parallel and occasionally exchanging good solutions is referred to as islands models. The idea is that the independence of the different islands leads to diversity, thus possibly exploring the search space better. Theoretical analyses have so far focused on simple unimodal fitness functions, for which typically no improvement can be gained from an island setup other than parallelism. Partially the problem here is to find fitness functions which are as somewhat canonical (exemplifying a common structure in search problems) and analyzable.
I suggest a simple fitness function Fork with two local optima parametrized by \(r ≥ 2\) and a scheme for composite fitness functions which can together extend the so far rather small library of canonical and analyzable fitness functions. I show that, while the \((1+1)\) EA gets stuck in a bad local optimum and incurs a run time of \(\Theta(n^{2r})\) fitness evaluations, island models with a complete topology can achieve a run time of \(\Theta(n^{1.5r})\) by making use of rare migrations in order to explore the search space more effectively. Finally, the ring topology, making use of rare migrations and a large diameter, can achieve a run time of \(\Theta(n^r)\), the black box complexity of Fork.

11.09. 11:00  A2.1  Jacob Focke  The Complexity of Surjective Homomorphism Counting Problems
A homomorphism from a graph G to a graph H is a function from the vertices of G to the vertices of H
that preserves edges.
A homomorphism is surjective if it uses all of the vertices of H and
it is a compaction if it uses all of the vertices of H and all of the nonloop edges of H. Let G be a graph that
contains an induced subgraph H. A retraction from G to H is a homomorphism from G to H
that is the identity function on H.
The corresponding decision problems are very wellstudied. However, despite a lot of effort the complexity of the surjective homomorphism decision problem and the complexity of the compaction decision problem are still not completely classified.
We consider the counting versions of these problems.
Part I: Exact Counting
Dyer and Greenhill gave a complete characterisation of the complexity of
exactly counting homomorphisms from an input graph G to a fixed graph H. We give complete characterisations of the complexity of exactly counting surjective homomorphisms, counting compactions and counting retractions.
Part II: Approximate Counting
Our first contribution is to give a complete trichotomy for approximately counting retractions to trees.
Our second contribution is to locate the retraction counting problem in the complexity landscape of related approximate counting problems.
Interestingly, these results are in contrast to the situation in the exact counting context.
Joint work with: Leslie Ann Goldberg and Stanislav Zivny

13.09. 11:00  A1.1  Christopher Weyand  Locality in Game Theoretic Models for RealWorld Networks
Many realworld networks, although from fundamentally different domains, exhibit common properties. The field of Network Science explores and models the generation of such networks to understand their creation. Numerous models were proposed to produce a subset or all properties of realworld networks and explain their emergence. Unfortunately, most models that generate all properties lack a convincing explanation and do not relate to their observed emergence in the real world. On the other hand, the intuitive explanatory power inherent in the field of Game Theory inspired recent research in this direction.
In continuation of the work of Schumann, we analyze a family of game theoretic models for realworld networks. We provide analytical and empirical results to show that the model generates sparse, scalefree networks with high clustering and small diameter. We focus on the consequences of agents having local instead of global goals by analyzing the structure of equilibrium networks and the dynamics of the system.

19.09. 11:00  A1.1  Manuel Rizzo  Multiple changepoint detection in seasonal time series by genetic algorithms
The present research is devoted to time series which display two main features: seasonality, for which a similar behaviour is repeated every year at the same period, and structural changes, that are abrupt modifications of the series features occurring at unknown time instants. Such features are common to time series in many fields, like finance, economics, hydrology. We propose a statistical model that considers several periodic autoregressive processes, which account for the seasonal effect, linked at different changepoints. Building such a model requires to select the optimal number and locations of changepoints from a prohibitevely large discrete set, and no analytical solution to the related combinatorial optimization problem is available. We propose a procedure based on genetic algorithms for dealing with this complex problem. An application to the Italian industrial production index data will be also presented (joint work with Francesco Battaglia, Domenico Cucina and Eugen Ursu).

04.10. 11:00  A2.1  Ralf Rothenberger  Memoryrestricted Routing With Tiled Map Data
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*.
