Approximating minimum cost connectivity orientation and augmentation

DOI10.1137/1.9781611973402.122MaRDI QIDQ5384084zbMATH OpenOpenAlexFDO

Authors Mohit Singh, László A. Végh

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Abstract: We investigate problems addressing combined connectivity augmentation and orientations settings. We give a polynomial-time 6-approximation algorithm for finding a minimum cost subgraph of an undirected graph $G$ that admits an orientation covering a nonnegative crossing $G$-supermodular demand function, as defined by Frank. An important example is $(k,ell)$-edge-connectivity, a common generalization of global and rooted edge-connectivity. Our algorithm is based on a non-standard application of the iterative rounding method. We observe that the standard linear program with cut constraints is not amenable and use an alternative linear program with partition and co-partition constraints instead. The proof requires a new type of uncrossing technique on partitions and co-partitions. We also consider the problem setting when the cost of an edge can be different for the two possible orientations. The problem becomes substantially more difficult already for the simpler requirement of $k$-edge-connectivity. Khanna, Naor, and Shepherd showed that the integrality gap of the natural linear program is at most $4$ when $k=1$ and conjectured that it is constant for all fixed $k$. We disprove this conjecture by showing an $Omega(|V|)$ integrality gap even when $k=2$.

Recommendations

• Approximating Minimum Cost Connectivity Orientation and Augmentation
• An algorithm for minimum cost arc-connectivity orientations
• Directed Network Design with Orientation Constraints
• scientific article; zbMATH DE number 1757953
• Combined connectivity augmentation and orientation problems

Cited in

(7)

• Combined connectivity augmentation and orientation problems
• scientific article; zbMATH DE number 1757953 (Why is no real title available?)
• Approximating Minimum Cost Connectivity Orientation and Augmentation
• scientific article; zbMATH DE number 1445363 (Why is no real title available?)
• Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation
• Directed Network Design with Orientation Constraints
• An algorithm for minimum cost arc-connectivity orientations

This page was built for publication: Approximating minimum cost connectivity orientation and augmentation

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