Constant work-space algorithms for facility location problems

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 th...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2020-09, Vol.283, p.456-472
Main Authors: Bhattacharya, Binay K., De, Minati, Nandy, Subhas C., Roy, Sasanka
Format: Article
Language:English
Subjects:
1-center
Algorithms
Euclidean geometry
Euclidean space
Facility location
Linear programming
Minimum enclosing circle
Prune-and-search paradigm
Search process
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2020.01.040