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.