Paper Info
Title
Facility location problems in the constant work-space read-only memory model.
Abstract
Facility location problems are captivating both from theoretical and practical point of view. In this paper, 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 {\em 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 $\IR^2$. This method works even if the input is given in a sequential access read-only memory. Using this we show how to compute (i) the Euclidean 1-center of a set of points in $\IR^2$, and (ii) the weighted 1-center and weighted 2-center of a tree network. The running time of all these algorithms are $O(n~poly(\log n))$. While the result of (i) 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 admit 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 all the above mentioned problems in the constant-work-space model. We also present optimal linear time algorithms for finding the centroid and weighted median of a tree in this model.
Year
Venue
Field
2014
CoRR
Binary logarithm,Discrete mathematics,Combinatorics,Computer science,Weighted median,Algorithm,Facility location problem,Linear programming,Time complexity,Centroid,Tree network,Sequential access
DocType
Volume
Citations 
Journal
abs/1409.4092
0
PageRank 
References 
Authors
0.34
5
4
Name
Order
Citations
PageRank
Binay K. Bhattacharya133249.20
Minati De24510.11
Subhas C. Nandy328549.55
Sasanka Roy463.35