CAREER: Geometric Tools for Algorithms

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

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.