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

Sanjeev Arora, Kevin L. Chang

Research output: Chapter in Book/Report/Conference proceedingChapter

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 languageAmerican English
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsJos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, Gerhard J. Woeginger
PublisherSpringer Verlag
Pages176-188
Number of pages13
ISBN (Print)3540404937, 9783540404934
DOIs
StatePublished - 2003

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2719

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Cite this