Past Awards
The 2023 INFORMS John von Neumann Theory Prize is awarded to Christos H. Papadimitriou and Mihalis Yannakakis for their fundamental and sustained contributions to computational complexity theory and providing an understanding of the limits of efficient solvability for a wide range of decision and optimization problems central to operations research and the management sciences (OR/MS).
As an example of a major contribution, Papadimitriou and Yannakakis introduced Max-NP and Max-SNP, natural variants of the NP complexity class, comprised of certain optimization problems that can be approximated with bounded error (Papadimitriou & Yannakakis 1988). Within these classes, they showed that several common problems have polynomial-time approximation schemes only if the whole class does.
Other major contributions include establishing the NP-completeness of the Euclidean traveling salesman problem (Papadimitriou 1977), an early tour de force in the traditional framework, and characterizing the complexity of many other natural problems. Examples include: checking the validity of facets of polytopes (Papadimitriou and Yannakakis 1984); determining whether a problem has a unique optimal solution (Papadimitriou 1984); local search (Johnson, Papadimitriou and Yannakakis 1988); the extension complexity of LP formulations for the matching and traveling salesman problems (Yannakakis 1988), a paper that erected a firewall to scores of would-be P=NP proofs; and computing Nash equilibria. In the online setting, their work on finding online solutions with a bounded competitive ratio (Papadimitriou and Yannakakis 1991, 1993) has been highly influential. Finally, the introduction of the concept of the “price of anarchy” (Koutsoupias & Papadimitriou 1999, Yannakakis 2009) was a catalyst for major developments in algorithmic game theory, substantially reinforcing the links between economics, computer science, and operations research.
Such contributions have addressed modeling and computational issues at the core of multiple areas in OR/MS; they have helped characterize what is possible and inherently impossible, and more broadly, have provided new tools for such characterizations. Their work has resolved fundamental open problems and sparked new and fruitful lines of research, leading to a better understanding of the field of optimization at large.