Node connectivity augmentation via iterative randomized rounding

DOI10.1007/s10107-022-01854-zarXiv2108.02041OpenAlexW3191755649WikidataQ114228485 ScholiaQ114228485MaRDI QIDQ6038664

Laura Sanità, Haris Angelidakis, Dylan Hyatt-Denesik

Publication date: 2 May 2023

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

network designapproximation algorithmsSteiner treeconnectivity augmentationiterative randomized rounding

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (2)

Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree ⋮ 2-node-connectivity network design

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
• A factor 2 approximation algorithm for the generalized Steiner network problem
• On the integrality ratio for tree augmentation
• LP-relaxations for tree augmentation
• Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
• Approximating (unweighted) tree augmentation via lift-and-project. II
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• Approximations for node-weighted Steiner tree in unit disk graphs
• Approximation algorithms for connectivity augmentation problems
• 2-node-connectivity network design
• Approximating Minimum-Cost $k$-Node Connected Subgraphs via Independence-Free Graphs
• The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
• The node-weighted steiner tree problem
• Approximation Algorithms for Several Graph Augmentation Problems
• Approximation Algorithms for Graph Augmentation
• Thek-Steiner Ratio in Graphs
• Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2
• A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree
• A 4 + ε approximation for k-connected subgraphs
• Parameterized Algorithms to Preserve Connectivity
• Improved approximation for tree augmentation: saving by rewiring
• Steiner Tree Approximation via Iterative Randomized Rounding
• Bridging the gap between tree and connectivity augmentation: unified and stronger approaches

This page was built for publication: Node connectivity augmentation via iterative randomized rounding