{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T13:30:51Z","timestamp":1791034251701,"version":"4.1.0"},"reference-count":40,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2000,1]]},"abstract":"<jats:p>This paper investigates the global routing problem for integrated circuits. We introduce a formulation on the basis of integer programming which minimizes the routing area among a limited set of Steiner trees for each net. Indeed, the involved cost function depends on the channel density of the routing which has a direct influence on the routing area.<\/jats:p>\n                  <jats:p>Our methods for solving the global routing problem employ local search heuristics, sequential routing, genetic routing, and randomized procedures. Our methods for computing lower bounds are based on linear and Lagrange relaxation. An analysis on the tightness of the bounds indicates that the difference between the cost of the optimal integer solutions and the cost of the optimal fractional solutions is only a small number of tracks in practice. Moreover, the analysis leads to the concept of linear preprocessing by which we exclude a large number of high-cost solutions.<\/jats:p>\n                  <jats:p>We introduce several versions of preprocessing, one of which preserves the opportunity of obtaining a globally optimal solution in general; all of them do so in practice. Linear preprocessing enables us to solve problem instances with several thousand nets provably optimal or at least provably close to optimal.<\/jats:p>\n                  <jats:p>All methods have been implemented in the software package Eridanus. We presentcomputational results.<\/jats:p>\n                  <jats:p>The global routing problem assumes the placement of the chip components to be fixed. An extension of the problem, which we call global layout of integrated circuits, allows the placement to be variable and searches for a placement that minimizes the routing area among a limited set of alternatives. We show that the results concerning the global routing problem can be easily extended to global layout.<\/jats:p>","DOI":"10.1137\/s1052623497331786","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1-30","source":"Crossref","is-referenced-by-count":10,"title":["Provably Good Global Routing of Integrated Circuits"],"prefix":"10.1137","volume":"11","author":[{"given":"T.","family":"Lengauer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M.","family":"L\u00fcgering","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","unstructured":"M. Burstein and S. J. Hong,\n                      Hierarchical VLSI layout: Simultaneous wiring and placement\n                      , in Proceedings of VLSI \u201983, F. Anceau and E. J. Aas, eds., Elsevier Science Publishers B. V., Amsterdam, 1983, pp. 45\u201360."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1983.1270040"},{"key":"R3","unstructured":"R. C. Carden and C.\u2010K. Cheng,\n                      A global router using an efficient approximate multicommodity multiterminal flow algorithm\n                      , in Proceedings of the 28th Design Automation Conference, San Francisco, ACM\/IEEE, 1991, pp. 316\u2013321."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1109\/43.486666"},{"key":"R5","unstructured":"C. Chiang, M. Sarrafzadeh, and C. K. Wong,\n                      A powerful global router: Based on Steiner min\u2010max trees\n                      , in Proceedings of the International Conference on Computer\u2010Aided Design, Sanata Clara, CA, IEEE, 1989, pp. 2\u20135."},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1109\/43.62776"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1109\/43.331403"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1987.1270326"},{"key":"R9","unstructured":"H. Esbensen,\n                      A macro\u2010cell global router based on two genetic algorithms\n                      , in Proceedings of the European Design Automation Conference, Grenoble, 1994, pp. 428\u2013433."},{"key":"R10","unstructured":"H. Esbensen and P. Mazumder,\n                      A genetic algorithm for the Steiner problem in a graph\n                      , in Proceedings of the European Design and Test Conference, Paris, 1994, pp. 402\u2013406."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592086"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1996.0004"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592085"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480193258716"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/S0025-5610(97)00016-6"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1109\/43.137503"},{"key":"R17","volume-title":"Adaptation in natural and artificial systems","author":"Holland John","year":"1975"},{"key":"R18","unstructured":"T. C. Hu,\n                      Integer Programming and Network Flows\n                      , Addison\u2010Wesley, Reading, MA, 1969."},{"key":"R19","unstructured":"T. C. Hu and M. T. Shing,\n                      A decomposition algorithm for circuit routing\n                      , in VLSI Circuit Layout: Theory and Design, T. C. Hu and E. S. Kuh, eds., IEEE, New York, 1985, pp. 144\u2013152."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579150"},{"key":"R21","unstructured":"R. M. Karp,\n                      Reducibility among combinatorial problems\n                      , in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum Press, New York, 1972, pp. 85\u2013103."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840353"},{"key":"R23","first-page":"1093","volume":"244","author":"Khachian L. G.","year":"1979","journal-title":"Doklady Akad. Nauk. USSR"},{"key":"R23","first-page":"191","volume":"20","year":"1979","journal-title":"Soviet Math. Doklady","ISSN":"https:\/\/id.crossref.org\/issn\/0197-6788","issn-type":"print"},{"key":"R24","unstructured":"BernhardKorte, HansPr\u00f6mel, AngelikaSteger, Steiner trees in VLSI\u2010layout, Algorithms Combin., Vol. 9, Springer, Berlin, 1990, 185\u201321492f:68078"},{"key":"R25","unstructured":"M. R. Kramer and J. van Leeuwen,\n                      The complexity of wire routing and finding minimum area layouts for arbitrary VLSI circuits\n                      , in Advances in Computing Research, Vol. 2: VLSI Theory, F. P. Preparata, ed., JAI Press, Reading, MA, 1984, pp. 129\u2013146."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-322-92106-2"},{"key":"R27","unstructured":"T. Lengauer and M. L\u00fcgering,\n                      Integer program formulations of global routing and placement problems\n                      , in Algorithmic Aspects of VLSI Layout, M. Sarrafzadeh and D. T. Lee, eds., Lecture Notes Series on Computing 2, World Scientific, Singapore, 1993, pp. 167\u2013197."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1109\/43.229754"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1987.1270300"},{"key":"R30","first-page":"229","volume":"6","author":"Ng A. P.\u2010C.","year":"1987","journal-title":"Comput. Artificial Intelligence"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90003-7"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759035"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1145\/77600.77620"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-9260(87)80003-2"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1983.1270048"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1109\/43.68406"},{"key":"R38","unstructured":"G. Zimmermann,\n                      Top\u2010down design of digital systems\n                      , in Advances in CAD for VLSI, Volume 2: Logic Design and Simulation, E. H\u00f6rbst, ed., North\u2010Holland, New York, 1986, pp. 185\u2013206."},{"key":"R39","unstructured":"G. Zimmermann,\n                      A new area and shape function estimation technique for VLSI layouts\n                      , in Proceedings of the 25th Design Automation Conference, Anaheim, CA, ACM\/IEEE, 1988, pp. 60\u201365."}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S1052623497331786","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:41:31Z","timestamp":1787330491000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S1052623497331786"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,1]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2000,1]]}},"alternative-id":["10.1137\/S1052623497331786"],"URL":"https:\/\/doi.org\/10.1137\/s1052623497331786","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,1]]}}}