Name
Abstract | ||
|---|---|---|
We consider minimum-cardinality Manhattan connected sets with arbitrary demands: Given a collection of points P in the plane, together with a subset of pairs of points in P (which we call demands), find a minimum-cardinality superset of P such that every demand pair is connected by a path whose length is the l(1)-distance of the pair. This problem is a variant of three well-studied problems that have arisen in computational geometry, data structures, and network design: (i) It is a node-cost variant of the classical Manhattan network problem, (ii) it is an extension of the binary search tree problem to arbitrary demands, and (iii) it is a special case of the directed Steiner forest problem. Since the problem inherits basic structural properties from the context of binary search trees, an O(log n)-approximation is trivial. We show that the problem is NP-hard and present an O(root log n)-approximation algorithm. Moreover, we provide an O(log log n)-approximation algorithm for complete k-partite demands as well as improved results for unit-disk demands and several generalizations. Our results crucially rely on a new lower bound on the optimal cost that could potentially be useful in the context of BSTs. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/978-3-030-83508-8_7 | ALGORITHMS AND DATA STRUCTURES, WADS 2021 |
Keywords | DocType | Volume |
Manhattan networks, Binary search tree, NP-hardness | Conference | 12808 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
0 | 8 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Antonios Antoniadis | 1 | 127 | 13.81 |
| Margarita Capretto | 2 | 0 | 0.34 |
| Parinya Chalermsook | 3 | 187 | 20.94 |
| Christoph Damerius | 4 | 0 | 1.01 |
| Peter Kling | 5 | 0 | 0.34 |
| Lukas Nölke | 6 | 0 | 1.01 |
| Nidia Obscura | 7 | 0 | 0.34 |
| Joachim Spoerhase | 8 | 0 | 0.34 |