The Alexander von Humboldt Foundation has granted ORIE professor David Williamson a prestigious Humboldt Research Award in recognition of his achievements. The award, valued at $80K, supports Williamson's stay at the Technical University of Berlin.
Each year the Alexander von Humboldt Foundation grants up to 100 Humboldt Research Awards to leading academics, regardless of discipline or nationality, who are invited to spend up to a year collaborating on a long-term research project at a research institution in Germany. ORIE Professor David Williamson is one of this year's winners, and is spending the year at the Technical University of Berlin as a Berlin Mathematical School Professor.
Williamson, who holds a joint appointment in ORIE and Computer and Information Science, seeks efficient algorithms that are provably close to optimal for a wide rannge of difficult problems in network design and scheduling. Such problems arise in many situations, including finding the best routes in networks - as exemplified by the classic Traveling Salesman Problem (TSP), which calls for the shortest route touching all members of a set of destinations.
Williamson, together with Cornell Jacob Gould Schurman Professor of Computer Science and OR field member Eva Tardos and coauthors, is also the winner of the Glover-Klingman Prize for the best 2009 paper published in the journal Networks. Their paper, "Approximating the Smallest k-edge Connected Spanning Subgraph by LP-Rounding." treats a variant of a central problem in graph theory, the theory devoted to the properties of graphs: sets of points (or nodes) connected by arcs (or edges). This central problem, which has application in the design of telecommunication, transportation and other networks, is to find a smallest, or least-cost, subset of edges that connects all of the nodes, directly or indirectly.
In their paper, Williamson, Tardos, Gabow and Goemans seek an algorithm to determine (if there is one) a smallest subset of edges in a multiply-connected network such that any k-1 edges can be removed and the graph will still be connected, where k is an arbitrary number specified in advance. "This is a basic problem in network design," according to the authors, and like the TSP is known to be in a class of problems known to be hard to compute. As a result, researchers such as the authors seek algorithms that find approximate solutions as well as lower bounds on how close they are to optimum.
Williamson joined ORIE from IBM, where he was Senior Manager of the Computer Science Principles and Methodologies Department at the IBM Almaden Research Center. He received his Ph.D. in Computer Science from MIT.
Cornell computer science professor Johannes Gehrke is also a recipient of a Humboldt Research Award this year.
Cornell faculty members Ailong Ke, David Shmoys and Martin T. Wells have been elected fellows of the American Association for the Advancement of Science, the world’s largest general scientific society... Read more about Three faculty members elected AAAS fellows
ORIE third-year student Kiran Chandrasekher ’25 has won a 2024 Goldwater Scholarship. The Goldwater Scholarship is one of the most competitive scholarships offered to undergraduates in the US pursuing... Read more about ORIE junior wins Goldwater Scholarship
David Williamson has been appointed as the next Director of the School of Operations Research and Information Engineering (ORIE). In addition to his role as a professor in ORIE, Williamson is also a... Read more about David Williamson appointed next ORIE director
