A factor 2 approximation algorithm for the generalized Steiner network problem
From MaRDI portal
Publication:873648
DOI10.1007/s004930170004zbMath1107.68533OpenAlexW2172955861MaRDI QIDQ873648
Publication date: 29 March 2007
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s004930170004
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
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, 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, Degree constrained node-connectivity problems, On the cycle augmentation problem: hardness and approximation algorithms, Black-box reductions for cost-sharing mechanism design, An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem, Fractional routing using pairs of failure-disjoint paths, A \(4+\epsilon\) approximation for \(k\)-connected subgraphs, Approximability of Capacitated Network Design, Iterative Packing for Demand and Hypergraph Matching, Approximating Minimum Cost Source Location Problems with Local Vertex-Connectivity Demands, On matrices with the Edmonds-Johnson property arising from bidirected graphs, An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity, Fast distributed approximation for TAP and 2-edge-connectivity, The \(k\)-path tree matroid and its applications to survivable network design, A computational study on the maximum-weight bounded-degree rooted tree problem, Stochastic survivable network design problems: theory and practice, Improved approximation algorithm for the feedback set problem in a bipartite tournament, Approximating source location and star survivable network problems, Multicommodity flow in trees: packing via covering and iterated relaxation, A partition-based relaxation for Steiner trees, Improved approximation for fractionally subadditive network design, Simpler analysis of LP extreme points for traveling salesman and survivable network design problems, On survivable network polyhedra, Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems, A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs, Improved approximation algorithms for maximum lifetime problems in wireless networks, On linear and semidefinite programming relaxations for hypergraph matching, Covering a laminar family by leaf to leaf links, Approximating the smallest k -edge connected spanning subgraph by LP-rounding, Network flow spanners, A note on Rooted Survivable Networks, Dual-based approximation algorithms for cut-based network connectivity problems, On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem, Algorithms for hierarchical and semi-partitioned parallel scheduling, On the integrality ratio for tree augmentation, Approximating the Generalized Terminal Backup Problem via Half-Integral Multiflow Relaxation, Approximating MIN-cost chain-constrained spanning trees: a reduction from weighted to unweighted problems, Minimizing the stabbing number of matchings, trees, and triangulations, Approximating Survivable Networks with Minimum Number of Steiner Points, Half-integrality, LP-branching, and FPT Algorithms, Path hitting in acyclic graphs, A (1 + ln 2)-Approximation Algorithm for Minimum-Cost 2-Edge-Connectivity Augmentation of Trees with Constant Radius, Network-Design with Degree Constraints, Inapproximability of survivable networks, Approximating minimum-power edge-covers and 2,3-connectivity, Approximating Source Location and Star Survivable Network Problems, The minimum degree group Steiner problem, Approximating fault-tolerant group-Steiner problems, On the maximum size of a minimal \(k\)-edge connected augmentation, Socially fair network design via iterative rounding, Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem, A primal-dual approximation algorithm for the survivable network design problem in hypergraphs, Approximability of capacitated network design, On rooted \(k\)-connectivity problems in quasi-bipartite digraphs, Flexible graph connectivity
