A probabilistic PTAS for shortest common superstring
type: Item
instance of: scholarly article
title: A probabilistic PTAS for shortest common superstring
zbMATH Open document ID: 1279.68360
author: Kai Plociennik
published in: Theoretical Computer Science
publication date: 2014-01-24T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q32
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 6249999
zbMATH Keywords: shortest common superstring
zbMATH Keywords: approximation
zbMATH Keywords: average-case analysis
zbMATH Keywords: semi-random input
zbMATH Keywords: greedy superstring
MaRDI profile type: Publication
full work available at URL: j.tcs.2013.12.005
OpenAlex ID: W2023382282
cites work: Algorithms on Strings, Trees and Sequences
cites work: On finding minimal length superstrings
cites work: More on the complexity of common superstring and supersequence problems
cites work: Linear approximation of shortest superstrings
cites work: Rotations of Periodic Strings and Short Superstrings
cites work: \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring
cites work: Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
cites work: Simpler approximation of the maximum asymmetric traveling salesman problem
cites work: Lyndon Words and Short Superstrings
cites work: A greedy approximation algorithm for constructing shortest common superstrings
cites work: Approximation algorithms for the shortest common superstring problem
cites work: The greedy algorithm for shortest superstrings
cites work: Q4944967
cites work: Mathematical Foundations of Computer Science 2005
cites work: Smoothed analysis of algorithms
cites work: Greedy algorithms for the shortest common superstring that are asymptotically optimal
cites work: Elements of Information Theory
cites work: The shortest common superstring problem: average case analysis for both exact and approximate matching
cites work: Why greed works for shortest common superstring problem
cites work: Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
DOI: 10.1016/J.TCS.2013.12.005
description: scientific article; zbMATH DE number 6249999