A Constant-Factor Approximation Algorithm for thek-MST Problem
Authors:
- Avrim BlumABAvrim Blum
- R RaviRRR Ravi
- Santosh VempalaSVSantosh Vempala
- 1 February 1999
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 58 (1) , 101-108
Abstract
No abstract availableKeywords
This publication has 8 references indexed in Scilit:
- A General Approximation Technique for Constrained Forest ProblemsSIAM Journal on Computing, 1995
- Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen1995
- A constant-factor approximation for the k-MST problem in the plane1995
- An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane1994
- The minimum latency problem1994
- Weighted k‐cardinality trees: Complexity and polyhedral structureNetworks, 1994
- The prize collecting traveling salesman problemNetworks, 1989
- The orienteering problemNaval Research Logistics (NRL), 1987