Better-than-\(\frac{4}{3}\)-approximations for leaf-to-leaf tree and connectivity augmentation
type: Item
instance of: scholarly article
title: Better-than-\(\frac{4}{3}\)-approximations for leaf-to-leaf tree and connectivity augmentation
author: Q6087008
author: Vera Traub
author: Rico Zenklusen
published in: Mathematical Programming. Series A. Series B
publication date: 2024-09-19T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 7915922
zbMATH Keywords: approximation algorithms
zbMATH Keywords: connectivity augmentation
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: tree augmentation
MaRDI profile type: Publication
cites work: Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
cites work: Parameterized Algorithms to Preserve Connectivity
cites work: Approximating (unweighted) tree augmentation via lift-and-project. II
cites work: Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
cites work: Q4938792
cites work: On the integrality ratio for tree augmentation
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: Q4607935
cites work: Rooted \(k\)-connections in digraphs
cites work: Approximation Algorithms for Several Graph Augmentation Problems
cites work: Q3128880
cites work: Improved approximation for tree augmentation: saving by rewiring
cites work: Geometric algorithms and combinatorial optimization.
cites work: A factor 2 approximation algorithm for the generalized Steiner network problem
cites work: Approximation Algorithms for Graph Augmentation
cites work: Hardness of Approximation for Vertex-Connectivity Network Design Problems
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: Covering a laminar family by leaf to leaf links
cites work: An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
cites work: On the tree augmentation problem
cites work: Approximation algorithms for connectivity augmentation problems
DOI: 10.1007/S10107-023-02018-3
description: scientific article; zbMATH DE number 7915922