Constant work-space algorithms for facility location problems

Abstract In this paper, we study some fundamental facility location problems from the space-efficient perspective. We show that 1-center problem in Euclidean space and in tree networks can be efficiently solved in constant-workspace model. We use a virtual pairing tree during the pruning stage that allows the maintenance of pruned elements. We also show that a feasible region during the prune-and-search process can always be maintained using O ( 1 ) space. These results realize the solutions to the problems in constant work-space model: linear programming in 2-d, 3-d, 2-center in trees, and largest disk inside a convex polygon.