The PI will study and attempt to improve the state of the art in fundamental areas of algorithms: linear time solution of systems of linear equations, matchings, and approximation. The basis of the linear system work is the recent breakthrough work of Spielman and Teng and the follow up work of Koutis, Miller, and Peng, who gave very efficient, near linear time algorithms for solving a large class of linear systems. The ideas in this scheme are intertwined with graph partitioning and metric approximation which the PI has long researched. The PI will also use ideas from Spielman and Teng to attack the matching or assignment problem; in particular, understanding graph sparsification techniques in terms of the matching problem. Finally, the investigator proposes to work on extending a recent breakthrough on the TSP problem that reduced the asymmetric version of the problem to one of finding a tree that crosses cuts expediently.
The solution of linear systems is central to a tremendous variety of engineering and scientific problems ranging from climate change, to building modeling, to jet engine design (essentially any problem dealing with simulating classical physics). The assignment problem which the PI proposes to investigate is central in numerous production and business applications: indeed, almost any application that assigns jobs to tasks efficiently. Finally, the TSP problem is a famously intriguing problem which is worth studying for its own sake and for the methodogical breakthroughs that its study typically leads to.
