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


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(n2dφ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((n2dφ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


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.


  Payday Loans In North Carolina. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.