OREGON STATE UNIVERSITY

You are here

A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest

TitleA Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
Publication TypeConference Paper
Year of Publication2008
AuthorsBorradaile, G., P. N. Klein, and C. Mathieu
Conference Name2008 IEEE 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS)
Pagination115 - 124
Date Published10/2008
PublisherIEEE
Conference LocationPhiladelphia, PA
ISBN Number978-0-7695-3436-7
Keywordsapproximation algorithm, approximation scheme, Euclidean plane, Steiner forest
Abstract

We give a randomized O(n2 log n)-time approximation scheme for the Steiner forest problem in the Euclidean plane. For every fixed epsi > 0 and given any n pairs of terminals in the plane, our scheme finds a (1 + epsi)- approximation to the minimum-length forest that connects every pair of terminals.

DOI10.1109/FOCS.2008.59