Talk: 'The Shortest Cycle Problem and Related Graph Theory and Algorithms'
February 23, 2018
11:00 am-12:00 pm
Integrative Learning Center
UMass Amherst Campus
Handicap access available
Professor James Orlin presents the fastest algorithm for finding a shortest cycle in a directed graph. The new algorithm is actually simpler than previous fast algorithms for the shortest cycle problem. He will also present a very brief history of algorithms for finding cycles in graphs as well as some new (and old) complexity results about cycles in graphs.
Orlin is the E. Pennell Brooks Professor of Management at the MIT Sloan School. He is best known for his research on obtaining faster algorithms for problems in network and combinatorial optimization and for his text with Ravi Ahuja and Tom Magnanti titled "Network Flows: Theory, Algorithms, and Applications." He has won various awards for his co-authored publications: the 1993 Lanchester Prize for the best publication in O.R., the 2004 EXPLOR Award for leadership in online marketing research, the 2007 INFORMS Computing Society Prize for research in the interface of O.R. and computer science, the 2008 IEEE Leonard G. Abraham Prize for research in communication theory, the 2008 INFORMS Koopman Prize for research in military operations research, the 2011 IEEE Bennett Prize for research in communication theory, and the 2016 ACM SIGecom Test of Time Award, for a paper published between 10 and 25 years ago that has had “significant impact on research or applications that exemplify the interplay of economics and computation.”
The Integrative Learning Center is located in the center of campus, between the campus pond and the Campus Center.