Access Restriction

Author Tazari, Siamak ♦ Mller-Hannemann, Matthias
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2011
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Planar graphs ♦ Steiner tree ♦ Polynomial-time approximation schemes ♦ Treewidth
Abstract We present the first attempt on implementing a highly theoretical polynomial-time approximation scheme (PTAS) with huge hidden constants, namely, the PTAS for Steiner tree in planar graphs by Borradaile, Klein, and Mathieu (2009). Whereas this result, and several other PTAS results of the recent years, are of high theoretical importance, no practical applications or even implementation attempts have been known to date, due to the extremely large constants that are involved in them. We describe techniques on how to circumvent the challenges in implementing such a scheme. With today's limitations on processing power and space, we still have to sacrifice approximation guarantees for improved running times by choosing some parameters empirically. But our experiments show that with our choice of parameters, we do get the desired approximation ratios, suggesting that a much tighter analysis might be possible. Our computational experiments with benchmark instances from SteinLib and large artificial instances well exceeded our own expectations. We demonstrate that we are able to handle instances with up to a million nodes and several hundreds of terminals in 1.5 hours on a standard PC. On the rectilinear preprocessed instances from SteinLib, we observe a monotonous improvement for smaller values of ε, with an average gap below 1% for ε = 0.1. We compare our implementation against the well-known batched 1-Steiner heuristic and observe that on very large instances, we are able to produce comparable solutions much faster. We also present a thorough experimental evaluation of the influence of the various parameters of the PTAS and thus obtain a better understanding of their empirical effects.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2008-11-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 16
Page Count 33
Starting Page 3.1
Ending Page 3.33

Open content in new tab

   Open content in new tab
Source: ACM Digital Library