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






Efficient Algorithms for Large-Scale Minimum Enclosing Ball



Emre Alper Yıldırım


Department of Industrial Engineering


Bilkent University






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.





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