E.A.Yıldırım; "Efficient Algorithms for Large-Scale...", Jan.28, 13:40
  • FENS
  • E.A.Yıldırım; "Efficient Algorithms for Large-Scale...", Jan.28, 13:40

You are here

                             

 Faculty of Engineering and Natural Sciences

 

FENS SEMINARS

 

 

 

Efficient Algorithms for Large-Scale Minimum Enclosing Ball

 

 

Emre Alper Yıldırım

 

Department of Industrial Engineering

 

Bilkent University

 

 

 

Abstract

 

We discuss simple and efficient algorithms for the approximate computation of the minimum enclosing ball of a given finite but large-scale set of points in a high-dimensional space. Our algorithms are iterative in nature and use only first-order information. The algorithms properly exploit the underlying geometric structure of the problem and have a nice geometric interpretation. We establish the existence of a small subset of points whose minimum enclosing ball provides a good approximation to that of the original input set. We also discuss ways to enhance the performances of our algorithms by identifying and eliminating interior points. We establish that our algorithms can be extended to the approximate computation of the minimum enclosing ball of much more general input sets without sacrificing most of their desirable features.

 

 

Biography

 

E. Alper Yildirim earned his B.S. degree in Industrial Engineering at Bilkent University in 1997 and his M.S. and Ph.D. degrees in Operations Research at Cornell University in 2000 and 2001, respecively. He worked as an Assistant Professor at the Department of Applied Mathematics and Statistics at Stony Brook University between 2001 and 2005. He then joined the Department of Industrial Engineering at Bilkent University, where he currently works as an Associate Professor. His research interests are mainly in mathematical programming including theory, algorithms, and applications.

 

 

Wednesday, 28 January 2009, 13:40-14:40, FENS G035