Approximation schemes for degree-restricted MST and red-blue separation problems

Sanjeev Arora, Kevin Chang

Research output: Contribution to journalArticle

22 Scopus citations

Abstract

We develop a quasi-polynomial time approximation scheme for the Euclidean version of the Degree-Restricted MST Problem by adapting techniques used previously by Arora for approximating TSP. Given n points in the plane, d = 3 or 4, 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, again extending Arora's techniques. Given ε > 0, the scheme finds an approximation with cost within 1+ ε of the cost of the optimum separating polygon of the input nodes, in nearly linear time.

Original languageEnglish (US)
Pages (from-to)189-210
Number of pages22
JournalAlgorithmica (New York)
Volume40
Issue number3
DOIs
StatePublished - Aug 1 2004

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Approximation schemes for degree-restricted MST and red-blue separation problems'. Together they form a unique fingerprint.

  • Cite this