How Can We Explain the Success of Heuristic Algorithms?


Richard M. Karp


Hard optimization problems arise in virtually every area of human activity, and we need to rely on heuristics to deal with them in practice. It is not an overstatement to say that the progress of society depends on the effectiveness of heuristics, and yet we have no rigorous understanding of why they work, or when they don't. I will discuss some fledgling efforts to solve this riddle.