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

AF：小：计算几何中基本优化问题的算法

基本信息

批准号：
1909171
负责人：
Sharath Raghvendra
金额：
$ 45万
依托单位：
Virginia Polytechnic Institute and State University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-07-15 至 2023-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1909171&HistoricalAwards=false
关键词：
AF Small Algorithms Fundamental Optimization

项目摘要

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.

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