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