On a partition LP relaxation for min-cost 2-node connected spanning subgraphs

DOI10.1016/j.orl.2023.03.008zbMath1525.90416arXiv2111.07481OpenAlexW3211932688MaRDI QIDQ6106538

Bundit Laekhanukit, Joseph Cheriyan, Logan Grout

Publication date: 3 July 2023

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

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

zbMATH Keywords

greedy algorithmnetwork designapproximation algorithmsconnectivity augmentation2-node connected graphspartition relaxation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Linear programming (90C05) Connectivity (05C40)

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 partition-based relaxation for Steiner trees
• Minimum-weight two-connected spanning networks
• On the integrality ratio for tree augmentation
• On the spanning tree polyhedron
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• Approximating node connectivity problems via set covers
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• 2-node-connectivity network design
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• The Design of Approximation Algorithms
• Approximation Algorithms for Several Graph Augmentation Problems
• An Analysis of the Greedy Heuristic for Independence Systems
• Improved Approximation Algorithms for Uniform Connectivity Problems