Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10455534" target="_blank" >RIV/00216208:11320/22:10455534 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1145/3519935.3520001" target="_blank" >https://doi.org/10.1145/3519935.3520001</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/3519935.3520001" target="_blank" >10.1145/3519935.3520001</a>

Result language
angličtina
Original language name
Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios
Original language description
In the Shortest Superstring problem, we are given a set of strings and we are asking for a common superstring, which has the minimum number of characters. The Shortest Superstring problem is NP-hard and several constant-factor approximation algorithms are known for it. Of particular interest is the GREEDY algorithm, which repeatedly merges two strings of maximum overlap until a single string remains. The GREEDY algorithm, being simpler than other well-performing approximation algorithms for this problem, has attracted attention since the 1980s and is commonly used in practical applications. Tarhio and Ukkonen (TCS 1988) conjectured that GREEDY gives a 2-approximation. In a seminal work, Blum, Jiang, Li, Tromp, and Yannakakis (STOC 1991) proved that the superstring computed by GREEDY is a 4-approximation, and this upper bound was improved to 3.5 by Kaplan and Shafrir (IPL 2005). We show that the approximation guarantee of GREEDY is at most (13+ root 57)/6 approximate to 3.425. Furthermore, we prove that the Shortest Superstring can be approximated within a factor of (37+root 57)/18 approximate to 2.475, improving slightly upon the currently best 2 11 23 -approximation algorithm by Mucha (SODA 2013).
Czech name
—
Czech description
—

Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GX19-27871X" target="_blank" >GX19-27871X: Efficient approximation algorithms and circuit complexity</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
PROCEEDINGS OF THE 54TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '22)
ISBN
978-1-4503-9264-8
ISSN
0737-8017
e-ISSN
—
Number of pages
14
Pages from-to
317-330
Publisher name
ASSOC COMPUTING MACHINERY
Place of publication
NEW YORK
Event location
Rome
Event date
Jun 20, 2022
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000852709400028

Similar results(10)