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.

算法的研究产生了许多在数学和广泛有用的技术。 从线性编程到密码学到几何形状，再到实现优化问题的方法。 在算法研究中，将世界的明显观点添加到了引人注目的研究领域。该项目将研究线性编程的更好算法，并探索和扩展最近的工作近似算法，并将探索具有世界化观点的算法。 最新的突破性工作在解决线性系统以及在线优化方面的发展，使得为线性编程的更好算法开发了可能性。 该项目将追求这个目标。第二特异性领域是近似算法的研究，该算法已成为算法研究的主要重点。 在范围内，诸如寻找稀疏削减，不相交的路径和旅行推销员问题之类的问题已成为开发新算法技术的沃土。 研究人员已经做了一些此项工作，并建议进一步研究这一领域。 最后，这个项目将超越``我们知道如何解决它''的线性编程案例，并且``我们将尽可能地做到'''approximation算法的概念'到``我们如何在由algorithm''视图中生成的数据生成的数据。 如今，随着生物学数据的生产的不断增长，后一种观点特别适合；该数据是相应地生成科学验证的统计模型的。 在Thisarea中已经完成了非常有趣的工作，但是该领域正在乞求从那些训练有素的算法中参与更多的参与。该项目的智力优点在于算法的进一步发展技术，以及传统思想与统计学中的思想的融合。 更广泛的影响在于算法在此项目中解决的问题的许多应用。 应用领域包括网络设计，分子生物学，推荐系统和优化。 研究人员也将向算法的研究生和本科课程介绍该项目的想法。