Bremen-Hamburg Initiative on Algorithms, Combinatorics, and Optimization

Hadwiger's Conjecture (1943) asserts that every graph without the complete graph \(K_{t+1}\) as a minor has a proper vertex-colouring using at most \(t\) colours. In spite of a lot of effort, we seem to be very far from a proof of the conjecture in general. For instance, it was proved in 1993 that it is true for t at most 5, a bound that hasn't changed since then. Nevertheless, in recent years there has been an increase in activity around the conjecture. In the talk I will discuss some of these recent approaches and results.

Population protocols are a model of distributed computing, where n agents with limited computational power and memory interact randomly, in order to jointly perform a global task. A fundamental problem in this setting is that of leader election, where all agents start from the same state, and they seek to reach and maintain a global state where exactly one agent is in a dedicated leader state.
In this paper we establish that if agents have \(\Omega(\log\log n)\) states, the expected time complexity of leader election is \(\Theta(n \log n)\). Unlike existing protocols, ours does not decrease the set of candidate leaders monotonically. Our protocol has both optimal time and space complexity.
Joint work with George Giakkoupis and Peter Kling.

The diameter of a polytope P is the maximum length of a shortest path between a pair of vertices of P, when one is allowed to walk on the edges (1-dimensional faces) of P. Despite decades of studies, it is still not known whether the diameter of a d-dimensional polytope with n facets can be bounded by a polynomial function of n and d. This is a fundamental open question in discrete mathematics, motivated by the (still unknown) existence of a polynomial pivot rule for the Simplex method for solving Linear Programs. A generalized notion of diameter, recently introduced in the literature, is that of circuit-diameter, defined as the maximum length of a shortest path between two vertices of P, where the path can use all edge directions (called circuits) that can arise by translating some of the facets of P. In this talk I will survey some results on the complexity of computing the diameter of a polytope, and the computation of circuits. We will discuss the more general framework of circuit-based augmentation algorithms, and how they can be exploited also to analyze the performance of the Simplex method.

Integer programs (IP) with $m$ constraints are solvable in pseudo-polynomial time. We give a new algorithm based on the Steinitz Lemma and dynamic programming with a better pseudo-polynomial running time than previous results. Vectors $v_1,\ldots,v_n$ in $R^m$ that sum up to the $0$ vector can be seen as a circle in $R^m$ that walks from $0$ to $v_1$ to $v_1 + v_2$, etc. until it reaches $v_1 + \ldots + v_n = 0$ again. The Steinitz Lemma says that if each of the vectors is small with respect to some norm, we can reorder the vectors in a way that each point in the circle is not far away from $0$ w.r.t. the same norm. We show in the talk that a solution to the IP $\max c^T x, A x = b, x >= 0, x in Z^n$ can be found in time $O(m \Delta)^{2m} log(||b||_\infty) + O(nm)$ where $\Delta$ is the biggest absolute value of any entry in $A$.
Moreover, we establish a strong connection to the problem $(min,+)$-convolution. $(min,+)$-convolution has a trivial quadratic time algorithm and it has been conjectured that this cannot be improved significantly. We show that further improvements to our pseudo-polynomial algorithm for any fixed number $m$ of constraints are equivalent to improvements for $(min,+)$-convolution. This is a strong evidence that our algorithm’s running time is best possible. We also present a faster specialized algorithm for testing feasibility of an integer program with few constraints. Our algorithm for the feasibility problem runs in $O(m \Delta)^{m}\log(\Delta) \log(\Delta + ||b||_\infty) + O(nm)$. Finally we show for the feasibility problem also a tight lower bound, which is based on the Strong Exponential Time Hypothesis (SETH), and give some applications for knapsack and scheduling problems. This is joint work with Lars Rohwedder.

For a $k$-uniform hypergraph $F$ let $\textrm{ex}(n,F)$ be the maximum number of edges of a $k$-uniform $n$-vertex hypergraph $H$ which contains no copy of~$F$.Determining or estimating $\textrm{ex}(n,F)$ is a classical and central problem in extremal combinatorics. While for graphs ($k=2$) this problem is well understood, due to the work of Tur\'an and of Erd\H os and Stone, only very little is known for $k$-uniform hypergraphs for $k>2$. Already the (somewhat particular looking) case when $F$ is a~$k$-uniform hypergraph with three edges on~$k+1$ vertices is still wide open even for~$k=3$.
We consider a variant of the problem where the large hypergraph~$H$ enjoys additional hereditary density conditions. Questions of this type were suggested by Erd\H os and S\'os about 30 years ago. In recent work with Reiher and R\"odl it turned out that the \emph{regularity method for hypergraphs}, established by Gowers and by R\"odl et al.\ about a decade ago, is a suitable tool for extremal problems of this type and we shall discuss some of those recent results.

Machine-learned predictors, although achieving very good results for inputs resembling training data, cannot possibly provide perfect predictions in all situations. Still, decision-making systems that are based on such predictors need not only to benefit from good predictions but also to achieve a decent performance when the predictions are inadequate. In this paper, we propose a prediction setup for arbitrary metrical task systems (MTS) (e.g., caching, k-server and convex body chasing) and online matching on the line. We utilize results from the theory of online algorithms to show how to make the setup robust. Specifically for caching, we present an algorithm whose performance, as a function of the prediction error, is exponentially better than what is achievable for general MTS. Finally, we present an empirical evaluation of our methods on real world datasets, which suggests practicality.
Joint work with Antonios Antoniadis, Christian Coester, Marek Elias, and Adam Polak