The Taub Faculty of Computer Science Events and Talks

The problem of finding the placement of certain number of facilities so that they can serve all the demands efficiently is a very important subject of research. In this talk, we present some fundamental facility location problems in memory-constrained environment. Here the input is considered to be given in a read-only memory and only constant amount of work-space is available for the computation. This model is well-motivated for handling big-data as well as for computing in smart portable devices with small amount of extra-space.

First, we propose a strategy to implement prune-and-search in this model. It will work even if the input is given in a sequential access read-only memory. Using this we show how to compute (i) the center of the minimum enclosing circle for a set of points in , and (ii) the weighted 1-center and weighted 2-center of a tree network. The running time of all these algorithms are . We also present optimal linear time algorithm for finding centroid and weighted median of a tree in this model. Our results improve product for all the stated problems.