2016/05/23 by Iglesias, Jennifer, Rajaraman, Rajmohan, Ravi, R. +1
#FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI)
paper · doi:10.48550/arxiv.1605.07196
We introduce group-to-group anycast (g2g-anycast), a network design problem of substantial practical importance and considerable generality. Given a collection of groups and requirements for directed connectivity from source groups to destination groups, the solution network must contain, for each requirement, an omni-directional down-link broadcast, centered at any node of the source group, called the ball; the ball must contain some node from the destination group in the requirement and all such destination nodes in the ball must aggregate into a tree directed towards the source, called the funnel-tree. The solution network is a collection of balls along with the funnel-trees they contain. g2g-anycast models DBS (Digital Broadcast Satellite), Cable TV systems and drone swarms. It generalizes several well known network design problems including minimum energy unicast, multicast, broadcast, Steiner-tree, Steiner-forest and Group-Steiner tree. Our main achievement is an O(log4 n) approximation, counterbalanced by an log(2-ε)n hardness of approximation, for general weights. Given the applicability to wireless communication, we present a scalable and easily implemented O(log n) approximation algorithm, Cover-and-Grow for fixed-dimensional Euclidean space with path-loss exponent at least 2.