CAREER: Geometric Tools for Algorithms

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

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.