## Invited Session Thu.1.H 3021

#### Thursday, 10:30 - 12:00 h, Room: H 3021

**Cluster 2: Combinatorial optimization** [...]

### Smoothed analysis of algorithms

**Chair: Alantha Newman and Heiko Röglin**

**Thursday, 11:00 - 11:25 h, Room: H 3021, Talk 2**

**Tobias Brunsch**

Improved smoothed analysis of multiobjective optimization

**Coauthor: Heiko Röglin**

**Abstract:**

We present several new results about smoothed analysis of multiobjective optimization problems. Particularly, we consider problems in which *d* linear and one arbitrary objective function are to be optimized over a set **S** ⊆ {0,1}^{n} of feasible solutions. The coefficients of the linear objectives are subject to random perturbations specified by an adversary whose power is limited by a perturbation parameter *φ*. We improve the previously best known bound for the smoothed number of Pareto-optimal solutions to *O(n*^{2d}φ^{d}) for natural perturbation models. Additionally, we show that for any constant *c* the *c*-th moment of the smoothed number of Pareto-optimal solutions is bounded by *O((n*^{2d}φ^{d})^{c}). This improves the previously best known bounds significantly. Furthermore, we address the criticism that the perturbations in smoothed analysis destroy the zero-structure of problems by giving a polynomial bound for the smoothed number of Pareto-optimal solutions for zero-preserving perturbations. One consequence of this result is that the smoothed number of Pareto-optimal solutions is polynomially bounded for polynomial objective functions.

**Thursday, 11:30 - 11:55 h, Room: H 3021, Talk 3**

**Kai Plociennik**

A probabilistic PTAS for shortest common superstring

**Abstract:**

We consider approximation algorithms for the shortest common superstring problem (SCS). It is

well-known that there is a constant *f > 1* such that there is no efficient approximation algorithm

for SCS achieving a factor of at most *f* in the worst case, unless P=NP. We study SCS on random

inputs and present an approximation scheme that achieves, for every *ε > 0*, a

*1+ε*-approximation in expected polynomial time. This result applies not only if the

letters are chosen independently at random, but also to the more realistic mixing model, which

allows for dependencies among the letters of the random strings. Our result is based on a sharp tail

bound on the optimal compression, which improves a previous result by Frieze and Szpankowski.