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)- Approximating Steiner Networks with Node Weights
- Degree constrained node-connectivity problems
- Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements
- A 3/2-Approximation for the Metric Many-Visits Path TSP
- A partition-based relaxation for Steiner trees
- Multiple facility location on a network with linear reliability order of edges
- Matroidal degree-bounded minimum spanning trees
- Price of stability in survivable network design
- An Exact Algorithm for the Steiner Forest Problem
- Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
- Flexible Graph Connectivity
- An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
- Fractional routing using pairs of failure-disjoint paths
- The parameterized complexity of the survivable network design problem
- A 3/2-approximation algorithm for generalized Steiner trees in complete graphs with edge lengths 1 and 2
- A Spectral Approach to Network Design
- scientific article; zbMATH DE number 7053371 (Why is no real title available?)
- Design of survivable networks with low connectivity requirements
- Group parking permit problems
- A \((1.5+\varepsilon)\)-approximation algorithm for weighted connectivity augmentation
- A PTAS for three-edge-connected survivable network design in planar graphs
- Shorter tours and longer detours: uniform covers and a bit beyond
- A local-search algorithm for Steiner forest
- Approximating fault-tolerant group-Steiner problems
- On the integrality gap of the prize-collecting Steiner forest LP
- From cost sharing mechanisms to online selection problems
- On the Complexity of Local Graph Transformations
- Task assignment in tree-like hierarchical structures
- Approximating directed weighted-degree constrained networks
- Iterative packing for demand and hypergraph matching
- New primal-dual algorithms for Steiner tree problems
- Survivable network design for group connectivity in low-treewidth graphs
- On generalizations of the parking permit problem and network leasing problems
- Chain-constrained spanning trees
- LP-relaxations for tree augmentation
- Approximating (unweighted) tree augmentation via lift-and-project. II
- Degree bounded matroids and submodular flows
- Stochastic survivable network design problems: theory and practice
- A simple LP relaxation for the asymmetric traveling salesman problem
- Approximating a class of combinatorial problems with rational objective function
- On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
- A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem
- On linear and semidefinite programming relaxations for hypergraph matching
- Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph
- Approximating minimum-power edge-covers and 2,3-connectivity
- Socially fair network design via iterative rounding
- Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
- Intuitive solution-doubling techniques for worst-case analysis of some survivable network design problems
- Bounded Degree Group Steiner Tree Problems
- The k-path tree matroid and its applications to survivable network design
- A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
- Approximating Minimum Cost Connectivity Orientation and Augmentation
- On survivable network polyhedra
- On the cycle augmentation problem: hardness and approximation algorithms
- Fast distributed approximation for TAP and 2-edge-connectivity
- Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
- Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
- Cluster before you hallucinate: node-capacitated network design and energy efficient routing
- 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
- 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
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)
