The Smoothed Complexity of Edit Distance

DOI10.1007/978-3-540-70575-8_30zbMath1153.68563OpenAlexW1577678042MaRDI QIDQ3521932

Alexandr Andoni, Robert Krauthgamer

Publication date: 28 August 2008

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-70575-8_30

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Related Items (3)

Global alignment of molecular sequences via ancestral state reconstruction ⋮ The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics ⋮ Why greed works for shortest common superstring problem

This page was built for publication: The Smoothed Complexity of Edit Distance