A factor 2 approximation algorithm for the generalized Steiner network problem

DOI10.1007/S004930170004zbMATH Open1107.68533OpenAlexW2172955861MaRDI QIDQ873648FDOQ873648

Authors: 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

Recommendations

A primal-dual approximation algorithm for generalized Steiner network problems
When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
Generalized steiner problem in series-parallel networks
scientific article; zbMATH DE number 1003254
An efficient approximation algorithm for the survivable network design problem

zbMATH Keywords

approximation algorithm Steiner network problem

Mathematics Subject Classification ID

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

Cited In (only showing first 100 items - show all)

Fast distributed approximation for TAP and 2-edge-connectivity
Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
An efficient PTAS for parallel machine scheduling with capacity constraints
Approximating source location and star survivable network problems
On the tree augmentation problem
ON THE VERTEX-CONNECTIVITY PROBLEM FOR GRAPHS WITH SHARPENED TRIANGLE INEQUALITY
Black-box reductions for cost-sharing mechanism design
On rooted $k$-connectivity problems in quasi-bipartite digraphs
Flexible graph connectivity
Stronger MIP formulations for the Steiner forest problem
LP-based solution methods for the asymmetric TSP
The matching augmentation problem: a $\frac{7}{4}$-approximation algorithm
Single-sink fractionally subadditive network design
On matrices with the Edmonds-Johnson property arising from bidirected graphs
Improved approximation for fractionally subadditive network design
Pruning 2-connected graphs
A $4+\epsilon$ approximation for $k$-connected subgraphs
A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs
A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs
The minimum degree group Steiner problem
Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
A note on iterated rounding for the survivable network design problem
On the $L_{\infty}$-norm of extreme points for crossing supermodular directed network LPs
A primal-dual approximation algorithm for the survivable network design problem in hypergraphs
Algorithms for hierarchical and semi-partitioned parallel scheduling
On the complexity of the bilevel minimum spanning tree problem
On some variants of Euclidean $k$-supplier
Title not available (Why is that?)
On the minimum-cost $\lambda$-edge-connected $k$-subgraph problem
Black-box reductions for cost-sharing mechanism design
Approximating the generalized terminal backup problem via half-integral multiflow relaxation
A simple LP-based approximation algorithm for the matching augmentation problem
Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow
An Exact Algorithm for the Steiner Forest Problem
Multiple facility location on a network with linear reliability order of edges
Flexible Graph Connectivity
Title not available (Why is that?)
A local-search algorithm for Steiner forest
Group parking permit problems
Shorter tours and longer detours: uniform covers and a bit beyond
On the Complexity of Local Graph Transformations
From cost sharing mechanisms to online selection problems
Chain-constrained spanning trees
LP-relaxations for tree augmentation
Approximating (unweighted) tree augmentation via lift-and-project. II
Approximating a class of combinatorial problems with rational objective function
Improved approximations for buy-at-bulk and shallow-light $k$-Steiner trees and $(k,2)$-subgraph
Approximating min-cost chain-constrained spanning-trees: a reduction from weighted to unweighted problems
Intuitive solution-doubling techniques for worst-case analysis of some survivable network design problems
Socially fair network design via iterative rounding
Bounded Degree Group Steiner Tree Problems
Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
Approximating Minimum Cost Connectivity Orientation and Augmentation
The $k$-path tree matroid and its applications to survivable network design
On the cycle augmentation problem: hardness and approximation algorithms
An iterative rounding 2-approximation algorithm for the $k$-partial vertex cover problem
New approaches to multi-objective optimization
Network-design with degree constraints
Facility Location with Matroid or Knapsack Constraints
Approximating minimum bounded degree spanning trees to within one of optimal
On the integrality ratio for tree augmentation
Covering a laminar family by leaf to leaf links
A note on Rooted Survivable Networks
Simpler analysis of LP extreme points for traveling salesman and survivable network design problems
Approximating Scheduling Machines with Capacity Constraints
Network design with edge-connectivity and degree constraints
Improved approximation algorithm for the feedback set problem in a bipartite tournament
Path hitting in acyclic graphs
Approximations for the Steiner multicycle problem
A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case
Improved approximation algorithms for directed Steiner forest
Title not available (Why is that?)
Inapproximability of survivable networks
Toward a 6/5 bound for the minimum cost 2-edge connected subgraph problem
Improved approximation algorithms for minimum cost node-connectivity augmentation problems
On some network design problems with degree constraints
On generalizations of network design problems with degree bounds
When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
Network design with weighted degree constraints
Improved approximation algorithms for maximum lifetime problems in wireless networks
A $(1 + \ln 2)$-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
Network Design with Weighted Degree Constraints
Improved approximation algorithms for min-cost connectivity augmentation problems
A unified algorithm for degree bounded survivable network design
Approximation algorithms for multi-budgeted network design problems
Tight approximation algorithm for connectivity augmentation problems
Greedy algorithms for online survivable network design
An Improved Approximation Algorithm for the Matching Augmentation Problem
Dual-based approximation algorithms for cut-based network connectivity problems
Min Sum Edge Coloring in Multigraphs Via Configuration LP
An improved approximation algorithm for minimum-cost subset $k$-connectivity (extended abstract)
Approximating node-connectivity augmentation problems
Approximability of capacitated network design
Approximating minimum cost source location problems with local vertex-connectivity demands
Group-Strategyproof Cost Sharing for Metric Fault Tolerant Facility Location
Approximating survivable networks with minimum number of Steiner points
Matching interdiction
Partial degree bounded edge packing problem for graphs and $k$-uniform hypergraphs
Approximating the smallest $k$-edge connected spanning subgraph by LP-rounding
Approximability of capacitated network design

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

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