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 ℝ². Using this we show how to compute the Euclidean 1-center of a set of points in ℝ². 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.