Shallow-Light Steiner Arborescences with Vertex Delays
Autor: | Stephan Held, Daniel Rotter |
---|---|
Rok vydání: | 2013 |
Předmět: | |
Zdroj: | Integer Programming and Combinatorial Optimization ISBN: 9783642366932 IPCO |
DOI: | 10.1007/978-3-642-36694-9_20 |
Popis: | We consider the problem of constructing a Steiner arborescence broadcasting a signal from a root r to a set T of sinks in a metric space, with out-degrees of Steiner vertices restricted to 2. The arborescence must obey delay bounds for each r-t-path (t∈T), where the path delay is imposed by its total edge length and its inner vertices. We want to minimize the total length. Computing such arborescences is a central step in timing optimization of VLSI design where the problem is known as the repeater tree problem [1,5]. We prove that there is no constant factor approximation algorithm unless $\mbox{\slshape P}=\mbox{\slshape NP}$ and develop a bicriteria approximation algorithm trading off signal speed (shallowness) and total length (lightness). The latter generalizes results of [8,3], which do not consider vertex delays. Finally, we demonstrate that the new algorithm improves existing algorithms on real world VLSI instances. |
Databáze: | OpenAIRE |
Externí odkaz: |