An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph

DOI10.1016/j.ipl.2020.106067OpenAlexW3102702333MaRDI QIDQ2656340

Gregory Kehne, D. Ellis Hershkowitz, R. Ravi

Publication date: 11 March 2021

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

network designapproximation algorithmsintegrality gapminimum strongly connected spanning subgraph

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Dual-based approximation algorithms for cut-based network connectivity problems
• A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem
• A matroid approach to finding edge connectivity and packing arborescences
• A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem
• Approximating Transitive Reductions for Directed Networks
• Approximation Algorithms for Several Graph Augmentation Problems
• Randomized metarounding
• Approximating the Minimum Equivalent Digraph
• A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2
• An improved approximation algorithm for TSP in the half integral case
• 2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture
• A Randomized Rounding Approach to the Traveling Salesman Problem
• Approximating Graphic TSP by Matchings
• Optimum branchings
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph