The Prague Stringology Conference 2004
Conditional Inequalities and the Shortest Common Superstring Problem
| Abstract: |
|
We investigate the shortest common superstring problem (SCSSP). As SCSSP is
APX-complete it cannot be approximated within an arbitrarily small
performance ratio. One heuristic that is widely used is the notorious greedy
heuristic. It is known, that the performance ratio of this heuristic is at
least 2 and not worse than 4. It is conjectured that the greedy heuristic's
performance ratio is in fact 2 (the greedy conjecture). Even the best
algorithms introduced for SCSSP can only guarantee an upper bound of 2.5.
In [1] an even stronger version of the greedy conjecture is proven for a restricted class of orders in which strings are merged. We extend these results by broadening the class for which this stronger version can be established. We also show that the Triple inequality, introduced in [1] and crucial for their results, is inherently insufficient to carry the proof for the greedy conjecture in the general case. Finally we describe how linear programming can be used to support research along this line. [1] M. Weinard and G. Schnitger: On the Greedy Superstring Conjecture. In Proceedings of the 23rd Conference on Foundations of Software Technology and Theoretical Computer Science, Mumbai, India, LNCS 2914, 387-398, December 2003. |
| Download paper: |  |
 |
| PostScript |