National Academy of Sciences honors Ola Svensson
Ola Svensson honored with the Michael and Sheila Held Prize © Alban Kakulya - NAS, 2019
Ola Svensson, Associate Professor at the School of Computer and Communication Sciences at EPFL, will receive the 2019 Michael and Sheila Held Prize for his Major Contribution to Science.
Professor 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 Professor Svensson authored an award-winning new algorithm for the symmetric traveling salesman problem that developed breakthroughs in computational optimization and graph-theoretic algorithms. Ola 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.
Ola 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.