Article
 

A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest

Público Deposited

Conteúdo disponível para baixar

Baixar PDF
https://ir.library.oregonstate.edu/concern/articles/rj430625s

Descriptions

Attribute NameValues
Creator
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.
  • © 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
  • Keywords: Euclidean plane, Approximation algorithms, Steiner forest
  • Keywords: Euclidean plane, Approximation algorithms, Steiner forest
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
Journal Title
Journal Volume
  • 11
Journal Issue/Number
  • 3
Declaração de direitos
Funding Statement (additional comments about funding)
  • This material is based on work supported by the National Science Foundation under grant numbers CCF-0635089, CCF-0964037, and CCF-0963921.
Publisher
Peer Reviewed
Language
Replaces

Relações

Parents:

This work has no parents.

Itens

Miniatura Título Data de carga Acesso Ações
file details BorradaileGlencoraElectricalEngeeringComputerSciencePolynomialTimeApproximationScheme.pdf 2017-07-26 Público Baixar