Name
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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.dam.2020.01.040 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
Facility location,Minimum enclosing circle,1-center,Prune-and-search paradigm | Journal | 283 |
ISSN | Citations | PageRank |
0166-218X | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Binay K. Bhattacharya | 1 | 332 | 49.20 |
| Minati De | 2 | 45 | 10.11 |
| Subhas C. Nandy | 3 | 285 | 49.55 |
| Sasanka Roy | 4 | 31 | 13.37 |