Balls and funnels: energy efficient group-to-group anycasts

DOI10.1007/978-3-319-42634-1_19MaRDI QIDQ2817865zbMATH OpenOpenAlexFDO

Authors Jennifer Iglesias, Rajmohan Rajaraman, R. Ravi, Ravi Sundaram

Publication date 2 September 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.07196

zbMATH Keywords

approximation algorithmnetwork designwireless communication

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Communication networks in operations research (90B18) Network design and communication in computer systems (68M10)

Abstract: 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(lo{g}^{4}n)$ approximation, counterbalanced by an $lo{g}^{(2-epsilon)}n$ hardness of approximation, for general weights. Given the applicability to wireless communication, we present a scalable and easily implemented $O(logn)$ approximation algorithm, Cover-and-Grow for fixed-dimensional Euclidean space with path-loss exponent at least 2.

Recommendations

• Network design with coverage costs
• Energy-efficient wireless network design
• Tackling group-to-tree matching in large scale group communications
• scientific article; zbMATH DE number 1303564
• Survivable network design problems in wireless networks

Cites work

• scientific article; zbMATH DE number 5823062 (Why is no real title available?)
• scientific article; zbMATH DE number 1003287 (Why is no real title available?)
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• Algorithms for energy-efficient multicasting in static ad hoc wireless networks
• Balls and funnels: energy efficient group-to-group anycasts
• Integrality Ratio for Group Steiner Trees and Directed Steiner Trees
• Minimum-energy broadcasting in static ad hoc wireless networks
• Polylogarithmic inapproximability
• Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
• Set connectivity problems in undirected graphs and the directed Steiner network problem
• The design of approximation algorithms

Cited in

(1)

• Balls and funnels: energy efficient group-to-group anycasts

This page was built for publication: Balls and funnels: energy efficient group-to-group anycasts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817865)