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.

对算法的研究已经产生了大量的技术，这些技术在数学上很有趣，而且非常有用。 这范围从线性规划到密码学到几何学到近似解决优化问题的方法。 在算法研究中加入统计世界观也是一个引人注目的研究领域。这个项目将研究线性规划的更好的算法，以及探索和扩展最近的工作近似算法，并将探索具有统计世界观的算法。 近年来，线性规划问题的研究取得了突破性的进展，在线优化技术的发展，使得线性规划问题的求解成为可能。 本项目将努力实现这一目标。第二个具体领域是研究近似算法，近年来，它一直是算法研究的主要焦点。 特别是，问题，如寻找稀疏削减，不相交的路径，和旅行推销员的问题一直是肥沃的土壤，发展新的算法技术。 研究者在此基础上做了一些工作，并提出了进一步的研究方向. 最后，这个项目超越了线性规划的“我们知道如何解决它”的情况，以及近似算法的“我们会尽我们所能”的概念，以“我们如何处理世界产生的数据”的算法观点。 后一种观点尤其适用于生物数据日益增长的今天;这些数据是根据科学验证的统计模型生成的。 在这一领域已经做了相当有趣的工作，但该领域正在乞求那些受过算法训练的人更多地参与进来。这个项目的智力价值在于进一步发展算法的数学技术，以及传统思想与统计思想的融合。 更广泛的影响在于算法在这个项目中解决的问题的许多应用。 应用领域包括网络设计、分子生物学、推荐系统和优化。 研究人员将把这个项目的想法引入到研究生和本科生的算法课程中。