A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest Public Deposited

http://ir.library.oregonstate.edu/concern/articles/rj430625s

© 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

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • 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.
Resource Type
DOI
Date Available
Date Issued
Citation
  • 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
Series
Keyword
Rights Statement
Funding Statement (additional comments about funding)
Publisher
Peer Reviewed
Language
Replaces
Additional Information
  • description.provenance : Made available in DSpace on 2015-07-10T23:34:10Z (GMT). No. of bitstreams: 1 BorradaileGlencoraElectricalEngeeringComputerSciencePolynomialTimeApproximationScheme.pdf: 566661 bytes, checksum: 3c819290c7dea46a16e1f47e56319242 (MD5) Previous issue date: 2015-01
  • description.provenance : Approved for entry into archive by Deanne Bruner(deanne.bruner@oregonstate.edu) on 2015-07-10T23:34:09Z (GMT) No. of bitstreams: 1 BorradaileGlencoraElectricalEngeeringComputerSciencePolynomialTimeApproximationScheme.pdf: 566661 bytes, checksum: 3c819290c7dea46a16e1f47e56319242 (MD5)
  • description.provenance : Submitted by Deanne Bruner (deanne.bruner@oregonstate.edu) on 2015-07-10T23:32:47Z No. of bitstreams: 1 BorradaileGlencoraElectricalEngeeringComputerSciencePolynomialTimeApproximationScheme.pdf: 566661 bytes, checksum: 3c819290c7dea46a16e1f47e56319242 (MD5)

Relationships

In Administrative Set:
Last modified: 07/26/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items