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

Sanjeev Arora; George Karakostas

doi:10.1007/s10107-005-0693-1

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

Sanjeev Arora, George Karakostas

Research output: Contribution to journal › Article › peer-review

29 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 language	English (US)
Pages (from-to)	491-504
Number of pages	14
Journal	Mathematical Programming
Volume	107
Issue number	3
DOIs	https://doi.org/10.1007/s10107-005-0693-1
State	Published - Jul 2006

All Science Journal Classification (ASJC) codes

Software
General Mathematics

Keywords

Approximation algorithm
Primal-Dual schema
k-Minimum Spanning Tree

Access to Document

10.1007/s10107-005-0693-1

Cite this

@article{f0105408f9e34724a282e856be1a9435,

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

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

keywords = "Approximation algorithm, Primal-Dual schema, k-Minimum Spanning Tree",

author = "Sanjeev Arora and George Karakostas",

year = "2006",

month = jul,

doi = "10.1007/s10107-005-0693-1",

language = "English (US)",

volume = "107",

pages = "491--504",

journal = "Mathematical Programming",

issn = "0025-5610",

publisher = "Springer-Verlag GmbH and Co. KG",

number = "3",

}

TY - JOUR

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

AU - Arora, Sanjeev

AU - Karakostas, George

PY - 2006/7

Y1 - 2006/7

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

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

KW - Approximation algorithm

KW - Primal-Dual schema

KW - k-Minimum Spanning Tree

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

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

U2 - 10.1007/s10107-005-0693-1

DO - 10.1007/s10107-005-0693-1

M3 - Article

AN - SCOPUS:33645320814

SN - 0025-5610

VL - 107

SP - 491

EP - 504

JO - Mathematical Programming

JF - Mathematical Programming

IS - 3

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this