{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T08:48:56Z","timestamp":1774687736766,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540221135","type":"print"},{"value":"9783540259602","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-25960-2_24","type":"book-chapter","created":{"date-parts":[[2010,8,8]],"date-time":"2010-08-08T23:21:46Z","timestamp":1281309706000},"page":"308-324","source":"Crossref","is-referenced-by-count":14,"title":["Near-Optimum Global Routing with Coupling, Delay Bounds, and Power Consumption"],"prefix":"10.1007","author":[{"given":"Jens","family":"Vygen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"24_CR1","doi-asserted-by":"publisher","first-page":"622","DOI":"10.1109\/43.920691","volume":"20","author":"C. Albrecht","year":"2001","unstructured":"Albrecht, C.: Global routing by new approximation algorithms for multicommodity flow. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems\u00a020, 622\u2013632 (2001a)","journal-title":"IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems"},{"key":"24_CR2","unstructured":"Albrecht, C.: Zwei kombinatorische Optimierungsprobleme im VLSIDesign: Optimierung der Zykluszeit und der Slackverteilung und globale Verdrahtung. Ph.D. thesis, University of Bonn (2001b)"},{"key":"24_CR3","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/S0166-218X(01)00339-0","volume":"123","author":"C. Albrecht","year":"2002","unstructured":"Albrecht, C., Korte, B., Schietke, J., Vygen, J.: Maximum mean weight cycle in a digraph and minimizing cycle time of a logic chip. Discrete Applied Mathematics\u00a0123, 103\u2013127 (2002)","journal-title":"Discrete Applied Mathematics"},{"key":"24_CR4","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1109\/43.486666","volume":"15","author":"R.C. Carden IV","year":"1996","unstructured":"Carden IV, R.C., Li, J., Cheng, C.-K.: A global router with a theoretical bound on the optimum solution. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems\u00a015, 208\u2013216 (1996)","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"24_CR5","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"Chernoff, H.: A measure of asymptotic efficiency for tests based on the sum of observations. Annals of Mathematical Statistics\u00a023, 493\u2013509 (1952)","journal-title":"Annals of Mathematical Statistics"},{"key":"24_CR6","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1287\/moor.12.4.634","volume":"12","author":"R.E. Erickson","year":"1987","unstructured":"Erickson, R.E., Monma, C.L., Veinott Jr., A.F.: Send-and-split method for minimum concave-cost network flows. Mathematics of Operations Research\u00a012, 634\u2013664 (1987)","journal-title":"Mathematics of Operations Research"},{"key":"24_CR7","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/S0895480199355754","volume":"13","author":"L.K. Fleischer","year":"2000","unstructured":"Fleischer, L.K.: Approximating fractional multicommodity flow independent of the number of commodities. SIAM Journal on Discrete Mathematics\u00a013, 505\u2013520 (2000)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"24_CR8","doi-asserted-by":"crossref","unstructured":"Garg, N., K\u00f6nemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pp. 300\u2013309 (1998)","DOI":"10.1109\/SFCS.1998.743463"},{"key":"24_CR9","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1137\/0804004","volume":"4","author":"M.D. Grigoriadis","year":"1994","unstructured":"Grigoriadis, M.D., Khachiyan, L.G.: Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM Journal on Optimization\u00a04, 86\u2013107 (1994)","journal-title":"SIAM Journal on Optimization"},{"key":"24_CR10","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1287\/moor.21.2.321","volume":"21","author":"M.D. Grigoriadis","year":"1996","unstructured":"Grigoriadis, M.D., Khachiyan, L.G.: Coordination complexity of parallel price-directive decomposition. Mathematics of Operations Research\u00a021, 321\u2013340 (1996)","journal-title":"Mathematics of Operations Research"},{"key":"24_CR11","unstructured":"Ho, T.-Y., Chang, Y.-W., Chen, S.-J., Lee, D.-T.: A fast crosstalkand performance-driven multilevel routing system. In: Proceedings of the IEEE International Conference on Computer-Aided Design (November 2003)"},{"key":"24_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0167-9260(01)00020-7","volume":"31","author":"J. Hu","year":"2001","unstructured":"Hu, J., Sapatnekar, S.S.: A survey on multi-net global routing for intergated circuits. Integration, the VLSI Journal\u00a031, 1\u201349 (2001)","journal-title":"Integration, the VLSI Journal"},{"key":"24_CR13","doi-asserted-by":"crossref","unstructured":"Jing, T., Hong, X., Bao, H., Cai, Y., Xu, J., Cheng, C., Gu, J.: Utaco: a unified timing and congestion optimizing algorithm for standard cell global routing. In: Proceedings of the Asia and South Pacific Design Automation Conference, pp. 834\u2013839 (2003)","DOI":"10.1145\/1119772.1119956"},{"key":"24_CR14","unstructured":"Karakostas, G.: Faster approximation schemes for fractional multicommodity flow problems. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 166\u2013173 (2002)"},{"key":"24_CR15","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF01840353","volume":"2","author":"R.M. Karp","year":"1987","unstructured":"Karp, R.M., Leighton, F.T., Rivest, R.L., Thompson, C.D., Vazirani, U.V., Vazirani, V.V.: Global wire routing in two-dimensional arrays. Algorithmica\u00a02, 113\u2013129 (1987)","journal-title":"Algorithmica"},{"key":"24_CR16","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1137\/S0097539700379760","volume":"31","author":"T. Leighton","year":"2001","unstructured":"Leighton, T., Lu, C.-J., Rao, S., Srinivasan, A.: New algorithmic aspects of the Local Lemma with applications to routing and partitioning. SIAM Journal on Computing\u00a031, 626\u2013641 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"24_CR17","unstructured":"M\u00fcller, D.: Bestimmung der Verdrahtungskapazit\u00e4ten im Global Routing von VLSI-Chips. Diploma thesis, University of Bonn (2002)"},{"key":"24_CR18","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"S.A. Plotkin","year":"1995","unstructured":"Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9.: Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research\u00a020, 257\u2013301 (1995)","journal-title":"Mathematics of Operations Research"},{"key":"24_CR19","unstructured":"Raghavan, P.: Randomized rounding and discrete ham-sandwich theorems: provably good algorithms for routing and packing problems. Ph.D. thesis, Report No. UCB\/CSD 87\/312, University of California, Berkeley (1986)"},{"key":"24_CR20","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","volume":"37","author":"P. Raghavan","year":"1988","unstructured":"Raghavan, P.: Probabilistic construction of deterministic algorithms: approximating packing integer programs. Journal of Computer and System Sciences\u00a037, 130\u2013143 (1988)","journal-title":"Journal of Computer and System Sciences"},{"key":"24_CR21","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"Raghavan, P., Thompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica\u00a07, 365\u2013374 (1987)","journal-title":"Combinatorica"},{"key":"24_CR22","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BF01759035","volume":"6","author":"P. Raghavan","year":"1991","unstructured":"Raghavan, P., Thompson, C.D.: Multiterminal global routing: a deterministic approximation. Algorithmica\u00a06, 73\u201382 (1991)","journal-title":"Algorithmica"},{"key":"24_CR23","doi-asserted-by":"crossref","unstructured":"Roughgarden, T., Tardos, \u00c9.: How bad is selfish routing? In: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, pp. 93\u2013102 (2000)","DOI":"10.1109\/SFCS.2000.892069"},{"key":"24_CR24","unstructured":"Schulz, A., Stier Moses, N.: Performance of user equilibria in traffic networks. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 86\u201387 (2003)"},{"key":"24_CR25","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1145\/77600.77620","volume":"37","author":"F. Shahrokhi","year":"1990","unstructured":"Shahrokhi, F., Matula, D.W.: The maximum concurrent flow problem. Journal of the ACM\u00a037, 318\u2013334 (1990)","journal-title":"Journal of the ACM"},{"key":"24_CR26","unstructured":"Vygen, J.: Disjoint paths. Report No. 94816\u2013OR, Research Institute for Discrete Mathematics, University of Bonn (1994)"},{"key":"24_CR27","doi-asserted-by":"crossref","unstructured":"Xu, J., Hong, X., Jing, T., Cai, Y., Gu, J.: A novel timing-driven global routing algorithm considering coupling effects for high performance circuit design. In: Proceedings of the Asia and South Pacific Design Automation Conference, pp. 847\u2013850 (2003)","DOI":"10.1145\/1119772.1119958"},{"key":"24_CR28","unstructured":"Young, N.E.: Randomized rounding without solving the linear program. In: Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 170\u2013178 (1995)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-25960-2_24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T23:22:19Z","timestamp":1740352939000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-25960-2_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540221135","9783540259602"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-25960-2_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}