A probabilistic PTAS for shortest common superstring

DOI10.1016/j.tcs.2013.12.005zbMath1279.68360OpenAlexW2023382282MaRDI QIDQ393897

Kai Plociennik

Publication date: 24 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.12.005

zbMATH Keywords

approximationaverage-case analysisgreedy superstringsemi-random inputshortest common superstring

Mathematics Subject Classification ID

Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• The greedy algorithm for shortest superstrings
• Why greed works for shortest common superstring problem
• A greedy approximation algorithm for constructing shortest common superstrings
• On finding minimal length superstrings
• More on the complexity of common superstring and supersequence problems
• Greedy algorithms for the shortest common superstring that are asymptotically optimal
• Approximation algorithms for the shortest common superstring problem
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Smoothed analysis of algorithms
• Algorithms on Strings, Trees and Sequences
• Linear approximation of shortest superstrings
• Rotations of Periodic Strings and Short Superstrings
• The shortest common superstring problem: average case analysis for both exact and approximate matching
• \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring
• Elements of Information Theory
• Mathematical Foundations of Computer Science 2005
• Lyndon Words and Short Superstrings

This page was built for publication: A probabilistic PTAS for shortest common superstring