Approximation schemes for degree-restricted MST and Red-Blue Separation Problem

Sanjeev Arora; Kevin L. Chang

Approximation schemes for degree-restricted MST and Red-Blue Separation Problem

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

Abstract

We develop a quasi-polynomial time approximation scheme for the Euclidean version of the Degree-restricted MST by adapting techniques used previously for approximating TSP. Given n points in the plane, d = 2 or 3, and ∈ > 0, the scheme finds an approximation with cost within 1 + ∈ of the lowest cost spanning tree with the property that all nodes have degree at most d. We also develop a polynomial time approximation scheme for the Euclidean version of the Red-Blue Separation Problem.

Original language	English (US)
Pages (from-to)	176-188
Number of pages	13
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2719
State	Published - Dec 1 2003

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Cite this

@article{9b25fc2ed2a847c0a1361ab896d38355,

title = "Approximation schemes for degree-restricted MST and Red-Blue Separation Problem",

abstract = "We develop a quasi-polynomial time approximation scheme for the Euclidean version of the Degree-restricted MST by adapting techniques used previously for approximating TSP. Given n points in the plane, d = 2 or 3, and ∈ > 0, the scheme finds an approximation with cost within 1 + ∈ of the lowest cost spanning tree with the property that all nodes have degree at most d. We also develop a polynomial time approximation scheme for the Euclidean version of the Red-Blue Separation Problem.",

author = "Sanjeev Arora and Chang, {Kevin L.}",

year = "2003",

month = dec,

day = "1",

language = "English (US)",

volume = "2719",

pages = "176--188",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

publisher = "Springer Verlag",

}

TY - JOUR

T1 - Approximation schemes for degree-restricted MST and Red-Blue Separation Problem

AU - Arora, Sanjeev

AU - Chang, Kevin L.

PY - 2003/12/1

Y1 - 2003/12/1

N2 - We develop a quasi-polynomial time approximation scheme for the Euclidean version of the Degree-restricted MST by adapting techniques used previously for approximating TSP. Given n points in the plane, d = 2 or 3, and ∈ > 0, the scheme finds an approximation with cost within 1 + ∈ of the lowest cost spanning tree with the property that all nodes have degree at most d. We also develop a polynomial time approximation scheme for the Euclidean version of the Red-Blue Separation Problem.

AB - We develop a quasi-polynomial time approximation scheme for the Euclidean version of the Degree-restricted MST by adapting techniques used previously for approximating TSP. Given n points in the plane, d = 2 or 3, and ∈ > 0, the scheme finds an approximation with cost within 1 + ∈ of the lowest cost spanning tree with the property that all nodes have degree at most d. We also develop a polynomial time approximation scheme for the Euclidean version of the Red-Blue Separation Problem.

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

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

M3 - Article

AN - SCOPUS:35248826365

SN - 0302-9743

VL - 2719

SP - 176

EP - 188

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -

Approximation schemes for degree-restricted MST and Red-Blue Separation Problem

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this