Minati De (Chennai Mathematical Institute)

Prune-and-search with limited work-space
Minati De (Chennai Mathematical Institute, India)


Prune-and-search is an excellent algorithmic paradigm for solving various optimization problems. In this talk, we discuss a general scheme for  prune-and-search technique and show how to implement it in space-efficient manner. We consider both the in-place and read-only model which have several advantages compared to traditional model of computation. Our technique can be applied to a large number of problems which accept prune-and-search. For explaining the technique, we consider the following problem  which has tremendous practical usage apart from theoretical implication:  computing the minimum enclosing circle (MEC) of a set of n points in 2D.  The time and extra-space complexities of the proposed algorithm is $O(n~polylog(n))$ and $O(polylog(n))$ respectively.

This talk is based on a joint work with S. Chandra Nandy and Sasanka Roy.


Friday, October 18, 2013


12:30 pm - 1:30 pm

ASB Building, Room No. 9896, Simon Fraser University, Burnaby