Dual-based approximation algorithms for cut-based network connectivity problems

DOI10.1007/S00453-017-0356-7zbMATH Open1392.68324arXiv1508.05567OpenAlexW2963985350MaRDI QIDQ722530FDOQ722530

Authors: Benjamin Grimmer 

Publication date: 26 July 2018

Published in: Algorithmica (Search for Journal in Brave)

Abstract: We consider a variety of NP-Complete network connectivity problems. We introduce a novel dual-based approach to approximating network design problems with cut-based linear programming relaxations. This approach gives a $3/2$-approximation to Minimum 2-Edge-Connected Spanning Subgraph that is equivalent to a previously proposed algorithm. One well-studied branch of network design models ad hoc networks where each node can either operate at high or low power. If we allow unidirectional links, we can formalize this into the problem Dual Power Assignment (DPA). Our dual-based approach gives a $3/2$-approximation to DPA, improving the previous best approximation known of $11/7approx1.57$. Another standard network design problem is Minimum Strongly Connected Spanning Subgraph (MSCS). We propose a new problem generalizing MSCS and DPA called Star Strong Connectivity (SSC). Then we show that our dual-based approach achieves a 1.6-approximation ratio on SSC. As a consequence of our dual-based approximations, we prove new upper bounds on the integrality gaps of these problems.

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

Recommendations

• A cut-based algorithm for the nonlinear dual of the minimum cost network flow problem
• Dual Algorithms for Pure Network Problems
• Approximating \(k\)-cuts using network strength as a Lagrangean relaxation
• scientific article; zbMATH DE number 2119718
• Approximation algorithms for connectivity augmentation problems
• scientific article; zbMATH DE number 2075842
• Connectivity and minimum cut approximation in the broadcast congested clique
• scientific article; zbMATH DE number 1332666

zbMATH Keywords

linear programminggraph theoryapproximation algorithmsnetwork designpower assignment

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cites Work

• Title not available (Why is that?)
• A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem
• Approximating the minimum strongly connected subgraph via a matching lower bound
• Biconnectivity approximations and graph carvings
• Title not available (Why is that?)
• A factor 2 approximation algorithm for the generalized Steiner network problem
• On Steiner trees and minimum spanning trees in hypergraphs
• Network lifetime and power assignment in ad hoc wireless networks
• Approximating the Minimum Equivalent Digraph
• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
• Approximate min-power strong connectivity
• On approximate optimal dual power assignment for biconnectivity and edge-biconnectivity
• On strongly connected digraphs with bounded cycle length
• Dual power assignment optimization and fault tolerance in WSNs
• A rounding by sampling approach to the minimum size \(k\)-arc connected subgraph problem
• Title not available (Why is that?)
• Power assignment in radio networks with two power levels

Cited In (3)

• Approximating \(k\)-cuts using network strength as a Lagrangean relaxation
• An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph
• Primal-dual-based algorithms for a directed network design problem

This page was built for publication: Dual-based approximation algorithms for cut-based network connectivity problems

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