AG 1, AG 4, RG1, MMCI, AG 3, AG 5   Info

AG Audience

English

60 Minutes

Saarbrücken

In the talk, we present a new result on 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 \eps>0, (1+\eps)-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 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.

Bodo Manthey

5502

--email hidden

passcode not visible

logged in users only