Fundamental Algorithms based on Random Sampling, Convex Relaxation, and Spectral Analysis

基于随机采样、凸松弛和谱分析的基本算法

• 批准号: 0721503
• 负责人: Santosh Vempala
• 金额: $ 30万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-10-01 至 2010-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0721503&HistoricalAwards=false
• 关键词: Fundamental; Algorithms; based; Random; Sampling

Randomness and geometry play a central role in the discovery of polynomial- time algorithms for fundamental problems. This project develops a set of algorithmic tools to tackle problems on the frontier of research in algorithms.The problems explored here are of a basic nature and originate from many areas, including sampling, optimization (both discrete and continuous), machine learning and data mining. Progress on these problems, in addition to its potential practical impact, unravels deep mathematical structure and yields newanalysis tools. As the yield of algorithms grows rapidly and extends its reach far beyond computer science, such tools play an important role in forming a theory of algorithms. The research results of this project contribute to several courses (with notes available online) and the graduate courses are the basis fortextbooks to benefit the research community.The tools developed by this project are based on randomness and geometry. Three specific approaches are studied | (a) sampling high-dimensional distributions by random walks, (b) convex relaxation of discrete sets and (c) spectral projection. Fundamental problems have been solved by these techniques (yielding effcient algorithms), including volume computation, convex optimization, approximation algorithms for some NP-hard discrete optimization problems and learning mixtures of distributions. The project addressesthe scope and effciency of these techniques and tackles basic open problems in the process. These include: what functions can be sampled effciently by the random walk approach? what is the complexity of volume computation? is the asymmetric TSP harder than the the symmetric version? what are the limitsof the spectral method?

随机性和几何形状在发现基本问题的多项式时间算法中起着核心作用。该项目开发了一系列算法工具来解决算法研究边界的问题。这里探索的问题具有基本性质，源自许多领域，包括采样，优化（离散和连续），机器学习和数据挖掘。这些问题的进展，除了其潜在的实际影响外，还揭开了深层的数学结构，并产生了新分析工具。随着算法的产量迅速增长并远远超出了计算机科学的范围，这种工具在形成算法理论中起着重要作用。该项目的研究结果有助于多个课程（在线可用的注释），研究生课程是使研究社区受益的基础文本。该项目开发的工具基于随机性和几何形状。研究了三种特定方法| （a）通过随机步行来对高维分布进行采样，（b）离散集的凸松弛和（c）光谱投影。这些技术（产生效率算法）已经解决了基本问题，包括体积计算，凸优化，一些NP-硬化离散优化问题的近似算法和分布的学习混合物。这些技术的项目范围和效率在此过程中解决了基本的开放问题。这些包括：通过随机步行方法可以将哪些功能效率地采样？音量计算的复杂性是多少？不对称的TSP比对称版本更难吗？光谱法的限制是什么？