AF: Small: Approximation Algorithms for Geometric Network Optimization

Suny At Stony Brook, Stony Brook NY

Investigators

Abstract

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.