Network Optimization for Some Geometric Problems with Uncertain Data

Abstract

Optimization problems abound in geometric network applications. Many of these problems are NP-hard but have good approximation algorithms that exploit geometric structure. We consider problems in which there is uncertainty in the input data. There may be uncertainty, for example, in the input set S of vertices of a geometric graph; we may not know exactly which subset, V ⊆ S, of points from S are actually present, or we might, more generally, have a spatial probability distribution for each point p_i ∈ S. Additionally, the edges that interconnect S may be described stochastically, with edges that may or may not exist or whose lengths are uncertain, e.g., because of the presence of random obstacles. We examine various models of geometric network optimization in the face of uncertainty and present recent results on approximation algorithms for their solution.

Bio

Joseph S. B. Mitchell received a BS (Physics and Applied Mathematics), and an MS (Mathematics) from Carnegie-Mellon University, and Ph.D. (Operations Research) from Stanford University (under advisorship of Christos Papadimitriou). Mitchell was with Hughes Research Labs and then on the faculty of Cornell University. He is now SUNY Distinguished Professor at Stony Brook University in the Applied Mathematics and Statistics Department, for which he serves as Chair. He holds a joint appointment in the Department of Computer Science at Stony Brook. Mitchell has received various research awards (ACM Fellow, 2010 Gödel Prize, NSF Presidential Young Investigator, Fulbright Scholar, President's Award for Excellence in Scholarship and Creative Activities) and numerous teaching awards. His primary research area is computational geometry, applied to problems in computer graphics, visualization, air traffic management, manufacturing, and geographic information systems. Mitchell has served for several years on the Computational Geometry Steering Committee, often as Chair. He is on the editorial board of the journals Discrete and Computational Geometry, Computational Geometry: Theory and Applications, Journal of Computational Geometry, and the Journal of Graph Algorithms and Applications, and is an Editor-in-Chief of the International Journal of Computational Geometry and Applications. He has served on numerous program committees and was co-chair of the PC for the 21st ACM Symposium on Computational Geometry (2005).