Budget management with applications

Given a directed acyclic graph with timing constraints, the budget management problem is to assign to each vertex an incremental delay such that the sum of these delays is maximized without violating given constraints. We propose the notion of slack sensitivity and budget gradient to demonstrate the characteristics of budget management. We develop a polynomial-time algorithm for the budget management problem, based on the maximum independent set of an established transitive graph. We show the comparison of our approach with the well-known zero-slack algorithm, and extend it to general weighted graphs. Applications to a class of problems in VLSI CAD are also discussed.