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

Sanjeev Arora, George Karakostas

Research output: Contribution to journalArticle

20 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 1 2006

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

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

  • Cite this