We study the generalized min sum set cover (GMSSC) problem, wherein given a collection of hyperedges E with arbitrary covering requirements k_e, the goal is to find an ordering of the vertices to minimize the total cover time of the hyperedges; a hyperedge e is considered covered by the first time when k_e many of its vertices appear in the ordering. We give a 4.642 approximation algorithm for GMSSC, coming close to the best possible bound of 4, already for the classical special case (with all k_e=1) of min sum set cover (MSSC) studied by Feige, Lovász and Tetali, and improving upon the previous best known bound of 12.4 due to Im, Sviridenko and van der Zwaan. Our algorithm is based on transforming the LP solution by a suitable kernel and applying randomized rounding. This also gives an LP-based 4 approximation for MSSC. As part of the analysis of our algorithm, we also derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which might be of independent interest and broader utility.

Another well-known special case is the min sum vertex cover (MSVC) problem, in which the input hypergraph is a graph and k_e=1, for every edge. We give a 16/9 approximation for MSVC, and show a matching integrality gap for the natural LP relaxation. This improves upon the previous best 1.999946 approximation of Barenholz, Feige and Peleg. Finally, we revisit MSSC and consider the ell_p norm of cover-time of the hyperedges. Using a dual fitting argument, we show that the natural greedy algorithm achieves tight, up to NP-hardness, approximation guarantees of (p+1)^{1+1/p}, for all p>=1. For p=1, this gives yet another proof of the 4 approximation for MSSC.

An upper dominating set in a graph is an inclusion-wise minimal dominating set of maximum cardinality. Berge and Duchet in 1975 showed how to compute the upper domination number \(k^*\) of an \(n\)-vertex graph in time \(O(n^{k^*+3})\). Conversely, Bazgan et al. [TCS 2018] proved that \(k^*\) cannot be computed in time \(f(k^*) n^{o(\sqrt{k^*})}\) for any computable function \(f\), unless the Exponential Time Hypothesis (ETH) fails. Very recently and independently of each other, Araújo et al. [ArXiv 2021] as well as Dublois, Lampis, and Paschos [CIAC 2021] closed this gap in ruling out any algorithm running in time \(f(k^*) n^{o(k^*)}\) under ETH.

In the talk, we walk through the proof of Araújo et al. and discuss some open problems regarding the transversal rank of a hypergraph.

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.

While crossover is ubiquitous in evolutionary computing, many theoretical analyzes have a strong focus on operators varying only a single parent individual. In order to understand better how and why crossover can benefit optimization, we consider pseudo-Boolean functions with an upper bound \(B\) on the number of 1s allowed in the bit string (cardinality constraint). For the natural translation of the OneMax test function to this setting, the literature gives a bound of \(\Theta(n^2)\) for the (1+1) EA. Part of the difficulty when optimizing this problem lies in having to improve individuals meeting the cardinality constraint by flipping both a 1 and a 0. The experimental literature proposes balanced operators, preserving the number of 1s, as a remedy. We show that a balanced mutation operator optimizes the problem in \(O(n\log n)\) if \(n-B=O(1)\). However, if \(n-B=\Theta(n)\), we show a bound of \(\Omega(n^2)\), just as classic bit flip mutation. Crossover and a simple island model gives \(O(n^2\log n)\) (uniform crossover) and \(O(n\sqrt n)\) (3-ary majority vote crossover). For balanced uniform crossover with Hamming distance maximization for diversity we show a bound of \(O(n\log n)\). As an additional contribution we analyze and discuss different balanced crossover operators from the literature.

Fair clustering is a variant of constrained clustering where the goal is to partition a set of colored points. The fraction of points of each color in every cluster should be more or less equal to the fraction of points of this color in the dataset. We present a new construction of coresets for fair k-means and k-median clustering for Euclidean and general metrics based on random sampling. For the Euclidean space, we provide the first coresets whose size does not depend exponentially on the dimension d. For general metric, our construction provides the first coreset for fair k-means and k-median. With the help of the coreset, we design better approximation and streaming algorithms for fair and other constrained clustering variants. In particular, we obtain the first fixed-parameter tractable PTAS for fair k-means and k-median clustering in R^d and the first FPT "true'' constant-approximation for metric fair clustering.

In this talk I introduce the Minimum Linear Arrangement Problem and our recent and upcoming results on it. But more importantly, I will depict a classical journey of researching a problem with its ups and downs, detours, and lucky (or unlucky) accidents until you are finally able to prove...something! Disclaimer to fresh PhD students: This is how research really works! Don't be discouraged.

I consider a simple noisy optimization problem: the value of a bit string is its number of 1s plus a random variable drawn from a (centered) Gaussian distribution. It was no surprise to me that simple hill-climbers (like random local search or the 1+1 Evolutionary Algorithm) cannot handle even small noise levels. It was a big surprise to me that some other algorithms (like some estimation of distribution algorithms and crossover-based algorithms) can deal even with big noise effectively. I came to understand this latter phenomenon as essentially the result of averaging over many iterations, and some parameters have to be scaled up in order to deal with higher noise.

However, even considering these effects, some algorithms were unreasonably effective. In my talk I want to discuss some further findings that seem to indicate that, for example, the compact genetic algorithm can handle Gaussian noise with O(n) variance (which is a lot!) without any scaling of parameters or any other tricks -- just out of the box. This is thanks to sampling widely different individuals a lot of the time, which I will elaborate on in my talk.