Approximating \(k\)-generalized connectivity via collapsing HSTs
DOI10.1007/s10878-009-9256-3zbMath1319.05128OpenAlexW2050873015MaRDI QIDQ491201
Publication date: 24 August 2015
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-009-9256-3
approximation algorithmsgroup Steiner treegeneralized connectivitydense \(k\)-subgraphprobabilistic embedding into HSTs
Programming involving graphs or networks (90C35) Trees (05C05) Applications of graph theory (05C90) Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10) Connectivity (05C40)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved approximation algorithms for directed Steiner forest
- Optimization, approximation, and complexity classes
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- An improved rounding method and semidefinite programming relaxation for graph partition
- Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
- On-line generalized Steiner problem
- A greedy approximation algorithm for the group Steiner problem
- Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
- Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree
- On network design problems: fixed cost flows and the covering steiner problem
- A general approach to online network optimization problems
- Proof verification and the hardness of approximation problems
- Matching Based Augmentations for Approximating Connectivity Problems
- Dial a Ride from k-Forest
- Polylogarithmic inapproximability
- The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
- Maximum Gradient Embeddings and Monotone Clustering
- A Tight Analysis of the Greedy Algorithm for Set Cover
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
- A General Approximation Technique for Constrained Forest Problems
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Approximation Algorithms for Directed Steiner Problems
- Greedily Finding a Dense Subgraph
- Approximating min-sum k -clustering in metric spaces
- Tighter Bounds for Graph Steiner Tree Approximation
- Integrality Ratio for Group Steiner Trees and Directed Steiner Trees
- Approximate k-Steiner Forests Via the Lagrangian Relaxation Technique with Internal Preprocessing
- Automata, Languages and Programming
- A tight bound on approximating arbitrary metrics by tree metrics
- The dense \(k\)-subgraph problem
This page was built for publication: Approximating \(k\)-generalized connectivity via collapsing HSTs
