Node connectivity augmentation via iterative randomized rounding
type: Item
instance of: scholarly article
title: Node connectivity augmentation via iterative randomized rounding
arXiv ID: 2108.02041
author: Haris Angelidakis
author: Dylan Hyatt-Denesik
author: Laura Sanità
published in: Mathematical Programming. Series A. Series B
publication date: 2023-05-02T00:00:00Z
full work available at URL: https://arxiv.org/abs/2108.02041
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 7681270
zbMATH Keywords: network design
zbMATH Keywords: connectivity augmentation
zbMATH Keywords: iterative randomized rounding
zbMATH Keywords: Steiner tree
zbMATH Keywords: approximation algorithms
MaRDI profile type: Publication
Wikidata QID: Q114228485
OpenAlex ID: W3191755649
cites work: Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
cites work: Parameterized Algorithms to Preserve Connectivity
cites work: Thek-Steiner Ratio in Graphs
cites work: Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree
cites work: Steiner Tree Approximation via Iterative Randomized Rounding
cites work: Bridging the gap between tree and connectivity augmentation: unified and stronger approaches
cites work: Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
cites work: Approximating (unweighted) tree augmentation via lift-and-project. II
cites work: Q4938792
cites work: On the integrality ratio for tree augmentation
cites work: Approximating minimum-cost \(k\)-node connected subgraphs via independence-free graphs
cites work: A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
cites work: A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
cites work: The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
cites work: Q4607935
cites work: Approximation Algorithms for Several Graph Augmentation Problems
cites work: Q3128880
cites work: Improved approximation for tree augmentation: saving by rewiring
cites work: A factor 2 approximation algorithm for the generalized Steiner network problem
cites work: Approximation Algorithms for Graph Augmentation
cites work: A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
cites work: A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2
cites work: LP-relaxations for tree augmentation
cites work: An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
cites work: Q5111750
cites work: 2-node-connectivity network design
cites work: A 4 + ε approximation for k-connected subgraphs
cites work: Approximation algorithms for connectivity augmentation problems
cites work: The node-weighted steiner tree problem
cites work: Approximations for node-weighted Steiner tree in unit disk graphs
DOI: 10.1007/S10107-022-01854-Z
Recommended article: Approximating node-connectivity augmentation problems
Recommended article: Approximating connectivity augmentation problems
Recommended article: Q4472504
Recommended article: Augmenting Undirected Node-Connectivity by One
Recommended article: Augmenting undirected node-connectivity by one
Recommended article: Connectivity augmentation of graphs
Recommended article: On the optimal vertex-connectivity augmentation
Recommended article: Augmenting undirected connectivity in RNC and in randomized \(\tilde{O}(n^3)\) time
description: scientific article; zbMATH DE number 7681270