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

DOI10.1007/978-3-319-42634-1_19zbMATH Open1476.68209arXiv1605.07196OpenAlexW2403753319MaRDI QIDQ2817865FDOQ2817865

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)

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.

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

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

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)

Cites Work

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

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)