### 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 language | English (US) |
---|---|

Pages (from-to) | 491-504 |

Number of pages | 14 |

Journal | Mathematical Programming |

Volume | 107 |

Issue number | 3 |

DOIs | |

State | Published - 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

Arora, S., & Karakostas, G. (2006). A 2 + ε approximation algorithm for the k-MST problem.

*Mathematical Programming*,*107*(3), 491-504. https://doi.org/10.1007/s10107-005-0693-1