CAREER: Geometric Tools for Algorithms

职业：算法的几何工具

• 批准号: 9875024
• 负责人: Santosh Vempala
• 金额: $ 24万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-07-01 至 2004-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9875024&HistoricalAwards=false
• 关键词: CAREER; Geometric; Tools; Algorithms

CCR-9875024VempalaThe goal of this research is to develop several tools for the design of efficient algorithms and apply them to fundamental algorithmic problems in computer science, as well as to modelling and solving some of the new challenges in the field. The design of approximation algorithms lends itself to a particularly geometric interpretation. There are two steps involved: (1) Find a Relaxation, i.e., a set that encloses the set of solutions to the original problem and is easier to solve, (2) Find a Rounding, i.e., a mapping from a solution of the relaxation to a true solution. The first idea this project sets out to explore is that of a Convex relaxation. The set of solutions to the original problem can be viewed as a convex set (viz. Their convex hull) and any convex set enclosing this is a relaxation. The quality of a relaxation is dependent on how well it estimates the true optimum of the problem. Building on the past success of this approach, the project pursues promising relaxations for two fundamental problems, finding the Minimum Sparsity Cut (or Conductance) of a graph, and the Minimum Traveling Salesman problem in a directed graph.The second idea is based on a technique of Lovasz and Schrijver, Called "lift-and-project," to progressively refine any given convex relaxation. Although the technique has so far been used only to solve special cases of NP-hard problems in polynomial time, it appears to be well-suited for approximation algorithms, and one objective of this research is to adapt it for this purpose. A natural candidate for this approach is the problem of finding the Maximum Acyclic Subgraph of a directed graph.The next two ideas are techniques for rounding. Random Projection has recently enjoyed much success as an algorithmic tool, for problems ranging from VLSI layout to finding nearest neighbors. Here it is developed by refining its application to the problem of learning the intersection of half-spaces (convex bodies).It is often the case that a relatively small subset of the solutions to a relaxation, upon rounding, leads to the worst case performance of the algorithm, whereas on average, near-optimum solutions to the relaxation exhibit much better performance. To exploit this, the idea is to find a Random Near-Optimum of the relaxation, and then round this to a true solution. The problem of finding a random near-optimum can be solved efficiently via a random walk. Two candidate problems where this strategy might improve the quality of approximation are the Maximum Cut problem and the Minimum Bandwidth problem.The last tool is a fast algorithm for approximating a given matrix with another matrix of small rank. Standard methods to compute such low-rank approximations take time that is polynomial in the size of the matrix. In the context of problems such as information retrieval on the internet, this can be prohibitively expensive. I contrast, the running time of the new algorithm depends only on the quality of the desired approximation and not on the size of the matrix. This algorithm will be applied as a tool to speed up existing (polynomial-time) algorithms for several applications, including linear equations, searching for nearest neighbours, and text and image retrieval.These ideas are being integrated into education in the form of two courses, one at the senior undergraduate level, and the other at the graduate level. The former would be based on the basic concepts and successful ideas that come out of this research, while the latter would be exploratory and present promising directions and relatively difficult results.

CCR-9875024Vempala这项研究的目标是开发几种工具来设计有效的算法，并将它们应用于计算机科学中的基本算法问题，以及建模和解决该领域的一些新挑战。近似算法的设计适合于一种特殊的几何解释。其中涉及两个步骤：(1)求松弛，即包含原问题的解的集合，且更容易求解；(2)求舍入，即从松弛的解到真解的映射。这个项目开始探索的第一个想法是凸起松弛。原始问题的解的集合可以被视为一个凸集(即。它们的凸包)和任何包含它的凸集都是松弛的。松弛的质量取决于它对问题的真正最优的估计有多好。在这种方法过去成功的基础上，该项目在两个基本问题上追求有希望的松弛，即寻找图的最小稀疏度割(或电导)和有向图中的最小旅行商问题。第二个想法基于Lovasz和Schrijver的技术，称为“提升和投影”，以逐步细化任何给定的凸松弛。虽然到目前为止，这种技术只被用来解决多项式时间内的NP-Hard问题的特殊情况，但它似乎非常适合于近似算法，本研究的一个目的是使其适用于此目的。这种方法的一个自然候选者是寻找有向图的最大无圈子图的问题。接下来的两个想法是舍入技术。随机投影最近作为一种算法工具获得了很大的成功，用于解决从VLSI布局到寻找最近邻居的各种问题。本文通过改进它在学习半空间(凸体)相交问题中的应用来发展它。通常情况下，松弛的解的相对较小的子集在舍入时会导致算法的最差情况下的性能，而平均而言，松弛的近最优解表现出更好的性能。为了利用这一点，我们的想法是找到松弛的随机近最优，然后将其舍入为真正的解决方案。通过随机游走可以有效地解决寻找随机近最优解的问题。这一策略可能提高逼近质量的两个候选问题是最大割问题和最小带宽问题。最后一个工具是一个用另一个小秩矩阵逼近给定矩阵的快速算法。计算这种低阶近似的标准方法所花费的时间是矩阵大小的多项式。在互联网上检索信息等问题的背景下，这可能是令人望而却步的昂贵。相比之下，新算法的运行时间仅取决于所需近似的质量，而不取决于矩阵的大小。这个算法将作为一种工具来加速现有的(多项式时间)算法，用于几个应用，包括线性方程，搜索最近的邻居，以及文本和图像检索。这些想法正在以两门课程的形式整合到教育中，一门在大学四年级，另一门在研究生水平。前者将基于这项研究的基本概念和成功的想法，而后者将是探索性的，并提出有希望的方向和相对困难的结果。