About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Discrete Applied Mathematics
Paper
Integer programming in VLSI design
Abstract
This paper surveys some recent developments in the application of combinatorial optimization to VLSI design. We focus on integer programs arising in wire routing and PLA partitioning. Typically, the integer programs we are interested in are computationally difficult. We present approaches to approximately solving them by rounding the solutions to the relaxed linear programs. The resulting algorithms run in polynomial time and have provable performance guarantees. We also introduce the notion of multiterminal multicommodity flows, and point out their relevance to VLSI routing. © 1992.