The Library
Approximation guarantees for shortest superstrings : simpler and better
Tools
Englert, Matthias, Matsakis, Nicolaos and Veselý, Pavel (2023) Approximation guarantees for shortest superstrings : simpler and better. In: 34th International Symposium on Algorithms and Computation (ISAAC 2023), Kyoto, Japan, 3–6 Dec 2023. Published in: Proceedings of the 34th International Symposium on Algorithms and Computation (ISAAC 2023) , 286 29:1-29:17. doi:10.4230/LIPIcs.ISAAC.2023.29 (In Press)
|
PDF
WRAP-Approximation-guarantees-shortest-superstrings-simpler-better-2023.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (801Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.ISAAC.2023.29
Abstract
The Shortest Superstring problem is an NP-hard problem, in which given as input a set of strings, we are looking for a string of minimum length that contains all input strings as substrings. The Greedy Conjecture (Tarhio and Ukkonen, 1988) states that the GREEDY algorithm, which repeatedly merges the two strings of maximum overlap, is 2-approximate. We have recently shown (STOC 2022) that the approximation guarantee of GREEDY is at most (13+√{57})/6 ≈ 3.425. Before that, the best established upper bound for this was 3.5 by Kaplan and Shafrir (IPL 2005), which improved upon the upper bound of 4 by Blum et al. (STOC 1991). To derive our previous result, we established two incomparable upper bounds on the overlap sum of all cycle-closing edges in an optimal cycle cover and utilized lemmas of Blum et al. We improve the more involved one of the two bounds and, at the same time, make its proof more straightforward. This results in an improved approximation guarantee of (√{67}+2)/3 ≈ 3.396 for GREEDY. Additionally, our result implies an algorithm for the Shortest Superstring problem having an approximation guarantee of (√{67}+14)/9 ≈ 2.466, improving slightly upon the previously best guarantee of (√{57}+37)/18 ≈ 2.475 (STOC 2022).
Item Type: | Conference Item (Paper) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
|||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
Library of Congress Subject Headings (LCSH): | Machine theory, Computational complexity, Text processing (Computer science) , Computer algorithms , Approximation algorithms | |||||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||
Journal or Publication Title: | Proceedings of the 34th International Symposium on Algorithms and Computation (ISAAC 2023) | |||||||||
Publisher: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||
Official Date: | 28 November 2023 | |||||||||
Dates: |
|
|||||||||
Volume: | 286 | |||||||||
Page Range: | 29:1-29:17 | |||||||||
Article Number: | 26 | |||||||||
DOI: | 10.4230/LIPIcs.ISAAC.2023.29 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | In Press | |||||||||
Access rights to Published version: | Open Access (Creative Commons) | |||||||||
Date of first compliant deposit: | 9 October 2023 | |||||||||
Date of first compliant Open Access: | 11 October 2023 | |||||||||
RIOXX Funder/Project Grant: |
|
|||||||||
Conference Paper Type: | Paper | |||||||||
Title of Event: | 34th International Symposium on Algorithms and Computation (ISAAC 2023) | |||||||||
Type of Event: | Conference | |||||||||
Location of Event: | Kyoto, Japan | |||||||||
Date(s) of Event: | 3–6 Dec 2023 | |||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year