A factor 2 approximation algorithm for the generalized Steiner network problem
From MaRDI portal
(Redirected from Publication:873648)
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
Cited in
(only showing first 100 items - show all)- Fast distributed approximation for TAP and 2-edge-connectivity
- An iterative rounding 2-approximation algorithm for the k-partial vertex cover problem
- New approaches to multi-objective optimization
- An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
- Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
- Network-design with degree constraints
- On the integrality ratio for tree augmentation
- Covering a laminar family by leaf to leaf links
- An efficient PTAS for parallel machine scheduling with capacity constraints
- A note on Rooted Survivable Networks
- Improved approximation algorithms for inventory problems
- Simpler analysis of LP extreme points for traveling salesman and survivable network design problems
- Facility Location with Matroid or Knapsack Constraints
- Approximating minimum bounded degree spanning trees to within one of optimal
- Approximating source location and star survivable network problems
- On the tree augmentation problem
- 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
- ON THE VERTEX-CONNECTIVITY PROBLEM FOR GRAPHS WITH SHARPENED TRIANGLE INEQUALITY
- Black-box reductions for cost-sharing mechanism design
- Path hitting in acyclic graphs
- Approximating Minimum Cost Source Location Problems with Local Vertex-Connectivity Demands
- Improved approximation algorithms for directed Steiner forest
- On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
- Flexible graph connectivity
- Improved approximations for relative survivable network design
- Inapproximability of survivable networks
- Stronger MIP formulations for the Steiner forest problem
- LP-based solution methods for the asymmetric TSP
- scientific article; zbMATH DE number 4008433 (Why is no real title available?)
- A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case
- The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
- Approximations for the Steiner multicycle problem
- Toward a 6/5 bound for the minimum cost 2-edge connected subgraph problem
- Reducing Path TSP to TSP
- On some network design problems with degree constraints
- Improved approximation algorithms for minimum cost node-connectivity augmentation problems
- Chvátal-Gomory cuts for the Steiner tree problem
- On matrices with the Edmonds-Johnson property arising from bidirected graphs
- Single-sink fractionally subadditive network design
- Improved approximation for fractionally subadditive network design
- Network design with weighted degree constraints
- Node connectivity augmentation via iterative randomized rounding
- Improved approximation algorithms for maximum lifetime problems in wireless networks
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- A \((1 + \ln 2)\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
- Pruning 2-connected graphs
- Network Design with Weighted Degree Constraints
- A unified algorithm for degree bounded survivable network design
- The generalized terminal backup problem
- Tight approximation algorithm for connectivity augmentation problems
- A 4+ approximation for k-connected subgraphs
- A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs
- Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
- Approximation algorithms for multi-budgeted network design problems
- Improved approximation algorithms for min-cost connectivity augmentation problems
- Dual-based approximation algorithms for cut-based network connectivity problems
- Greedy algorithms for online survivable network design
- Min Sum Edge Coloring in Multigraphs Via Configuration LP
- An Improved Approximation Algorithm for the Matching Augmentation Problem
- A computational study on the maximum-weight bounded-degree rooted tree problem
- Correlation clustering and two-edge-connected augmentation for planar graphs
- An improved approximation algorithm for minimum-cost subset \(k\)-connectivity (extended abstract)
- The minimum degree group Steiner problem
- A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs
- Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity
- Network flow spanners
- 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
- Better-than-\(\frac{4}{3}\)-approximations for leaf-to-leaf tree and connectivity augmentation
- On the \(L_{\infty}\)-norm of extreme points for crossing supermodular directed network LPs
- Approximability of capacitated network design
- Approximating node-connectivity augmentation problems
- Approximating minimum cost source location problems with local vertex-connectivity demands
- A primal-dual approximation algorithm for the survivable network design problem in hypergraphs
- Group-Strategyproof Cost Sharing for Metric Fault Tolerant Facility Location
- Algorithms for hierarchical and semi-partitioned parallel scheduling
- Capacity-preserving subgraphs of directed flow networks
- Partial degree bounded edge packing problem for graphs and \(k\)-uniform hypergraphs
- Matching interdiction
- On the complexity of the bilevel minimum spanning tree problem
- Approximations for the Steiner multicycle problem
- On some variants of Euclidean \(k\)-supplier
- Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
- Approximability of capacitated network design
- scientific article; zbMATH DE number 7205039 (Why is no real title available?)
- On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem
- 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
- A simple LP-based approximation algorithm for the matching augmentation problem
- Approximating the generalized terminal backup problem via half-integral multiflow relaxation
- Black-box reductions for cost-sharing mechanism design
- The entropy rounding method in approximation algorithms
- Approximating \(k\)-forest with resource augmentation: a primal-dual approach
- Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow
- Half-integrality, LP-branching, and FPT algorithms
- Minimizing the stabbing number of matchings, trees, and triangulations
- Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
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)
