Distributed Primal-Dual Approximation Algorithms for Network Design Problems
Distributed approximation algorithms aim to establish a trade off between optimality of a distributed algorithm solution for the communication complexity - number of communication rounds and messages of the algorithm. Distributed algorithms inherently deal with the way nodes should exchange information in order to solve a common problem. The goal in network design problems is to design a "Cheap" subnetwork (subgraph) that satisfies prescribed properties. Network connectivity is a fundamental property, naturally arising in distributed computing network design.