DEPARTMENT RESEARCH ACADEMICS PEOPLE NEWS
Rice Computer Science		SEARCH:
Rice University Department of Computer Science presents Chee Yap Courant Institute, New York University Seminar: Pseudo Approximation Algorithms, with Applications to Optimal Motion Planning Abstract The design of approximation algorithms is an important theme in the study of optimization problems. It takes on an additional significance when applied to NP-hard problems. We describe a highly efficient scheme for converting a pseudo epsilon-approximation algorithm into a true epsilon-approximation algorithm. The advantage for this approach derives from (i) the relative ease of constructing pseudo approximation algorithms as compared to approximation algorithms, (ii) the use of the above generic conversion scheme, and (iii) a clearer understanding of those aspects of the approximation process that are sensitive to the precision of the input. We illustrate our technique on two problems: (A) Euclidean Shortest Path (3ESP), namely the shortest path for a point robot amidst polyhedral obstacles in 3-D, and (B) d1-optimal motion for a rod moving amidst polygonal obstacles in 2-D. These problems are the simplest NP-hard motion planning problems in 3-D and 2-D, respectively. Previously, no epsilon-approximation algorithm for (B) was known. For (A), our new solution is simpler than two previous solutions and also has an exponentially lower complexity in terms of the input precision parameter. Joint work with Tetsuo Asano and David Kirkpatrick. Thursday, March 28 at 4pm in DH 3076 A 3:30 reception in DH 3076 will precede the talk. About Chee Yap Chee Yap is Professor of Computer Science at the Courant Institute of Mathematical Sciences, New York University. He has published over 120 papers in major conferences and journals, in the area of algorithms and complexity. His research interests include computational geometry, visualization problems, computer algebra and algorithmic robotics. Since 1993, he has been interested in numerical non-robustness, especially issues at the interface between numerical, algebraic and topological computation. A current project called the Core Library (http://cs.nyu.edu/exact/core/) aims to bring robust computation out of research realm and make it widely accessible to all programmers. Yap was born in Singapore and educated at MIT (S.B. 1975) and Yale (PhD 1980). He served on the editorial boards of SIAM J. of Computing (1985-2002), J. of Computer and System Sciences (1986--), J. of Symbolic Computation (1988--), Computational Geometry: Theory and Applications (1990--), Int'l J. of Comp. Geometry and Applications (1990--), and Algorithmica (1992--). His books include the edited volume "Advances in Robotics: Algorithmic and Geometric Issues", (co-edited with Jack Schwartz), Lawrence Erlbaum Associates, Inc, 1987, and "Fundamental Problems in Algorithmic Algebra", Oxford University Press, 2000. Copyright 2000 Rice University site problems: www@cs.rice.edu --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---