Allan Borodin, Jon Kleinberg, et al.
Journal of the ACM
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.
Allan Borodin, Jon Kleinberg, et al.
Journal of the ACM
Cynthia Dwork, Ravi Kumar, et al.
WWW 2001
Moses Charikar, Shay Solomon
ICALP 2018
T.S. Jayram, Subhash Khot, et al.
Journal of Computer and System Sciences