A probabilistic PTAS for shortest common superstring

DOI10.1016/J.TCS.2013.12.005MaRDI QIDQ393897zbMATH OpenOpenAlexFDO

Authors 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) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• A Probabilistic PTAS for Shortest Common Superstring
• Greedy algorithms for the shortest common superstring that are asymtotically optimal
• Greedy algorithms for the shortest common superstring that are asymptotically optimal
• Approximation algorithms for the shortest common superstring problem
• The shortest common superstring problem: average case analysis for both exact and approximate matching

Cites work

• scientific article; zbMATH DE number 1420898 (Why is no real title available?)
• A greedy approximation algorithm for constructing shortest common superstrings
• Algorithms on Strings, Trees and Sequences
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation algorithms for the shortest common superstring problem
• Elements of Information Theory
• Greedy algorithms for the shortest common superstring that are asymptotically optimal
• Linear approximation of shortest superstrings
• Lyndon words and short superstrings
• Mathematical Foundations of Computer Science 2005
• More on the complexity of common superstring and supersequence problems
• On finding minimal length superstrings
• Rotations of Periodic Strings and Short Superstrings
• Simpler approximation of the maximum asymmetric traveling salesman problem
• Smoothed analysis of algorithms
• The greedy algorithm for shortest superstrings
• The shortest common superstring problem: average case analysis for both exact and approximate matching
• Why greed works for shortest common superstring problem
• \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring

Cited in

(2)

• A Probabilistic PTAS for Shortest Common Superstring
• The shortest common superstring problem: average case analysis for both exact and approximate matching

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q393897)