1 Search Results for "Juhel, Samuel"


Document
Practical lower and upper bounds for the Shortest Linear Superstring

Authors: Bastien Cazaux, Samuel Juhel, and Eric Rivals

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)


Abstract
Given a set P of words, the Shortest Linear Superstring (SLS) problem is an optimisation problem that asks for a superstring of P of minimal length. SLS has applications in data compression, where a superstring is a compact representation of P, and in bioinformatics where it models the first step of genome assembly. Unfortunately SLS is hard to solve (NP-hard) and to closely approximate (MAX-SNP-hard). If numerous polynomial time approximation algorithms have been devised, few articles report on their practical performance. We lack knowledge about how closely an approximate superstring can be from an optimal one in practice. Here, we exhibit a linear time algorithm that reports an upper and a lower bound on the length of an optimal superstring. The upper bound is the length of an approximate superstring. This algorithm can be used to evaluate beforehand whether one can get an approximate superstring whose length is close to the optimum for a given instance. Experimental results suggest that its approximation performance is orders of magnitude better than previously reported practical values. Moreover, the proposed algorithm remainso efficient even on large instances and can serve to explore in practice the approximability of SLS.

Cite as

Bastien Cazaux, Samuel Juhel, and Eric Rivals. Practical lower and upper bounds for the Shortest Linear Superstring. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{cazaux_et_al:LIPIcs.SEA.2018.18,
  author =	{Cazaux, Bastien and Juhel, Samuel and Rivals, Eric},
  title =	{{Practical lower and upper bounds for the Shortest Linear Superstring}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.18},
  URN =		{urn:nbn:de:0030-drops-89530},
  doi =		{10.4230/LIPIcs.SEA.2018.18},
  annote =	{Keywords: greedy, approximation, overlap, Concat-Cycles, cyclic cover, linear time, text compression}
}
  • Refine by Author
  • 1 Cazaux, Bastien
  • 1 Juhel, Samuel
  • 1 Rivals, Eric

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Theory of computation → Discrete optimization

  • Refine by Keyword
  • 1 Concat-Cycles
  • 1 approximation
  • 1 cyclic cover
  • 1 greedy
  • 1 linear time
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail