When and How Can We Compute Approximately Optimal Solutions to Intractable Computational Problems?
The discovery of NP-completeness by computer scientists in the 1970s showed that many computational problems in a variety of disciplines do not have efficient algorithms (assuming the classes P and NP are different, as is widely believed). This was a profound discovery. However, in practice it often suffices to solve problems approximately: say, to obtain a solution of cost within 10% of optimum. Can efficient algorithms find approximately optimal solutions? The classical theory of NP-completeness didn’t address or preclude this possibility. Research in the past two decades has answered the approximability issue for a large subset of NP-complete problems. We know the precise approximation threshold that can be achieved by efficient algorithms, and also know that improving upon that threshold is no easier than exact optimization. The former is the domain of “approximation algorithms,” and the latter of the theory of “probabilistically checkable proofs.” This theory makes connections with a host of other disciplines and yields surprising results such as the PCP Theorem, which states that mathematical proofs can be checked by examining a constant number of bits in them (this constant is independent of the size of the proof).
Suggested Reading:
Chapter 8 on NP-completeness from Algorithms by Dasgupta, Papadimitriou & Vazirani
NP-completeness: A Retrospective
The Approximability of NP-hard Problems
About the Speaker:
Sanjeev Arora is the Charles C. Fitzmorris Professor of Computer Science at Princeton University. His research area is Theoretical Computer Science. Specific topics that Arora has worked on: Computational Complexity, Probabilistically Checkable Proofs (PCPs), computing approximate solutions to NP-hard problems, geometric embedding of metric spaces, unique games conjecture, complexity of financial derivatives, provable bounds for Machine Learning.
Arora received his PhD from UC Berkeley in 1994. In 2012 he received a Simons Investigator award and the AMS-MOS D.R. Fulkerson Prize. Past awards include ACM-Infosys Foundation Award in the Computing Sciences; Best paper, IEEE Foundations of Computer Science; EATCS-SIGACT Goedel Prize; elected ACM Fellow; Engineering Council Teaching Award for Fall 2008, Princeton University.
