A faster implementation of the Goemans-Williamson clustering algorithm

MaRDI QIDQ2768267zbMATH OpenFDO

Authors Ramesh Hariharan, Ely Porat, Richard Cole, Moshe Lewenstein

Publication date 20 January 2003

zbMATH Keywords

generalized Steiner treestravelling Salesman

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• scientific article; zbMATH DE number 2089222
• Approximation algorithms for min-sum \(p\)-clustering
• Clustering to minimize the maximum intercluster distance
• On efficient implementation of an approximation algorithm for the Steiner tree problem
• A faster approximation algorithm for the Steiner problem in graphs

Cited in

(6)

• Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem
• Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
• On the hardness of optimal vertex relabeling and restricted vertex relabeling
• scientific article; zbMATH DE number 2089222 (Why is no real title available?)
• Linear-time approximation for maximum weight matching
• Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints

This page was built for publication: A faster implementation of the Goemans-Williamson clustering algorithm

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