22 listopada 2022 11:15
[Seminarium ZOK] Nicolaos Matsakis: Improved Approximation Guarantees for Shortest Superstrings
Abstract:
In the Shortest Superstring problem, we are given a set of strings and
we are asking for a common superstring of them, having the minimum
number of characters. This problem is NP-hard and several
constant-factor approximation algorithms have been derived for it,
since the early 90's.
Of particular interest is the GREEDY algorithm, which repeatedly
merges two strings of maximum overlap until one string remains.
We show that the approximation guarantee of GREEDY is at most 3.425,
improving upon the previously best upper bound of 3.5 for this
algorithm. Furthermore, we prove that the Shortest Superstring can be
approximated within a factor of 2.475.
Joint work with Matthias Englert and Pavel Veselý.
Appeared at: STOC 2022.
ArXiv link: https://arxiv.org/abs/2111.03968