Survival Network Design of Doubling Dimension Metrics

2012/10/21 by Hao-Hsiang Hung, Hung, Hao-Hsiang
Computer Science · #Complexity and Algorithms in Graphs #Mobile Ad Hoc Networks #Optimization and Search Problems #cs.DS

paper · pdf · doi:10.48550/arxiv.1210.5729

arxiv created 2012/10/21 · arxiv updated 2012/10/23

Abstract

We investigate the Minimum Weight 2-Edge-Connected Spanning Subgraph (2-ECSS) problem in an arbitrary metric space of doubling dimension and show a polynomial time randomized (1+ε)-approximation algorithm.

Related

• A 5/4-Approximation for Two-Edge Connectivity
• Improved Distributed Approximations for Minimum-Weight\n Two-Edge-Connected Spanning Subgraph
• Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
• Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver
• A note on the Survivable Network Design Problem