A factor 2 approximation algorithm for the generalized Steiner network problem

DOI10.1007/S004930170004zbMath1107.68533OpenAlexW2172955861MaRDI QIDQ873648

N. E. Zubov

Publication date: 29 March 2007

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s004930170004

zbMATH Keywords

approximation algorithmSteiner network problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (only showing first 100 items - show all)

An Improved Approximation Algorithm for the Matching Augmentation Problem ⋮ Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity ⋮ Bounded Degree Group Steiner Tree Problems ⋮ Flexible Graph Connectivity ⋮ Improved Approximation Algorithms for Inventory Problems ⋮ A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ Approximating Scheduling Machines with Capacity Constraints ⋮ On the Integrality Gap of the Prize-Collecting Steiner Forest LP ⋮ A Spectral Approach to Network Design ⋮ Unnamed Item ⋮ A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case ⋮ Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph ⋮ Node connectivity augmentation via iterative randomized rounding ⋮ Correlation clustering and two-edge-connected augmentation for planar graphs ⋮ On the complexity of the bilevel minimum spanning tree problem ⋮ Min Sum Edge Coloring in Multigraphs Via Configuration LP ⋮ Approximations for the Steiner multicycle problem ⋮ Approximation algorithms for flexible graph connectivity ⋮ Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree ⋮ Unnamed Item ⋮ Capacity-preserving subgraphs of directed flow networks ⋮ Unnamed Item ⋮ Approximating Minimum Cost Connectivity Orientation and Augmentation ⋮ A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem ⋮ Approximating Directed Weighted-Degree Constrained Networks ⋮ A Local-Search Algorithm for Steiner Forest ⋮ A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs ⋮ Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow ⋮ An Exact Algorithm for the Steiner Forest Problem ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems ⋮ ON THE VERTEX-CONNECTIVITY PROBLEM FOR GRAPHS WITH SHARPENED TRIANGLE INEQUALITY ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ Intuitive solution-doubling techniques for worst-case analysis of some survivable network design problems ⋮ A \((1.5+\varepsilon)\)-approximation algorithm for weighted connectivity augmentation ⋮ Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees ⋮ Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements ⋮ Network Design with Weighted Degree Constraints ⋮ Approximating \(k\)-forest with resource augmentation: a primal-dual approach ⋮ Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph ⋮ Approximating Steiner Networks with Node Weights ⋮ Group-Strategyproof Cost Sharing for Metric Fault Tolerant Facility Location ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Complexity of Local Graph Transformations ⋮ A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs ⋮ An Approximation Algorithm for Fully Planar Edge-Disjoint Paths ⋮ Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal ⋮ Facility Location with Matroid or Knapsack Constraints ⋮ Reducing Path TSP to TSP ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ From Cost Sharing Mechanisms to Online Selection Problems ⋮ Network design with edge-connectivity and degree constraints ⋮ Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ LP-based solution methods for the asymmetric TSP ⋮ Approximating a class of combinatorial problems with rational objective function ⋮ Approximation Algorithms for Multi-budgeted Network Design Problems ⋮ Toward a 6/5 bound for the minimum cost 2-edge connected subgraph problem ⋮ Partial degree bounded edge packing problem for graphs and \(k\)-uniform hypergraphs ⋮ A simple LP-based approximation algorithm for the matching augmentation problem ⋮ On some network design problems with degree constraints ⋮ New primal-dual algorithms for Steiner tree problems ⋮ Chvátal-Gomory cuts for the Steiner tree problem ⋮ On the tree augmentation problem ⋮ Matching interdiction ⋮ On the \(L_{\infty}\)-norm of extreme points for crossing supermodular directed network LPs ⋮ On generalizations of network design problems with degree bounds ⋮ A simple LP relaxation for the asymmetric traveling salesman problem ⋮ Fast Distributed Approximation for TAP and 2-Edge-Connectivity ⋮ Task assignment in tree-like hierarchical structures ⋮ A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius ⋮ On some variants of Euclidean \(k\)-supplier ⋮ On generalizations of the parking permit problem and network leasing problems ⋮ Multiple facility location on a network with linear reliability order of edges ⋮ The Generalized Terminal Backup Problem ⋮ Group parking permit problems ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ An iterative rounding 2-approximation algorithm for the \(k\)-partial vertex cover problem ⋮ New approaches to multi-objective optimization ⋮ The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm ⋮ A unified algorithm for degree bounded survivable network design ⋮ An Efficient PTAS for Parallel Machine Scheduling with Capacity Constraints ⋮ Improved approximation algorithms for directed Steiner forest ⋮ Approximating directed weighted-degree constrained networks ⋮ Pruning 2-connected graphs ⋮ Approximating node-connectivity augmentation problems ⋮ Network design with weighted degree constraints ⋮ Chain-constrained spanning trees ⋮ Approximating minimum cost source location problems with local vertex-connectivity demands ⋮ LP-relaxations for tree augmentation ⋮ Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP ⋮ Approximating (unweighted) tree augmentation via lift-and-project. II ⋮ Price of stability in survivable network design ⋮ Degree bounded matroids and submodular flows ⋮ Shorter tours and longer detours: uniform covers and a bit beyond ⋮ Tight approximation algorithm for connectivity augmentation problems ⋮ Stronger MIP formulations for the Steiner forest problem

This page was built for publication: A factor 2 approximation algorithm for the generalized Steiner network problem