 |
Center for Nonlinear Studies |
This talk will demonstrate work on theoretical foundations for simple greedy heuristics. Particularly, similar to the notion approximation algorithms with respect to their approximation ratios, we prove that several simple greedy heuristics in the sense that it is NP-hard to recognize the gap between the greedy solution and the optimal solution. We show results for several well known problems such as maximum clique, maximum independent set, minimum vertex coloring and discuss extensions of these results to a more general class of problems.
Host: Aric Hagberg