On Minimum Generalized Manhattan Connections

Antonios Antoniadis, Margarita Capretto, Parinya Chalermsook, Christoph Damerius*, Peter Kling, Lukas Nölke, Nidia Obscura Acosta, Joachim Spoerhase

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu


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(logn) -approximation is trivial. We show that the problem is NP-hard and present an O(logn) -approximation algorithm. Moreover, we provide an O(loglogn) -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.

OtsikkoAlgorithms and Data Structures - 17th International Symposium, WADS 2021, Proceedings
ToimittajatAnna Lubiw, Mohammad Salavatipour
ISBN (painettu)9783030835071
DOI - pysyväislinkit
TilaJulkaistu - 2021
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Symposium on Algorithms and Data Structures - Virtual, Online
Kesto: 9 elok. 202111 elok. 2021
Konferenssinumero: 17


NimiLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vuosikerta12808 LNCS
ISSN (painettu)0302-9743
ISSN (elektroninen)1611-3349


ConferenceInternational Symposium on Algorithms and Data Structures
LyhennettäWADS 2021
KaupunkiVirtual, Online


Sukella tutkimusaiheisiin 'On Minimum Generalized Manhattan Connections'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä