Explorations in Algorithms

算法探索

• 批准号: 0830797
• 负责人: Satish Rao
• 金额: $ 32.85万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830797&HistoricalAwards=false
• 关键词: Explorations; 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.

算法的研究已经产生了许多在数学上有趣且广泛有用的技术。 其范围从线性规划到密码学到几何到近似解决优化问题的方法。 将世界统计观点添加到算法研究中也是一个引人注目的研究领域。该项目将研究更好的线性规划算法，探索和扩展近似算法的最新工作，并将探索具有统计世界观的算法。 最近在解决线性系统方面的突破性工作以及在线优化的发展，使得开发更好的线性规划算法成为可能。 该项目将追求这一目标。第二个特定领域是近似算法的研究，近年来，它已成为算法研究的主要焦点。 特别是，诸如寻找稀疏切割、不相交路径和旅行商问题等问题已经成为开发新算法技术的沃土。 研究人员已经做了一些这方面的工作，并建议进一步研究这一领域。 最后，这个项目将超越线性规划的“我们知道如何解决它”的情况，以及近似算法的“我们将尽我们所能”的概念，到“我们如何处理生成的数据”根据算法的世界观。 随着生物数据产量的不断增长，后一种观点尤其适用；这些数据是根据经过科学验证的统计模型生成的。 在这个领域已经做了相当有趣的工作，但是这个领域需要算法训练者的更多参与。这个项目的智力价值在于算法数学技术的进一步发展，以及传统思想与统计学思想的融合。 更广泛的影响在于算法在该项目中解决的问题的许多应用。 应用领域包括网络设计、分子生物学、推荐系统和优化。 研究人员还将将该项目的想法引入研究生和本科生的算法课程中。