Name
Abstract | ||
|---|---|---|
We consider the (GMMN). The input to this problem is a set of pairs of terminals, which are points in . The goal is to find a minimum-length rectilinear network that connects every pair in by a , that is, a path of axis-parallel line segments whose total length equals the pair’s Manhattan distance. This problem is a natural generalization of the extensively studied (MMN) in which consists of all possible pairs of terminals. Another important special case is the well-known (RSA). As a generalization of these problems, GMMN is NP-hard. No approximation algorithms are known for general GMMN. We obtain an -approximation algorithm for GMMN. Our solution is based on a stabbing technique, a novel way of attacking Manhattan network problems. Some parts of our algorithm generalize to higher dimensions, yielding a simple -approximation algorithm for the problem in arbitrary fixed dimension . As a corollary, we obtain an exponential improvement upon the previously best -ratio for MMN in dimensions (ESA 2011). En route, we show that an existing -approximation algorithm for 2D-RSA generalizes to higher dimensions. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s00453-017-0298-0 | Algorithmica |
Keywords | DocType | Volume |
Approximation algorithms,Computational geometry,Minimum Manhattan Network | Journal | 80 |
Issue | ISSN | Citations |
4 | 0178-4617 | 0 |
PageRank | References | Authors |
0.34 | 7 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aparna Das | 1 | 2 | 2.10 |
| Krzysztof Fleszar | 2 | 368 | 25.38 |
| Stephen G. Kobourov | 3 | 1440 | 122.20 |
| Joachim Spoerhase | 4 | 112 | 14.12 |
| Sankar Veeramoni | 5 | 22 | 3.91 |
| Alexander Wolff | 6 | 222 | 22.66 |