### 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) |
---|---|

Title of host publication | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |

Publisher | SIAM |

Pages | 754-759 |

Number of pages | 6 |

State | Published - Jan 1 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
- 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.