We consider two-player zero-sum stochastic mean payoff games with perfect information. We show that any such game, with a constant number of random positions and polynomially bounded positive transition probabilities, admits a polynomial time approximation scheme, both in the relative and absolute sense.

We provide a smoothed analysis of Hoare’s find algorithm, and we revisit the smoothed analysis of quicksort. Hoare’s find algorithm—often called quickselect or one-sided quicksort—is an easy-to-implement algorithm for finding the k-th smallest element of a sequence. While the worst-case number of comparisons that Hoare’s find needs is Θ(n 2), the average-case number is Θ(n). We analyze what happens between these two extremes by providing a smoothed analysis. In the first perturbation model, an adversary specifies a sequence of n numbers of [0,1], and then, to each number of the sequence, we add a random number drawn independently from the interval [0,d]. We prove that Hoare’s find needs $\Theta(\frac{n}{d+1} \sqrt{n/d} + n)$ comparisons in expectation if the adversary may also specify the target element (even after seeing the perturbed sequence) and slightly fewer comparisons for finding the median. In the second perturbation model, each element is marked with a probability of p, and then a random permutation is applied to the marked elements. We prove that the expected number of comparisons to find the median is $\Omega((1-p) \frac{n}{p} \log n)$ . Finally, we provide lower bounds for the smoothed number of comparisons of quicksort and Hoare’s find for the median-of-three pivot rule, which usually yields faster algorithms than always selecting the first element: The pivot is the median of the first, middle, and last element of the sequence. We show that median-of-three does not yield a significant improvement over the classic rule.

We introduce to the runtime analysis of evolutionary algorithms two powerful techniques: probability-generating functions and variable drift analysis. They are shown to provide a clean framework for proving sharp upper and lower bounds. As an application, we improve the results by Doerr et al. (GECCO~2010) in several respects. First, the upper bound on the expected running time of the most successful quasirandom evolutionary algorithm for the OneMax function is improved from 1.28n ln n to 0.982n ln n, which breaks the barrier of n ln n posed by coupon-collector processes. Compared to the classical 1+1-EA, whose runtime will for the first time be analyzed with respect to terms of lower order, this represents a speedup by more than a factor of e=2.71...

With the prevalence of social networks, it has become increasingly important to understand their features and limitations. It has been observed that information spreads extremely fast in social networks. We study the performance of randomized rumor spreading protocols on graphs in the preferential attachment model. The well-known random phone call model of Karp et al. (FOCS 2000) is a push-pull strategy where in each round, each vertex chooses a random neighbor and exchanges information with it. We prove the following. - The push-pull strategy delivers a message to all nodes within Θ(log n) rounds with high probability. The best known bound so far was O(log2 n). - If we slightly modify the protocol so that contacts are chosen uniformly from all neighbors but the one contacted in the previous round, then this time reduces to Θ(log n / log log n), which is the diameter of the graph. This is the first time that a sublogarithmic broadcast time is proven for a natural setting. Also, this is the first time that avoiding double-contacts reduces the run-time to a smaller order of magnitude.

Motivated by recent successful applications of the concept of quasirandomness, we investigate to what extent such ideas can be used in evolutionary computation. To this aim, we propose different variations of the classical (1+1) evolutionary algorithm, all imitating the property that the (1+1) EA over intervals of time touches all bits roughly the same number of times. We prove bounds on the optimization time of these algorithms for the simple OneMax function. Surprisingly, none of the algorithms achieves the seemingly obvious reduction of the runtime from Θ( n log n ) to O(n) . On the contrary, one may even need Ω( n 2 ) time. However, we also find that quasirandom ideas, if implemented correctly, can yield an over 50% speed-up.

We bound the hereditary discrepancy of a hypergraph $\mathcal{H}$ in two colors in terms of its hereditary discrepancy in c colors. We show that $\mathrm{herdisc}(\mathcal{H},2)\leq Kc$ $\mathrm{herdisc}(\mathcal{H},c)$, where K is some absolute constant. This bound is sharp apart from the absolute constant.