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

Sanjeev Arora, Kevin L. Chang

Research output: Contribution to journalArticle

3 Scopus citations

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 languageEnglish (US)
Pages (from-to)176-188
Number of pages13
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2719
StatePublished - Dec 1 2003

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Approximation schemes for degree-restricted MST and Red-Blue Separation Problem'. Together they form a unique fingerprint.

  • Cite this