Dick Karp, University of California, Berkeley

Abstract

Algorithmic complexity theory measures the performance of an algorithm principally by its worst-case asymptotic running time, whereas practitioners tend to assess an algorithm by its observed performance on typical instances.  These two approaches often yield similar conclusions, but striking differences can occur. After reviewing the theoretical background of NP-completeness and hardness of approximation, we will compare and contrast the approaches in some important cases: propositional satisfiability, linear programming, integer programming, the traveling-salesman problem and bin packing.

Slides     Video