Jon Kleinberg, Christos Papadimitriou, et al.
Data Mining and Knowledge Discovery
An important problem in VLSI design is distributing a clock signal to synchronous elements in a VLSI circuit so that the signal arrives at all elements simultaneously. The signal is distributed by means of a clock routing tree rooted at a global clock source. The difference in length between the longest and shortest root-leaf path is called the skew of the tree. The problem is to construct a clock tree with zero skew (to achieve synchronicity) and minimal sum of edge lengths (so that circuit area and clock tree capacitance are minimized). We give the first constant-factor approximation algorithms for this problem and its variants that arise in the VLSI context. For the zero skew problem in general metric spaces, we give an approximation algorithm with a performance guarantee of 2e. For the L 1 version on the plane, we give an (8/ ln 2)-approximation algorithm.
Jon Kleinberg, Christos Papadimitriou, et al.
Data Mining and Knowledge Discovery
Tuǧkan Batu, Sanjoy Dasgupta, et al.
SIAM Journal on Computing
Ravi Kumar, Jasmine Novak, et al.
World Wide Web
Song Feng, Sujith Ravi, et al.
AAAI/IAAI 2015