Communications of the ACM
2019 Michael and Sheila Held Prize
Ola Svensson of the School of Computer and Communication Sciences at EPFL, the Federal Institute of Technology in Lausanne, Switzerland, will receive the 2019 Michael and Sheila Held Prize.
Credit: National Academy of Sciences
Ola Svensson, of the School of Computer and Communication Sciences at Ecole polytechnique fédérale de Lausanne, (EPFL, the Federal Institute of Technology in Lausanne, Switzerland), will receive the 2019 Michael and Sheila Held Prize.
Svensson has delivered a series of groundbreaking new algorithms for the traveling salesman problem, one of the most heavily studied and important questions in theoretical computer science.
The traveling salesman problem seeks to determine the shortest possible route for a person to take while visiting a given number of cities and returning to their point of origin. First posited in 1930, the problem is considered a benchmark in optimization.
In 2011 Svensson authored an award-winning new algorithm for the symmetric traveling salesman problem that developed breakthroughs in computational optimization and graph-theoretic algorithms. Svensson also presented a new approach for the asymmetric variant in 2015. Two additional co-authored papers followed, culminating in the first constant-factor approximation guarantee and collectively contributing several new ideas to the field of combinatorial optimization.
Svensson's work outside of the traveling salesman problem has contributed additional new ideas, most recently moving forward on derandomizing a probabilistic algorithm that has been a major focus of research for nearly three decades.
The Michael and Sheila Held Prize is presented annually and carries with it a $100,000 prize. The prize honors outstanding, innovative, creative, and influential research in the areas of combinatorial and discrete optimization, or related parts of computer science, such as the design and analysis of algorithms and complexity theory. This $100,000 prize is intended to recognize recent work (defined as published within the last eight years). The prize was established in 2017 by the bequest of Michael and Sheila Held.
From National Academy of Sciences
View Full Article
No entries found