2+ε approximation algorithm for the k-MST problem

Sanjeev Arora, George Karakostas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

55 Scopus citations

Abstract

For any ε>0, an nO(1/ε) time algorithm that computes a 2+ε approximation to the k-MST problem is presented. A simple modification to Garg's three-approximation algorithms was used, through an linear programming and the primal-dual framework. It is noted that Garg had exhibited a `tight' instance for the approach, thus suggesting that three is the best approximation ratio achievable using the approach.

Original languageEnglish (US)
Title of host publicationProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherSIAM
Pages754-759
Number of pages6
StatePublished - Jan 1 2000
Event11th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA
Duration: Jan 9 2000Jan 11 2000

Other

Other11th Annual ACM-SIAM Symposium on Discrete Algorithms
CitySan Francisco, CA, USA
Period1/9/001/11/00

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

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

  • Cite this

    Arora, S., & Karakostas, G. (2000). 2+ε approximation algorithm for the k-MST problem. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 754-759). SIAM.