A factor 2 approximation algorithm for the generalized Steiner network problem
From MaRDI portal
Publication:873648
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
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)
- 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
- LP-based solution methods for the asymmetric TSP
- 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
- 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
- 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
- Approximating Directed Weighted-Degree Constrained Networks
- Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- On the maximum size of a minimal \(k\)-edge connected augmentation
- Approximating Steiner Networks with Node Weights
- Half-integrality, LP-branching, and FPT algorithms
- Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
- Minimizing the stabbing number of matchings, trees, and triangulations
- Matroidal degree-bounded minimum spanning trees
- Degree constrained node-connectivity problems
- A partition-based relaxation for Steiner trees
- Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
- Price of stability in survivable network design
- A Spectral Approach to Network Design
- An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
- Fractional routing using pairs of failure-disjoint paths
- On the integrality gap of the prize-collecting Steiner forest LP
- Approximating fault-tolerant group-Steiner problems
- Iterative packing for demand and hypergraph matching
- Approximating directed weighted-degree constrained networks
- New primal-dual algorithms for Steiner tree problems
- Degree bounded matroids and submodular flows
- Stochastic survivable network design problems: theory and practice
- A simple LP relaxation for the asymmetric traveling salesman problem
- On linear and semidefinite programming relaxations for hypergraph matching
- Approximating minimum-power edge-covers and 2,3-connectivity
- Approximating Minimum Cost Connectivity Orientation and Augmentation
- A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
- On survivable network polyhedra
- Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
- Approximating source location and star survivable network problems
- Multicommodity flow in trees: packing via covering and iterated relaxation
- 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
- 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 computational study on the maximum-weight bounded-degree rooted tree problem
- 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
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)
