Greedy wire-sizing is linear time

The greedy wire-sizing algorithm (GWSA) has been experimentally shown to be very efficient, but no mathematical analysis on its convergence rate has e ver been reported. In this paper, we consider GWSA for continuous wire sizi ng. We prove that GWSA converges linearly to the optimal solution, which im plies that the run time of GWSA is linear with respect to the number of wir e segments for any filed precision of the solution. Moreover, we also prove that this is true for any starting solution. This is a surprising result b ecause previously it was believed that in order to guarantee convergence, G WSA had to start from a solution in which every wire segment is set to the minimum (or maximum) possible width. Our result implies that GWSA can use a good starting solution to achieve faster convergence, We demonstrate this point by showing that the minimization of maximum delay and the minimizatio n of area subject to maximum delay bound using Lagrangian relaxation can be sped up by more than 50%.