{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:36:17Z","timestamp":1750307777718,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,3,1]],"date-time":"2008-03-01T00:00:00Z","timestamp":1204329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2008,3]]},"abstract":"<jats:p>\n            We introduce a problem directly inspired by its application to DWDM (\n            <jats:italic>dense wavelength division multiplexing<\/jats:italic>\n            ) network design. We are given a set of demands to be carried over a network. Our goal is to choose a route for each demand and to decompose the network into a collection of edge-disjoint simple paths. These paths are called\n            <jats:italic>optical line systems<\/jats:italic>\n            . The cost of routing one unit of demand is the number of line systems with which the demand route overlaps; our design objective is to minimize the total cost over all demands. This cost metric is motivated by the need to minimize O-E-O (\n            <jats:italic>optical-electrical-optical<\/jats:italic>\n            ) conversions in optical transmission.\n          <\/jats:p>\n          <jats:p>For given line systems, it is easy to find the optimal demand routes. On the other hand, for given demand routes designing the optimal line systems can be NP-hard. We first present a 2-approximation for general network topologies. As optical networks often have low node degrees, we offer an algorithm that finds the optimal solution for the special case in which the node degree is at most 3. Our solution is based on a local greedy approach.<\/jats:p>\n          <jats:p>\n            If neither demand routes nor line systems are fixed, the situation becomes much harder. Even for a restricted scenario on a 3-regular Hamiltonian network, no efficient algorithm can guarantee a constant approximation better than 2. For general topologies, we offer a simple algorithm with an\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>K<\/jats:italic>\n            )- and an\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            )-approximation, where\n            <jats:italic>K<\/jats:italic>\n            is the number of demands and\n            <jats:italic>n<\/jats:italic>\n            the number of nodes. This approximation ratio is almost tight. For rings, a common special topology, we offer a more complex 3\/2-approximation algorithm.\n          <\/jats:p>","DOI":"10.1145\/1328911.1328926","type":"journal-article","created":{"date-parts":[[2008,4,1]],"date-time":"2008-04-01T16:08:32Z","timestamp":1207066112000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Path decomposition under a new cost measure with applications to optical network design"],"prefix":"10.1145","volume":"4","author":[{"given":"Elliot","family":"Anshelevich","sequence":"first","affiliation":[{"name":"Rensselaer Polytechnic Institute, Troy, NY"}]},{"given":"Lisa","family":"Zhang","sequence":"additional","affiliation":[{"name":"Bell Laboratories, Murray Hill, NJ"}]}],"member":"320","published-online":{"date-parts":[[2008,3,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0998"},{"volume-title":"Proceedings of l\u00e8re Rencontres Francophones sur les Aspects Algorithmiques des T\u00e9l\u00e9communications, 77--82","author":"Bermond J.-C.","key":"e_1_2_1_2_1","unstructured":"Bermond , J.-C. , Marlin , N. , Peleg , D. , and P\u00e9rennes , S . 1999. Virtual path layouts with low congestion or low diameter in ATM networks . In Proceedings of l\u00e8re Rencontres Francophones sur les Aspects Algorithmiques des T\u00e9l\u00e9communications, 77--82 . Bermond, J.-C., Marlin, N., Peleg, D., and P\u00e9rennes, S. 1999. Virtual path layouts with low congestion or low diameter in ATM networks. In Proceedings of l\u00e8re Rencontres Francophones sur les Aspects Algorithmiques des T\u00e9l\u00e9communications, 77--82."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190160209"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02110141"},{"key":"e_1_2_1_5_1","volume-title":"LIPI: A lightpath intelligent instantiation tool: Capabilities and impact. Bell Labs Tech. J.","author":"Doshi B.","year":"2002","unstructured":"Doshi , B. , Nagarajan , R. , Blackwood , N. , Jothipragasam , S. , Raman , N. , Sharma , M. , and Prasanna , S . 2002 . LIPI: A lightpath intelligent instantiation tool: Capabilities and impact. Bell Labs Tech. J. Doshi, B., Nagarajan, R., Blackwood, N., Jothipragasam, S., Raman, N., Sharma, M., and Prasanna, S. 2002. LIPI: A lightpath intelligent instantiation tool: Capabilities and impact. Bell Labs Tech. J."},{"volume-title":"Interval Orders and Interval Graphs","author":"Fishburn P.","key":"e_1_2_1_6_1","unstructured":"Fishburn , P. 1985. Interval Orders and Interval Graphs . Wiley and Sons , New York . Fishburn, P. 1985. Interval Orders and Interval Graphs. Wiley and Sons, New York."},{"volume-title":"Proceedings of the 11th International Telecommunications Network Strategy and Planning Symposium (Networks).","author":"Fortune S.","key":"e_1_2_1_7_1","unstructured":"Fortune , S. , Sweldens , W. , and Zhang , L . 2004. Line system design for DWDM networks . In Proceedings of the 11th International Telecommunications Network Strategy and Planning Symposium (Networks). Fortune, S., Sweldens, W., and Zhang, L. 2004. Line system design for DWDM networks. In Proceedings of the 11th International Telecommunications Network Strategy and Planning Symposium (Networks)."},{"key":"e_1_2_1_8_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability - A Guide to the Theory of NP-Completeness. W. H. Freeman New York.   Garey M. R. and Johnson D. S. 1979. Computers and Intractability - A Guide to the Theory of NP-Completeness. W. H. Freeman New York."},{"volume-title":"Proceedings of the IEEE INFOCOM.","author":"Gerstel O.","key":"e_1_2_1_9_1","unstructured":"Gerstel , O. and Segall , A . 1995. Dynamic maintenance of the virtual path layout . In Proceedings of the IEEE INFOCOM. Gerstel, O. and Segall, A. 1995. Dynamic maintenance of the virtual path layout. In Proceedings of the IEEE INFOCOM."},{"key":"e_1_2_1_10_1","unstructured":"Khanna S. 1997. A polynomial-time approximation scheme for the SONET ring loading problem. Bell Labs Tech. J.  Khanna S. 1997. A polynomial-time approximation scheme for the SONET ring loading problem. Bell Labs Tech. J."},{"volume-title":"Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 566--575","author":"Kleinberg J.","key":"e_1_2_1_11_1","unstructured":"Kleinberg , J. and Kumar , A . 1999. Wavelength conversion in optical networks . In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 566--575 . Kleinberg, J. and Kumar, A. 1999. Wavelength conversion in optical networks. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 566--575."},{"volume-title":"Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 437--444","author":"Kumar V.","key":"e_1_2_1_12_1","unstructured":"Kumar , V. and Schwabe , E . 1997. Improved access to optical bandwidth in trees . In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 437--444 . Kumar, V. and Schwabe, E. 1997. Improved access to optical bandwidth in trees. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 437--444."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02785579"},{"volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"McGregor A.","key":"e_1_2_1_14_1","unstructured":"McGregor , A. and Shepherd , B . 2007. Island hopping and path coloring with respect to WDM network design . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). McGregor, A. and Shepherd, B. 2007. Island hopping and path coloring with respect to WDM network design. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"volume-title":"Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS), 548--557","author":"Mihail M.","key":"e_1_2_1_15_1","unstructured":"Mihail , M. , Kaklamanis , C. , and Rao , S . 1995. Efficient access to optical bandwidth . In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS), 548--557 . Mihail, M., Kaklamanis, C., and Rao, S. 1995. Efficient access to optical bandwidth. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS), 548--557."},{"key":"e_1_2_1_16_1","unstructured":"Papadimitriou C. and Steiglitz K. 1998. Combinatorial Optimization. Dover Mineola New York.  Papadimitriou C. and Steiglitz K. 1998. Combinatorial Optimization. Dover Mineola New York."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195119"},{"key":"e_1_2_1_18_1","volume-title":"Optical Networks: A Practical Perspective. Morgan Kaufmann","author":"Ramaswami R.","year":"1998","unstructured":"Ramaswami , R. and Sivarajan , K . 1998 . Optical Networks: A Practical Perspective. Morgan Kaufmann , San Francisco, CA . Ramaswami, R. and Sivarajan, K. 1998. Optical Networks: A Practical Perspective. Morgan Kaufmann, San Francisco, CA."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480195294994"},{"volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 333--341","author":"Wilfong G.","key":"e_1_2_1_20_1","unstructured":"Wilfong , G. and Winkler , P . 1998. Ring routing and wavelength translation . In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 333--341 . Wilfong, G. and Winkler, P. 1998. Ring routing and wavelength translation. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 333--341."},{"volume-title":"Networks in Distributed Computing","author":"Zaks S.","key":"e_1_2_1_21_1","unstructured":"Zaks , S. 1998. Path layout in ATM networks - A survey . In Networks in Distributed Computing ; DIMACS : Series in Discrete Mathematics and Theoretical Computer Science , 145--160. Zaks, S. 1998. Path layout in ATM networks - A survey. In Networks in Distributed Computing; DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, 145--160."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1328911.1328926","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1328911.1328926","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:56:03Z","timestamp":1750254963000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1328911.1328926"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,3]]}},"alternative-id":["10.1145\/1328911.1328926"],"URL":"https:\/\/doi.org\/10.1145\/1328911.1328926","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2008,3]]},"assertion":[{"value":"2005-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-03-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}