Approximation Guarantees for Shortest Superstrings: Simpler and Better

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10475246" target="_blank" >RIV/00216208:11320/23:10475246 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.4230/LIPIcs.ISAAC.2023.29" target="_blank" >https://doi.org/10.4230/LIPIcs.ISAAC.2023.29</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.ISAAC.2023.29" target="_blank" >10.4230/LIPIcs.ISAAC.2023.29</a>

Result language

angličtina

Original language name

Approximation Guarantees for Shortest Superstrings: Simpler and Better

Original language description

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+6SQUARE ROOT57 ALMOST EQUAL TO 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 SQUARE ROOT67+23 ALMOST EQUAL TO 3.396 for GREEDY. Additionally, our result implies an algorithm for the Shortest Superstring problem having an approximation guarantee of SQUARE ROOT67+149 ALMOST EQUAL TO 2.466, improving slightly upon the previously best guarantee of SQUARE ROOT57+3718 ALMOST EQUAL TO 2.475 (STOC 2022).

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/GA22-22997S" target="_blank" >GA22-22997S: Efficient and Realistic Models in Computational Social Choice</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2023

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

Leibniz International Proceedings in Informatics, LIPIcs

ISBN

978-3-95977-289-1

ISSN

—

e-ISSN

—

Number of pages

17

Pages from-to

—

Publisher name

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Place of publication

Dagstuhl, Germany

Event location

Kyoto, Japan

Event date

Dec 3, 2023

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—