scientific article; zbMATH DE number 1757947

MaRDI QIDQ4537735zbMATH OpenFDO

Authors Tim Roughgarden, David P. Williamson, F. Chudak

Publication date 20 June 2002

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2081/20810060

Mathematics Subject Classification ID

Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Recommendations

• Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
• A constant-factor approximation algorithm for the \(k\)-MST problem
• A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
• scientific article; zbMATH DE number 1256763
• A 2.5-factor approximation algorithm for the k-MST problem

Cited in

(10)

• Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
• Clustering to minimize the sum of cluster diameters
• An approximation algorithm for the k-prize-collecting multicut on a tree problem
• Euclidean prize-collecting Steiner forest
• An approximation algorithm for \(P\)-prize-collecting set cover problem
• A 2.5-factor approximation algorithm for the k-MST problem
• Approximate k-Steiner Forests Via the Lagrangian Relaxation Technique with Internal Preprocessing
• Approximating \(k\)-forest with resource augmentation: a primal-dual approach
• Approximating fault-tolerant group-Steiner problems
• Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4537735)