On the Worst-Case Behaviour of Some Approximation Algorithms for the Shortest Common Supersequence of k Strings.
Robert W. IrvingCampbell FraserPublished in: CPM (1993)
Keyphrases
- shortest common supersequence
- approximation algorithms
- np hard
- worst case
- special case
- minimum cost
- lower bound
- scheduling problem
- vertex cover
- np hardness
- optimal solution
- average case
- facility location problem
- network design problem
- integer programming
- open shop
- constant factor
- linear programming
- computational complexity
- approximation ratio
- branch and bound algorithm
- upper bound
- primal dual
- constraint satisfaction problems
- randomized algorithms
- set cover
- greedy heuristic
- error bounds
- greedy algorithm
- sample size
- linear program
- undirected graph
- polynomial time approximation
- approximation schemes
- knapsack problem
- combinatorial auctions
- single machine