AF: Small: Approximation Algorithms for Geometric Optimization

The methodologies of computational geometry will be applied to design, analyze, implement, and test algorithms for problems that arise in several application areas, including geometric network optimization, air traffic management, sensor networks, robotics, geometric modeling, and manufacturing. The main project goal is the development of fundamental advances in approximation algorithms for geometric problems. Additionally, the project will strive to foster and deepen collaborations with researchers and domain experts in application areas and industry, in order to formulate their algorithmic needs precisely and to make available algorithmic tools, insights from theoretical results, and software from experimental investigations. The specific repertoire of problems includes: (a) Geometric Network Optimization: optimal routing and network design in geometric contexts, including traveling salesman (TSP) variants, vehicle routing, constrained spanning trees, minimum-weight subdivisions, optimal route planning with various constraints, and survivable network design; (b) Air Traffic Management: optimal use of airspace in the face of dynamic and uncertain constraints induced by weather and traffic congestion, sectorization (load balancing), and optimization of flow management structures for the National Airspace System; (c) Sensor Networks and Coverage: sensor deployment, localization, data field monitoring, and coverage for stationary or mobile (robotic) sensors. The problems will be attacked on two fronts: (1) Use of formal algorithmic analysis, attempting to prove the tightest possible bounds (upper and lower) on the worst-case or average-case time/space, or approximation ratio for the problem; and (2) Development of solution techniques designed to be simple, fast, and practical, and which are compared experimentally.