Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing
From MaRDI portal
Publication:848846
DOI10.1007/s00453-008-9189-8zbMath1194.68263OpenAlexW2170451311MaRDI QIDQ848846
Publication date: 23 February 2010
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-008-9189-8
Programming involving graphs or networks (90C35) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (2)
A 2-approximation algorithm and beyond for the minimum diameter \(k\)-Steiner forest problem ⋮ Approximating \(k\)-forest with resource augmentation: a primal-dual approach
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on the prize collecting traveling salesman problem
- Partial multicuts in trees
- Real-time scheduling with a budget
- Optimization, approximation, and complexity classes
- A constant-factor approximation algorithm for the \(k\)-MST problem
- 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
- The geometry of graphs and some of its algorithmic applications
- On approximation of the submodular set cover problem
- Cut problems in graphs with a budget constraint
- A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
- Using Homogeneous Weights for Approximating the Partial Cover Problem
- Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
- Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree
- Proof verification and the hardness of approximation problems
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Dial a Ride from k-Forest
- Saving an epsilon
- Euclidean distortion and the sparsest cut
- Approximating the k-multicut problem
- The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
- New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- A Tight Analysis of the Greedy Algorithm for Set Cover
- An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
- An Efficient Polynomial Time Approximation Scheme for the Constrained Minimum Spanning Tree Problem Using Matroid Intersection
- Approximation algorithms for partial covering problems
- A General Approximation Technique for Constrained Forest Problems
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Spanning Trees—Short or Small
- Approximation Algorithms for Directed Steiner Problems
- Greedily Finding a Dense Subgraph
- A Unified Approach to Approximating Partial Covering Problems
- Automata, Languages and Programming
- The dense \(k\)-subgraph problem
This page was built for publication: Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing
