{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:23:25Z","timestamp":1787340205280,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2007,1]]},"abstract":"<jats:p>We consider a generalization of edge coloring bipartite graphs in which every edge has a weight in $[0,1]$ and the coloring of the edges must satisfy that the sum of the weights of the edges incident to a vertex v of any color must be at most 1. For unit weights, K\u00f6nig's theorem says that the number of colors needed is exactly the maximum degree. For this generalization, we show that $2.557 n + o(n)$ colors are sufficient, where n is the maximum total weight adjacent to any vertex, improving the previously best bound of $2.833n+O(1)$ due to Du et al. Our analysis is interesting on its own and involves a novel decomposition result for bipartite graphs and the introduction of an associated continuous one-dimensional bin packing instance which we can prove allows perfect packing. This question is motivated by the question of the rearrangeability of 3-stage Clos networks. In that context, the corresponding parameter n of interest in the edge coloring problem is the maximum over all vertices of the number of unit-sized bins needed to pack the weights of the incident edges. In that setting, we are able to improve the bound to $2.5480 n + o(n)$, also improving a bound of $2.5625n+O(1)$ of Du et al. We also consider the online version of this problem in which edges have to be colored as soon as they are revealed. In this context, we can show that $5n$ colors are enough. This contrasts with the best known lower bound of $3n-2$ by Tsai, Wang, and Hwang but improves upon the previous best upper bound of $5.75n$ obtained by Gao and Hwang. Additionally, we show several improved bounds for more restricted versions of the problem. These online bounds are achieved by simple and easy-to-implement algorithms, inspired by the first fit heuristic for bin packing.<\/jats:p>","DOI":"10.1137\/060656413","type":"journal-article","created":{"date-parts":[[2007,8,15]],"date-time":"2007-08-15T10:07:23Z","timestamp":1187172443000},"page":"870-894","source":"Crossref","is-referenced-by-count":16,"title":["Improved Bounds on Nonblocking 3-Stage Clos Networks"],"prefix":"10.1137","volume":"37","author":[{"given":"Jos\u00e9 R.","family":"Correa","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michel X.","family":"Goemans","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2007,8,15]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90209-E"},{"key":"R2","first-page":"64","volume":"9","author":"Bassalygo L. A.","year":"1974","journal-title":"Problems Inform. Transmission","ISSN":"https:\/\/id.crossref.org\/issn\/0032-9460","issn-type":"print"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"J. Beetem, M. Denneau, and D. Weingarten,\n                      The GF\n                      11\n                      supercomputer\n                      , in Proceedings of the 12th ACM Annual International Symposium on Computer Architecture, 1985, pp. 108\u2013115.","DOI":"10.1145\/327070.327139"},{"key":"R4","unstructured":"B. Beizer,\n                      The analysis and synthesis of signal switching networks\n                      , in Proceedings of the Symposium on Mathematical Theory of Automata, 1962, pp. 563\u2013576."},{"key":"R5","unstructured":"V. E. Benes,\n                      Mathematical Theory of Connecting Networks and Telephone Traffic\n                      , Academic Press, New York, 1965."},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1964.tb04103.x"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"P. Brucker, J. Hurink, and F. Werner,\n                      Improving local search heuristics for some scheduling problems\n                      \u2014I, Discrete Appl. Math., 65 (1996), pp. 97\u2013122.","DOI":"10.1016\/0166-218X(95)00030-U"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0220046"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1953.tb01433.x"},{"key":"R10","first-page":"165","volume":"8","author":"de Werra D.","year":"1970","journal-title":"CORS. J."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n                      Graph Theory\n                      , Grad. Texts in Math. 173, Springer-Verlag, New York, 1997.","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795284716"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00151-X"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"P. Haxell, A. Rasala, G. Wilfong, and P. Winkler,\n                      Wide-sense nonblocking WDM cross-connects\n                      , in Proceedings of the 10th European Symposium on Algorithms (ESA 2002), Lecture Notes in Comput. Sci. 2461, Springer-Verlag, Berlin, 2002, pp. 538\u2013550.","DOI":"10.1007\/3-540-45749-6_48"},{"key":"R15","first-page":"211","volume":"46","author":"Hoffman A. J.","year":"1956","journal-title":"J. Washington Acad. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0043-0439","issn-type":"print"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1109\/49.105174"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"N. Karmarkar,\n                      Probabilistic analysis of some bin-packing algorithms\n                      , in Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, 1982, pp. 107\u2013111.","DOI":"10.1109\/SFCS.1982.37"},{"key":"R18","unstructured":"N. Karmarkar and R. M. Karp,\n                      The Differencing Method of Set Partitioning\n                      , Technical report UCB\/CSD 82\/113, University of California, Berkeley, CA, 1982."},{"key":"R19","first-page":"104","volume":"34","author":"K\u00f6nig D.","year":"1916","journal-title":"Mathematikai \u00e9s Term\u00e9szettudom\u00e1nyi \u00c9rtesit\u00f6"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796313921"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"G. Lin, D. Du, W. Wu, and K. Yoo,\n                      On 3-rate rearrangeability of Clos networks\n                      , in Advances in Switching Networks, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 42. AMS, Providence, RI, 1998, pp. 315\u2013333.","DOI":"10.1090\/dimacs\/042\/19"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(84)90004-X"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/0218021"},{"key":"R24","unstructured":"H. Q. Ngo and V. H. Vu,\n                      Multirate rearrangeable Clos networks and a generalized edge coloring problem on bipartite graphs\n                      , in Proceedings of the Fourteenth ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), 2003, pp. 834\u2013840."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1287\/moor.13.1.140"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1145\/44483.44487"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1950.tb02349.x"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"P. Schuurman and T. Vredeveld,\n                      Performance guarantees of local search for multiprocessor scheduling\n                      , in Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization (IPCO 2001), Springer-Verlag, Berlin, 2001, pp. 370\u2013382.","DOI":"10.1007\/3-540-45535-3_29"},{"key":"R29","unstructured":"D. Slepian,\n                      Two Theorems on a Particular Crossbar Switching\n                      , manuscript, 1958."},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1109\/MCOM.2003.1235593"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00147-X"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/060656413","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:24:39Z","timestamp":1787336679000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/060656413"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["10.1137\/060656413"],"URL":"https:\/\/doi.org\/10.1137\/060656413","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1]]}}}