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

几何学无处不在。普通人会在不知情的情况下在各种应用中生成几何数据，例如在使用位置服务或甚至进行金融交易时。快速处理这样的几何数据对于提供快速响应是不可或缺的。例如，导航系统需要一个有效的算法来提供最优路线。同样，出租车公司需要一种快速算法来匹配车辆和客户，以最大限度地减少等待时间和旅行距离。然而，尽管经过了几十年的努力，许多此类几何优化问题的现有算法要么速度很慢，要么产生的解质量较低。在这个项目中，PI将引入新的技术，并提供一个路线图来设计选择基本几何问题的有效算法。鉴于其广泛的适用性，Pi和他的学生不仅将为这些问题设计算法，而且还将实现、测试、优化和公开代码，以造福于研究人员。这个项目将研究计算几何中的一些基本优化问题。这些问题包括几何运输问题、几何瓶颈匹配、容量限制的服务器分配、最小权重三角剖分和最小权重Steiner三角剖分问题的计算。最新的几何优化技术在这些问题上有严重的局限性。该项目将探索三种新技术，以在解决这些基本问题上取得进展。首先，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.