Explorations in Algorithms

点击翻译按钮获取中文摘要

The study of algorithms has yielded numerous techniques that are bothinteresting mathematically and broadly useful. This ranges fromlinear programming to cryptography to geometry to approaches forapproximately solving optimization problems. The addition of astatistical view of the world to the study of algorithms has also beena compelling area of study. This project will study better algorithmsfor linear programming as well as, explore and expand on recent workin approximation algorithms, and will explore algorithms with astatistical view of the world. Recent breakthrough work onsolving linear systems as well as developments in online optimization,make the development of better algorithms for linear programming atantalizing possibility. This project will pursue this goal. A secondspecific area is the study of approximation algorithms which has, inrecent years, been a primary focus of algorithms research. Inparticular, problems such as finding sparse cuts, disjoint paths, andthe traveling salesman problem have been fertile ground for developingnew algorithmic techniques. The researcher has done some of thiswork, and proposes to study this area further. Finally, this projectwill go beyond the ``we know how to solve it'' case of linearprogramming, and the ``we will do as well as we can'' notion ofapproximation algorithms, to a ``how do we do on data generated by theworld'' view of algorithms. This latter view is especiallyappropriate these days with the growing production of biological data;This data is generated accordingly to scientifically validatedstatistical models. Quite interesting work has been done in thisarea, but the field is begging for more involvement from those trainedin algorithms.The intellectual merit of this project lies in the further developmentof mathematical techniques for algorithms, and the blending oftraditional ideas with ideas in statistics. The broader impacts liein the many applications of algorithms for the problems addressed inthis project. Application areas include network design, molecular biology, recommendation systems, and optimization. The researcher will introduce ideas from this project into graduate and undergraduate classes in algorithms as well.