2+ε approximation algorithm for the k-MST problem

Sanjeev Arora; George Karakostas

2+ε approximation algorithm for the k-MST problem

Research output: Contribution to conference › Paper › peer-review

Abstract

For any ε>0, an n^O(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 language	English (US)
Pages	754-759
Number of pages	6
State	Published - 2000
Event	11th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA Duration: Jan 9 2000 → Jan 11 2000

Other

Other	11th Annual ACM-SIAM Symposium on Discrete Algorithms
City	San Francisco, CA, USA
Period	1/9/00 → 1/11/00

All Science Journal Classification (ASJC) codes

Software
General Mathematics

Cite this

@conference{93c5e0ab9ce94308b1b7a44b8bb391d0,

title = "2+ε approximation algorithm for the k-MST problem",

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.",

author = "Sanjeev Arora and George Karakostas",

year = "2000",

language = "English (US)",

pages = "754--759",

note = "11th Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 09-01-2000 Through 11-01-2000",

}

TY - CONF

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

AU - Arora, Sanjeev

AU - Karakostas, George

PY - 2000

Y1 - 2000

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0033904038&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033904038&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0033904038

SP - 754

EP - 759

T2 - 11th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 9 January 2000 through 11 January 2000

ER -

2+ε approximation algorithm for the k-MST problem

Abstract

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this