Minati De (Chennai Mathematical Institute)
18/10/13 12:30 Talks
Prune-and-search with limited work-space
Speaker:
Minati De (Chennai Mathematical Institute, India)
Abstract:
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.
Date:
Friday, October 18, 2013
Time:
12:30 pm - 1:30 pm
Location:
ASB Building, Room No. 9896, Simon Fraser University, Burnaby
Minati De (Chennai Mathematical Institute, India)
Abstract:
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.
Date:
Friday, October 18, 2013
Time:
12:30 pm - 1:30 pm
Location:
ASB Building, Room No. 9896, Simon Fraser University, Burnaby