AF: Small: Approximation Algorithms for Geometric Optimization

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

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

The methodologies of computational geometry will be applied to design,analyze, implement, and test algorithms for problems that arise inseveral application areas, including geometric network optimization,air traffic management, sensor networks, robotics, geometric modeling,and manufacturing. The main project goal is the development offundamental advances in approximation algorithms for geometricproblems. Additionally, the project will strive to foster and deepencollaborations with researchers and domain experts in applicationareas and industry, in order to formulate their algorithmic needsprecisely and to make available algorithmic tools, insights fromtheoretical results, and software from experimental investigations.The specific repertoire of problems includes: (a) Geometric NetworkOptimization: optimal routing and network design in geometriccontexts, including traveling salesman (TSP) variants, vehiclerouting, constrained spanning trees, minimum-weight subdivisions,optimal route planning with various constraints, and survivablenetwork design; (b) Air Traffic Management: optimal use of airspacein the face of dynamic and uncertain constraints induced by weatherand traffic congestion, sectorization (load balancing), andoptimization of flow management structures for the National AirspaceSystem; (c) Sensor Networks and Coverage: sensor deployment,localization, data field monitoring, and coverage for stationary ormobile (robotic) sensors.The problems will be attacked on two fronts: (1) Use of formalalgorithmic analysis, attempting to prove the tightest possible bounds(upper and lower) on the worst-case or average-case time/space, orapproximation ratio for the problem; and (2) Development of solutiontechniques designed to be simple, fast, and practical, and which arecompared experimentally.

计算几何的方法将被应用于设计，分析，实施和测试算法的问题出现在几个应用领域，包括几何网络优化，空中交通管理，传感器网络，机器人，几何建模和制造。 主要的项目目标是在几何问题的近似算法方面取得基础性的进展。 此外，该项目将努力促进和深化与应用领域和行业的研究人员和领域专家的合作，以便精确地制定他们的算法需求，并提供算法工具，理论结果的见解和实验研究的软件。具体的问题包括：（a）几何网络优化：几何环境中的最佳路由和网络设计，包括旅行商（TSP）变量、车辆路由、约束生成树、最小权重细分、具有各种约束的最佳路由规划和可生存网络设计;（B）空中交通管理：最佳利用空域在面对由天气和交通拥挤、扇区化引起的动态和不确定的限制时（c）传感器网络和覆盖：传感器部署、定位、数据场监测和固定或移动（机器人）传感器的覆盖。（1）使用形式算法分析，试图证明最坏情况或平均情况下的时间/空间或问题的近似比的最严格的可能界限（上限和下限）;（2）开发解决方案技术，旨在简单，快速和实用，并通过实验进行比较。