Claire Mathieu
Approximation schemes on planar graphs
Methods are currently being developed to design approximation schemes for optimization problems in planar graphs. The traveling salesman problem, the Steiner tree problem, the Steiner forest problem have one by one been resolved. The talk will focus on techniques used, including bounded tree-width graphs, spanners, and brick decompositions.
Biography
Claire Mathieu received her PhD in 1988 from the University of Paris-Sud. Aside from post-doctoral, visitor, and consulting appointments, she was a junior researcher at CNRS, a professor at Universite Paris-Sud, a junior member of Institut Universitaire de France, and a professor at Ecole Polytechnique. She is currently a professor at Brown university.
During her PhD, her research started with a collaboration with Andy Yao on the computation of boolean functions when querying the bits may lead to erroneous answers, and a collaboration with Jeff Vitter on the average-case analysis of a lazy data structure. Her main focus is the design and analysis of approximation algorithms for hard combinatorial optimization problems such as bin-packing, scheduling, maxcut, vehicle routing, and clustering.
