AF: Small: Algorithms for Fundamental Optimization Problems in Computational Geometry

几何无处不在。普通人会在各种应用中不知不觉地生成几何数据，例如在使用位置服务甚至进行金融交易时。快速处理这样的几何数据对于提供快速响应是不可或缺的。例如，导航系统需要有效的算法来提供最佳路线。同样，出租车公司需要一种快速算法来匹配汽车和客户，以最大限度地减少等待时间和行驶距离。 尽管几十年的努力，然而，现有的算法，许多这样的几何优化问题是缓慢的或产生低质量的解决方案。在这个项目中，PI将引入新的技术，并提供一个路线图，以设计有效的算法，选择基本的几何问题。鉴于其广泛的适用性，PI和他的学生不仅将为这些问题设计算法，而且还将实现，测试，优化和公开代码以造福研究人员。本计画将研究计算几何中的一些基本最佳化问题。这些包括计算的几何运输问题，几何瓶颈匹配，容量限制的服务器分配，最小重量三角和最小重量斯坦纳三角问题。国家的最先进的几何优化技术有严重的局限性，这些问题。该项目将探索三种新技术，以解决这些基本问题。 首先，PI将介绍一种新的图形划分技术，以协助设计快速算法的匹配和运输问题的几何和度量设置。其次，PI将匈牙利算法推广到其他服务器分配问题，并提出在几何和度量设置中设计快速精确，近似和在线算法。第三，PI将探索一种概率方法来设计多项式时间近似方案，用于著名的最小重量三角剖分和Steiner三角剖分问题。该项目还将引入和整合来自各个领域的几种新技术，包括计算几何和优化，这将有助于弥合这些问题的上限和下限之间的差距。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

Geometry is everywhere. An average person will unknowingly generate geometric data in various applications, for instance while using location services or even conducting a financial transaction. Processing such geometric data quickly is integral to providing a fast response. For example, a navigation system requires an efficient algorithm to provide an optimal route. Similarly, taxi companies require a fast algorithm to match cars to customers in order to minimize wait time and travel distance. Despite decades of effort, however, existing algorithms for many such geometric optimization problems are either slow or produce low-quality solutions. In this project, the PI will introduce new techniques and provide a roadmap to design efficient algorithms for select fundamental geometric problems. Given their wide applicability, the PI and his students will not only design algorithms for these problems but also implement, test, optimize and make the code public for the benefit of researchers. This project will study a number of fundamental optimization problems in computational geometry. These include computation of the Geometric Transportation problem, Geometric Bottleneck Matching, Capacitated Server Allocation, Minimum Weight Triangulation and the Minimum Weight Steiner Triangulation problems. State-of-the-art geometric optimization techniques have severe limitations with respect to these problems. This project will explore three new techniques to make progress on solving these fundamental problems. First, the PI will introduce a new graph-partitioning technique to assist in the design of fast algorithms for matching and transportation problems in geometric and metric settings. Second, the PI will generalize the Hungarian Algorithm to other server-allocation problems and propose to design fast exact, approximation and online algorithms in geometric and metric settings. Third, the PI will explore a probabilistic approach to design polynomial-time approximation schemes for the well-known minimum-weight triangulation and Steiner triangulation problems. This project will also introduce and integrate several novel techniques from various areas including computational geometry and optimization that will assist in bridging the gap between the upper and lower bounds for these problems.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.