A probabilistic PTAS for shortest common superstring

DOI10.1016/J.TCS.2013.12.005zbMATH Open1279.68360OpenAlexW2023382282MaRDI QIDQ393897FDOQ393897

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

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

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)

Cites Work

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

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)