Approximation Guarantees for Shortest Superstrings: Simpler and Better.

Matthias Englert Nicolaos Matsakis Pavel Veselý

Published in: ISAAC (2023)

Keyphrases

approximation guarantees
greedy algorithm
approximation algorithms
np hard
approximation ratio
lower bound
objective function
shortest path
greedy algorithms
constant factor
worst case
linear programming relaxation
multistage
branch and bound
small number
upper bound
evolutionary algorithm