Tight Lower Bounds for Certain Parameterized NP-Hard Problems.
Jianer ChenBenny ChorMike FellowsXiuzhen HuangDavid W. JuedesIyad A. KanjGe XiaPublished in: Computational Complexity Conference (2004)
Keyphrases
- lower bound
- np hard problems
- np hard
- upper bound
- knapsack problem
- constraint programming
- worst case
- optimal solution
- branch and bound
- branch and bound algorithm
- np complete
- scheduling problem
- objective function
- integer programming
- linear programming
- combinatorial search
- constraint satisfaction problems
- graph coloring
- special case
- state space
- heuristic search
- multi objective