Approximation Schemes for Optimization

How can we efficiently aggregate rankings, cut a graph into two parts with many edges between them, pack items into bins, cluster items using pairwise similarity information, route vehicles in the Euclidean plane, or construct a Steiner tree in a planar graph? All these examples of optimization problems are NP-hard, yet, under some mild assumptions, they all have near-optimal solutions that can be computed in (high) polynomial time. I will present a few algorithmic techniques and their application to the above problems.

Speaker Details

Claire Mathieu, an alumnus from Ecole Normale Superieure, has held positions at CNRS, Orsay University, Institut Universitaire de France (junior member), Ecole Polytechnique, and Brown University, where she is currently a professor. She has done postdocs and long-term visits at several US universities: Dimacs, Princeton, ICSI, Berkeley, and Cornell. She has also visited industrial research labs: NEC, AT&T, and MSR Redmond.

Her research area spans the design and analysis of algorithms. In particular, in various collaborations she has developed the first approximation schemes for strip packing, completion time scheduling, metric maxcut, rank aggregation, counting dimer configurations in lattices, vehicle routing (quasi-PTAS), network design on planar graphs, broadcast disk scheduling, weighted Huffman coding, and other hard optimization problems. She is also interested in streaming algorithms, algorithmic game theory, and other emerging areas within Algorithms.

She primarily serves the research community by being journal editor (Algorithmica until 2010, SiComp since 2010) and by participating in conference program committees on a regular basis (SODA, STOC, FOCS, and others). She was program chair of SODA 2009.

Outside work, Claire enjoys hiking.

Date:
Speakers:
Claire Mathieu
Affiliation:
Brown University
    • Portrait of Jeff Running

      Jeff Running