A 2 + ε approximation algorithm for the k-MST problem

Sanjeev Arora, George Karakostas

Research output: Contribution to journalArticlepeer-review

25 Scopus citations

Abstract

For any ε > 0 we give a (2 + ε)-approximation algorithm for the problem of finding a minimum tree spanning any k vertices in a graph (k-MST), improving a 3-approximation algorithm by Garg [10]. As in [10] the algorithm extends to a (2 + ε)-approximation algorithm for the minimum tour that visits any k vertices, provided the edge costs satisfy the triangle inequality.

Original languageEnglish (US)
Pages (from-to)491-504
Number of pages14
JournalMathematical Programming
Volume107
Issue number3
DOIs
StatePublished - Jul 2006

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Keywords

  • Approximation algorithm
  • Primal-Dual schema
  • k-Minimum Spanning Tree

Fingerprint

Dive into the research topics of 'A 2 + ε approximation algorithm for the k-MST problem'. Together they form a unique fingerprint.

Cite this