Approximation Hardness for Small Occurrence Instances of NP-Hard Problem
Janka ChlebíkováMiroslav ChlebíkPublished in: Electron. Colloquium Comput. Complex. (2002)
Keyphrases
- np hard
- approximation algorithms
- approximation ratio
- np complete
- np hardness
- medium size
- worst case
- scheduling problem
- constant factor approximation
- special case
- linear programming
- lower bound
- computational complexity
- minimum cost
- optimal solution
- randomly generated
- shortest common supersequence
- polynomial time approximation
- integer programming
- error bounds
- small number
- branch and bound algorithm
- approximation guarantees
- closed form
- approximation methods
- greedy heuristic
- closely related
- exact methods
- phase transition
- boolean variables
- min sum
- training instances
- decision problems
- information theoretic
- random instances
- training data
- genetic algorithm
- neural network