On Minimum Generalized Manhattan Connections

10/27/2020
by   Antonios Antoniadis, et al.
0

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 ℓ_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(√(log n))-approximation algorithm. Moreover, we provide an O(loglog n)-approximation algorithm for complete bipartite 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset