{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:53Z","timestamp":1750308773407,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p>We investigate the problem of online routing and wavelength assignment and the related throughput maximization problem in wavelength division multiplexing optical networks. It is pointed out that these problems are highly inapproximable, that is, the competitive ratio of any algorithm is at least a polynomial. We evaluate the average-case performance of several online algorithms, which have no knowledge of future arriving connection requests when processing the current connection request. Our experimental results on a wide range of optical networks demonstrate that the average-case performance of these algorithms are very close to optimal.<\/jats:p>","DOI":"10.1145\/1227161.1370598","type":"journal-article","created":{"date-parts":[[2008,10,8]],"date-time":"2008-10-08T13:57:58Z","timestamp":1223474278000},"page":"1-24","source":"Crossref","is-referenced-by-count":5,"title":["Experimental average-case performance evaluation of online algorithms for routing and wavelength assignment and throughput maximization in WDM optical networks"],"prefix":"10.1145","volume":"12","author":[{"given":"Keqin","family":"Li","sequence":"first","affiliation":[{"name":"State University of New York at New Paltz, New York"}]}],"member":"320","published-online":{"date-parts":[[2008,6,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026569720098"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366884"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/314464.314510"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365675"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/49.510913"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.879346"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/646251.685860"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.238001"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/ett.4460100509"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/290169"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1895807.1895832"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.153361"},{"volume-title":"Proceedings of the 7th International Conference on Optical Communications and Networks. 1109--1115","author":"Choi J. S.","key":"e_1_2_1_13_1","unstructured":"Choi, J. S., Golmie, N., Lapeyrere, F., Mouveaux, F., and Su, D. 2000. A functional classification of routing and wavelength assignment, schemes in DWDM networks: Static case. Proceedings of the 7th International Conference on Optical Communications and Networks. 1109--1115."},{"key":"e_1_2_1_14_1","volume-title":"An Introduction, to Probability Theory and Its Applications","author":"Feller W.","unstructured":"Feller, W. 1968. An Introduction, to Probability Theory and Its Applications, Vol. 1, 3rd edn. Wiley, New York.","edition":"3"},{"key":"e_1_2_1_15_1","unstructured":"Ford L. R. and Fulkerson D. R. 1962. Flows in Networks. Princeton University Press Princeton New Jersey."},{"key":"e_1_2_1_16_1","volume-title":"Statistics: A First Course","author":"Freund J. E.","year":"1981","unstructured":"Freund, J. E. 1981. Statistics: A First Course, 3rd edn. Prentice-Hall, Englewood Cliffs, New Jersey.","edition":"3"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301262"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.21236\/AD0705364"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89568"},{"key":"e_1_2_1_20_1","first-page":"143","article-title":"An extremal problem in recursive combinatorics","volume":"33","author":"Kierstead H. A.","year":"1981","unstructured":"Kierstead, H. A. and Trotter, W. T. 1981. An extremal problem in recursive combinatorics. Congressus Numerantium 33, 143--153.","journal-title":"Congressus Numerantium"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796280"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/314613.314724"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of Optical Networks Workshop","author":"Li G.","year":"2000","unstructured":"Li, G. and Simha, R. 2000. The partition coloring problem and its application to wavelength routing and assignment. Proceedings of Optical Networks Workshop, Richardson, Texas. (See http:\/\/mozart.utdallas.edu\/ONW2000\/proceedings.)"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 3rd International Conference on Communications in Computing","author":"Li K.","year":"2002","unstructured":"Li, K. 2002. Inapproximability results for wavelength assignment in wavelength division multiplexing optical networks. Proceedings of the 3rd International Conference on Communications in Computing, Las Vegas, Nevada. 217--223."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10586-005-6177-5"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/50.387798"},{"key":"e_1_2_1_27_1","unstructured":"Palmer E. M. 1985. Graphical Evolution. Wiley New York."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.469957"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/275688"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","unstructured":"Stern T. B. and Bala K. 2000. Multiwavelength Optical Networks\u2014A Layered Approach Prentice-Hall Upper Saddle River New Jersey.","DOI":"10.5555\/553835"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.392387"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1370598","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1227161.1370598","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:37Z","timestamp":1750278157000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1370598"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":31,"alternative-id":["10.1145\/1227161.1370598"],"URL":"https:\/\/doi.org\/10.1145\/1227161.1370598","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}