Distributed Distance-Bounded Network Design Through Distributed Convex Programming

DOI10.4230/LIPIcs.OPODIS.2017.5zbMath1487.68251arXiv1703.07417OpenAlexW2776111721MaRDI QIDQ3300803

Yasamin Nazari, Michael Dinitz

Publication date: 30 July 2020

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

zbMATH Keywords

convex programmingapproximation algorithmsdistributed algorithms

Mathematics Subject Classification ID

Convex programming (90C25) Network design and communication in computer systems (68M10) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (1)

Distributed Spanner Approximation

Cites Work

• Unnamed Item
• Local approximability of max-min and min-max linear programs
• Geometric algorithms and combinatorial optimization
• Low diameter graph decompositions
• Design networks with bounded pairwise distance
• Fault-tolerant spanners
• Improved Approximation for the Directed Spanner Problem
• Oblivious network design
• The price of being near-sighted
• Graph spanners
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Distributed Computing: A Locality-Sensitive Approach
• Label Cover Instances with Large Girth and the Hardness of Approximating Basic k -Spanner
• Linear programming without the matrix
• Distributed Strong Diameter Network Decomposition
• Directed spanners via flow-based linear programs
• Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph

This page was built for publication: Distributed Distance-Bounded Network Design Through Distributed Convex Programming