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

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

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.