Designing Approximation Schemes
Support provided by National Science Foundation
Description
Design techniques for approximation algorithms.
The MaxCut problem strives to cut a graph into two pieces so that many edges cross the cut. The investigator studies new algorithms for MaxCut and other fundamental problems of combinatorial optimization. Why?
Because MaxCut is a simplified abstraction of a wide range of partitioning problems that are pervasive in applications such as scientific computing, sparse-matrix ordering for linear solvers, VLSI design, or task partitioning for parallel processors. The hope that the insight currently being gained on core theory problems can later translate into progress for more applied problems.
Thus, speeding up scientific computing applications could eventually have impacts on computer simulations for engineering problems such as automotive crash studies or for exploring major scientific issues such as global climate change.
How does the investigator proceed in her study?
In two ways: first, by exploring the power of the ""lift-and-project"" technique to obtain better linear programming models. Better, in the sense that adding constraints makes the linear program resemble more closely the real problem under study.
Lift-and-project
is an exciting technique whose power is not yet well understood. Second, by unifying and simplifying existing algorithms. Known dense graph algorithms can seem forbiddingly technical and numerous for prospective users. In contrast, the investigator is shifting the technical difficulties from the design to the analysis of algorithms, by proving that variants of greedy algorithms work well: greedy algorithms are simple, natural, and attractive, and thus much more likely to be used. Such foundational work on algorithms for combinatorial optimization is the way to engineering and technological improvements in the long term.
Principal Investigator
| Claire Mathieu |
Projects Supported
Details
| Amount: | 300000 |
| Dates: | September 2007 - August 2010 |
| Status: | Active |
| Page Owner: Amy Tarbox | Last Modified: Fri Feb 27 16:19:01 2009 |