Indian Statistical Institute (ISI)

Facility location problems are captivating both from theoretical and practical point of view. We study some fundamental facility location problems from the space-efficient perspective. Here the input is considered to be given in a read-only memory and only constant amount of work-space is available during the computation. This *constant-work-space 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. As a warm up, we illustrate this technique for finding the Euclidean 1-center constrained on a line for a set of points in ℝ^{2}. Using this we show how to compute the Euclidean 1-center of a set of points in ℝ^{2}. The running time of this algorithms are *O*(*n* *poly*(log *n*)). While this result gives a positive answer to an open question asked by Asano, Mulzer, Rote and Wang in 2011, the technique used can be applied to other problems which admits solutions by prune-and-search paradigm. For example, we can apply the technique to solve two and three dimensional linear programming in *O*(*n* *poly*(log *n*)) time in this model. To the best of our knowledge, these are the first sub-quadratic time algorithms for the above mentioned problems in the constant-work-space model.