AF: Small: Approximation Algorithms for Geometric Network Optimization

AF：小：几何网络优化的近似算法

• 批准号: 1526406
• 负责人: Joseph S. Mitchell
• 金额: $ 45.1万
• 依托单位: SUNY at Stony Brook
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-07-01 至 2019-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1526406&HistoricalAwards=false
• 关键词: AF; Small; Approximation; Algorithms; Geometric

Networks are the backbone of our modern world, from the internet to cellular communication networks, to transportation networks of roads and rails, to the power grid, to social networks, neural networks, computer circuitry, and more. Optimization problems (such as finding the most efficient way to place sensors or transmitters/relays to achieve coverage and connectivity, or computing a shortest route to visit a set of locations, or determining a set of routes for a fleet of robots to search a domain) arise naturally in logistics applications, including vehicle routing, robotics, advanced transportation systems, and communication. Many networks are geometric, involving infrastructure deployed in physical spaces or involving geographic coordinates and connectivity based on proximity. Even abstract networks often have special structure that essentially make them "geometric" when viewed appropriately, and this can have an impact on the efficiency of methods used to study them. This project investigates how to exploit special geometric structure of networks in order to obtain efficient algorithms for solving various optimization problems --- studying them through the lens of computational geometry and approximation algorithms. A particular challenge addressed by this project is the fact that data is often plagued with errors and sources of uncertainty that must be addressed within the model and the solutions. The discovery of "polynomial-time approximation schemes" for a wide variety of problems related to the classic "traveling salesperson problem" has shown that provable approximation algorithms with substantially better theoretical guarantees are often possible in geometric settings. The project will advance the state of the art in approximation algorithms for several variants of the vehicle routing problem in geometric domains. Examples include visibility coverage optimization for static sensors as well as mobile agents (robotic "watchmen"). Of special interest are problems involving uncertain geometric data, which may arise from a stochastic process (e.g., weather events) or from imprecise knowledge of deterministic data. While many of the solution techniques are considered to be purely theoretical, there is some hope that simplifications of earlier techniques will give rise to practical methods and that a deeper understanding of what makes some geometric problems easier to solve than their most general abstract counterparts. The problems will be attacked on two fronts, through the use of formal algorithmic analysis, with proofs of the tightest possible provable bounds (upper and lower) on worst-case or average-case performance metrics (time, space, and approximation ratio), and through the development of solution techniques designed to be simple, fast, and practical, with new methods and heuristics compared experimentally.The research has broader impact in transportation engineering, energy optimization, air traffic management, sensor networks, robotics, manufacturing processes and logistics, virtual environments, automated inspection, homeland security, and geographic information systems. Tools of optimization, network analysis, approximation algorithms, and computational geometry will be developed and applied to attack these problems. The project will advance the research frontier, while training students at all levels, and from varied disciplines, in the pursuit of research and problem solving. The project incorporates a tightly-integrated educational mission, through courses, seminars, and training of both graduate and undergraduate students.

网络是我们现代世界的支柱，从互联网到蜂窝通信网络，到公路和铁路运输网络，到电网，再到社交网络，神经网络，计算机电路等等。 优化问题（例如找到最有效的方式来放置传感器或发射器/中继器以实现覆盖和连接，或计算访问一组位置的最短路线，或确定一组机器人搜索域的路线）自然出现在物流应用中，包括车辆路由，机器人，先进的运输系统和通信。 许多网络是几何网络，涉及部署在物理空间中的基础设施，或涉及地理坐标和基于邻近性的连接。 即使是抽象的网络也往往具有特殊的结构，当适当地观察时，这些结构基本上使它们成为“几何”，这可能会影响用于研究它们的方法的效率。 本计画探讨如何利用网路的特殊几何结构，以获得解决各种最佳化问题的有效演算法--透过计算几何的透镜与近似演算法来研究。 该项目所面临的一个特殊挑战是，数据经常受到错误和不确定性来源的困扰，这些问题必须在模型和解决方案中解决。 发现的“多项式时间近似方案”的各种各样的问题有关的经典的“旅行推销员问题”表明，可证明的近似算法与更好的理论保证往往是可能的几何设置。 该项目将推进最先进的近似算法的几个变种的车辆路径问题的几何域。 示例包括静态传感器以及移动的代理（机器人“守望者”）的可见性覆盖优化。 特别感兴趣的是涉及不确定的几何数据的问题，其可能由随机过程引起（例如，天气事件）或来自确定性数据的不精确知识。 虽然许多解决技术被认为是纯粹的理论，有一些希望，简化早期的技术将产生实用的方法，并更深入地了解是什么使一些几何问题更容易解决比他们最一般的抽象的同行。 这些问题将在两个方面进行攻击，通过使用正式的算法分析，证明最严格的可能可证明的界限最差情况或平均情况性能指标（上限和下限）（时间、空间和近似比），并通过开发旨在简单、快速和实用的解决方案技术，该研究对运输工程、能源优化、空中交通管理、传感器网络、机器人、制造过程和物流、虚拟环境、自动化检测、国土安全和地理信息系统 优化，网络分析，近似算法和计算几何工具将开发和应用于攻击这些问题。 该项目将推进研究前沿，同时培养各级学生，并从不同学科，在追求研究和解决问题。 该项目通过课程、研讨会和对研究生和本科生的培训，纳入了一个紧密结合的教育使命。