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)- Group parking permit problems
- Approximating (unweighted) tree augmentation via lift-and-project. II
- A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs
- Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow
- On the complexity of the bilevel minimum spanning tree problem
- The minimum degree group Steiner problem
- Shorter tours and longer detours: uniform covers and a bit beyond
- An Exact Algorithm for the Steiner Forest Problem
- Flexible Graph Connectivity
- On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
- Flexible graph connectivity
- Approximating a class of combinatorial problems with rational objective function
- Intuitive solution-doubling techniques for worst-case analysis of some survivable network design problems
- Algorithms for hierarchical and semi-partitioned parallel scheduling
- Single-sink fractionally subadditive network design
- Socially fair network design via iterative rounding
- Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
- The \(k\)-path tree matroid and its applications to survivable network design
- On the \(L_{\infty}\)-norm of extreme points for crossing supermodular directed network LPs
- Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph
- On some variants of Euclidean \(k\)-supplier
- A computational study on the maximum-weight bounded-degree rooted tree problem
- Stronger MIP formulations for the Steiner forest problem
- On the Complexity of Local Graph Transformations
- Fast distributed approximation for TAP and 2-edge-connectivity
- An efficient PTAS for parallel machine scheduling with capacity constraints
- On the tree augmentation problem
- ON THE VERTEX-CONNECTIVITY PROBLEM FOR GRAPHS WITH SHARPENED TRIANGLE INEQUALITY
- Bounded Degree Group Steiner Tree Problems
- On the cycle augmentation problem: hardness and approximation algorithms
- Black-box reductions for cost-sharing mechanism design
- A note on iterated rounding for the survivable network design problem
- Multiple facility location on a network with linear reliability order of edges
- From cost sharing mechanisms to online selection problems
- A primal-dual approximation algorithm for the survivable network design problem in hypergraphs
- Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
- Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements
- A \(4+\epsilon\) approximation for \(k\)-connected subgraphs
- A local-search algorithm for Steiner forest
- On matrices with the Edmonds-Johnson property arising from bidirected graphs
- Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
- A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs
- Black-box reductions for cost-sharing mechanism design
- On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem
- The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
- The entropy rounding method in approximation algorithms
- Improved approximation for fractionally subadditive network design
- scientific article; zbMATH DE number 7205039 (Why is no real title available?)
- Chain-constrained spanning trees
- LP-relaxations for tree augmentation
- Approximating the generalized terminal backup problem via half-integral multiflow relaxation
- Pruning 2-connected graphs
- A simple LP-based approximation algorithm for the matching augmentation problem
- Approximating source location and star survivable network problems
- scientific article; zbMATH DE number 7053371 (Why is no real title available?)
- Approximating Scheduling Machines with Capacity Constraints
- Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
- Path hitting in acyclic graphs
- An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
- Improved approximation algorithm for the feedback set problem in a bipartite tournament
- Fractional routing using pairs of failure-disjoint paths
- Stochastic survivable network design problems: theory and practice
- Approximations for the Steiner multicycle problem
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- On linear and semidefinite programming relaxations for hypergraph matching
- On the maximum size of a minimal \(k\)-edge connected augmentation
- On the integrality gap of the prize-collecting Steiner forest LP
- Network design with weighted degree constraints
- Approximating node-connectivity augmentation problems
- Approximability of capacitated network design
- Improved approximation algorithms for directed Steiner forest
- Approximating minimum-power edge-covers and 2,3-connectivity
- A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case
- Approximating minimum cost source location problems with local vertex-connectivity demands
- Approximating directed weighted-degree constrained networks
- Iterative packing for demand and hypergraph matching
- Minimizing the stabbing number of matchings, trees, and triangulations
- New primal-dual algorithms for Steiner tree problems
- An iterative rounding 2-approximation algorithm for the \(k\)-partial vertex cover problem
- New approaches to multi-objective optimization
- Improved approximation algorithms for min-cost connectivity augmentation problems
- Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
- An improved approximation algorithm for minimum-cost subset \(k\)-connectivity (extended abstract)
- Approximating Directed Weighted-Degree Constrained Networks
- A simple LP relaxation for the asymmetric traveling salesman problem
- Facility Location with Matroid or Knapsack Constraints
- Approximating minimum bounded degree spanning trees to within one of optimal
- Group-Strategyproof Cost Sharing for Metric Fault Tolerant Facility Location
- scientific article; zbMATH DE number 4008433 (Why is no real title available?)
- Greedy algorithms for online survivable network design
- An Improved Approximation Algorithm for the Matching Augmentation Problem
- A unified algorithm for degree bounded survivable network design
- A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
- A partition-based relaxation for Steiner trees
- Toward a 6/5 bound for the minimum cost 2-edge connected subgraph problem
- Inapproximability of survivable networks
- On survivable network polyhedra
- Improved approximation algorithms for maximum lifetime problems in wireless networks
- Improved approximation algorithms for minimum cost node-connectivity augmentation problems
- Dual-based approximation algorithms for cut-based network connectivity problems
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)
