On small-depth tree augmentations

DOI10.1016/J.ORL.2022.10.002OpenAlexW3208440388MaRDI QIDQ2102832FDOQ2102832

Authors: Ojas Parekh, R. Ravi, Michael Zlatin 

Publication date: 12 December 2022

Published in: Operations Research Letters (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmintegrality gapnetwork design

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Cites Work

• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
• A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2
• A bidirected generalization of network matrices
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• On the integrality ratio for tree augmentation
• A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
• Title not available (Why is that?)
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• Approximation Algorithms for Graph Augmentation
• Approximation Algorithms for Several Graph Augmentation Problems
• Improved approximation for tree augmentation: saving by rewiring
• Optimization with binet matrices
• Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
• Title not available (Why is that?)
• Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
• Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem

Cited In (1)

• LP-relaxations for tree augmentation

This page was built for publication: On small-depth tree augmentations

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