Record Details
A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
ScholarsArchive at Oregon State University
| Field | Value |
|---|---|
| Title | A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest |
| Names |
Borradaile, Glencora
(creator) Klein, Philip N. (creator) Mathieu, Claire (creator) |
| Date Issued | 2015-01 (iso8601) |
| Note | © ACM, 2015. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Transactions on Algorithms (TALG), 11(3), Article 19, (January 2015) http://doi.acm.org/10.1145/2629654 |
| Abstract | We give a randomized O(n polylog n)-time approximation scheme for the Steiner forest problem in the Euclidean plane. For every fixed ε > 0 and given n terminals in the plane with connection requests between some pairs of terminals, our scheme finds a (1 + ε) approximation to the minimum-length forest that connects every requested pair of terminals. |
| Genre | Article |
| Topic | Approximation algorithms |
| Identifier | Borradaile, G., Klein, P. N., & Mathieu, C. (2015). A polynomial-time approximation scheme for Euclidean Steiner forest. ACM Transactions on Algorithms (TALG), 11(3), 19. doi:10.1145/2629654 |
