Quantified Suboptimality of VLSI Layout Heuristics

We show how to quantify the suboptimality of heuristic algorithms for NP-hard problems arising in VLSI layout. Our approach is based on the notion of constructing new scaled instances from an initial problem instance. From the given problem instance, we essentially construct doubled, tripled, etc. instances which have optimum solution costs at most twice, three times, etc. that of the original instance. By executing the heuristic on these scaled instances, and then comparing the growth of solution cost with the growth of instance size, we can measure the scaling suboptimality of the heuristic. We give experimentally determined scaling behavior of several placement and partitioning heuristics; these results suggest that siginificant improvement remains possible over current state-of-the-art methods.