{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:41:55Z","timestamp":1760164915355,"version":"build-2065373602"},"reference-count":33,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2021,5,11]],"date-time":"2021-05-11T00:00:00Z","timestamp":1620691200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>All-optical networks transmit messages along lightpaths in which the signal is transmitted using the same wavelength in all the relevant links. We consider the problem of switching cost minimization in these networks. Specifically, the input to the problem under consideration is an optical network modeled by a graph G, a set of lightpaths modeled by paths on G, and an integer g termed the grooming factor. One has to assign a wavelength (modeled by a color) to every lightpath, so that every edge of the graph is used by at most g paths of the same color. A lightpath operating at some wavelength \u03bb uses one Add\/Drop multiplexer (ADM) at both endpoints and one Optical Add\/Drop multiplexer (OADM) at every intermediate node, all operating at a wavelength of \u03bb. Two lightpaths, both operating at the same wavelength \u03bb, share the ADMs and OADMs in their common nodes. Therefore, the total switching cost due to the usage of ADMs and OADMs depends on the wavelength assignment. We consider networks of ring and path topology and a cost function that is a convex combination \u03b1\u00b7|OADMs|+(1\u2212\u03b1)|ADMs| of the number of ADMs and the number of OADMs deployed in the network. We showed that the problem of minimizing this cost function is NP-complete for every convex combination, even in a path topology network with g=2. On the positive side, we present a polynomial-time approximation algorithm for the problem.<\/jats:p>","DOI":"10.3390\/a14050151","type":"journal-article","created":{"date-parts":[[2021,5,11]],"date-time":"2021-05-11T10:20:36Z","timestamp":1620728436000},"page":"151","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["The Traffic Grooming Problem in Optical Networks with Respect to ADMs and OADMs: Complexity and Approximation"],"prefix":"10.3390","volume":"14","author":[{"given":"Michele","family":"Flammini","sequence":"first","affiliation":[{"name":"GSSI Institute, Viale Francesco Crispi 7, 67100 L\u2019Aquila, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianpiero","family":"Monaco","sequence":"additional","affiliation":[{"name":"Department of Information Engineering Computer Science and Mathematics, University of L\u2019Aquila, 67100 L\u2019Aquila, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca","family":"Moscardelli","sequence":"additional","affiliation":[{"name":"Dipartimento di Economia, University of Chieti-Pescara, Viale Pindaro 42, 65125 Pescara, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2688-5703","authenticated-orcid":false,"given":"Mordechai","family":"Shalom","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Tel-Hai Academic College, Upper Galilee 1220800, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shmuel","family":"Zaks","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Technion, Haifa 3200003, Israel"},{"name":"Member of the Academic Council, Ort Braude College, Karmiel 2161002, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,5,11]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/2.191977","article-title":"Distributed computing with high-speed optical networks","volume":"26","author":"Du","year":"1993","journal-title":"Computer"},{"key":"ref_2","unstructured":"Green, P.E. (1992). Fiber-Optic Communication Networks, Prentice Hall."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"948","DOI":"10.1109\/49.57798","article-title":"Dense Wavelength Division Multiplexing Networks: Principles and applications","volume":"8","author":"Brackett","year":"1990","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_4","unstructured":"Klasing, R. (1998, January 24\u201325). Methods and problems of wavelength-routing in all-optical networks. Proceedings of the MFCS\u201998 Workshop on Communication, Brno, Czech Republic."},{"key":"ref_5","unstructured":"Beauquier, B., Bermond, J.C., Gargano, L., Hell, P., Perennes, S., and Vaccaro, U. (1997, January 1). Graph problems arising from Wavelength\u2013Routing in All\u2013Optical Networks. Proceedings of the 2nd Workshop on Optics and Computer Science, WOCS\u201997, Geneva, Switzerland."},{"key":"ref_6","unstructured":"Gerstel, O., Lin, P., and Sasaki, G. (April, January 29). Wavelength Assignment in a WDM Ring to Minimize Cost of Embedded SONET Rings. Proceedings of the INFOCOM\u201998, Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies, San Francisco, CA, USA."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1109\/49.974671","article-title":"Lightpath Arrangement in Survivable Rings to Minimize the Switching Cost","volume":"20","author":"Eilam","year":"2002","journal-title":"IEEE J. Sel. Area Commun."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1023\/A:1019525904862","article-title":"Traffic Partition in WDM\/SONET rings to minimize SONET ADMs","volume":"6","author":"Wan","year":"2002","journal-title":"J. Comb. Optim."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1593","DOI":"10.1109\/TNET.2007.906638","article-title":"A 10\/7 + epsilon approximation for minimizing the number of ADMs in SONET rings","volume":"15","author":"Shalom","year":"2007","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/j.jcss.2008.08.003","article-title":"Better bounds for minimizing SONET ADMs","volume":"75","author":"Epstein","year":"2009","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00607-009-0072-5","article-title":"Minimization of SONET ADMs in ring networks revisited","volume":"87","author":"Epstein","year":"2010","journal-title":"Computing"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1109\/49.974672","article-title":"Minimizing Electronic Line Terminals for Automatic Ring Protection in General WDM Optical Networks","volume":"20","author":"Frieder","year":"2002","journal-title":"IEEE J. Sel. Area Commun."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1721","DOI":"10.1016\/j.comnet.2008.02.009","article-title":"Selfishness, collusion and power of local search for the ADMs minimization problem","volume":"52","author":"Flammini","year":"2008","journal-title":"Comput. Netw."},{"key":"ref_14","unstructured":"Gerstel, O., Ramaswami, R., and Sasaki, G. (April, January 29). Cost effective traffic grooming in WDM rings. Proceedings of the INFOCOM\u201998, Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies, San Francisco, CA, USA."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1109\/50.818901","article-title":"Traffic Grooming Algorithms for Reducing Electronic Multiplexing Costs in WDM Ring Networks","volume":"18","author":"Chiu","year":"2000","journal-title":"J. Light. Technol."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1109\/JSAC.2006.1613773","article-title":"Traffic grooming in path, star, and tree networks: Complexity, bounds, and algorithms","volume":"24","author":"Huang","year":"2006","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Shalom, M., Unger, W., and Zaks, S. (2007, January 3\u20135). On the Complexity of the Traffic Grooming Problem in Optical Networks. Proceedings of the Fun with Algorithms, 4th International Conference, Castiglioncello, Italy.","DOI":"10.1007\/978-3-540-72914-3_23"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1016\/j.jda.2007.09.001","article-title":"Approximating the Traffic Grooming Problem","volume":"6","author":"Flammini","year":"2008","journal-title":"J. Discret. Algorithms"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"939","DOI":"10.1016\/j.jpdc.2008.01.003","article-title":"Approximating the traffic grooming problem in tree and star networks","volume":"68","author":"Flammini","year":"2008","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"3751","DOI":"10.1016\/j.tcs.2009.04.028","article-title":"Hardness and approximation of traffic grooming","volume":"410","author":"Amini","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Chen, B., Rouskas, G.N., and Dutta, R. (2004). Traffic Grooming in WDM Ring Networks with the Min-Max Objective. Networking 2004, Proceedings of the International Conference on Research in Networking, Athens, Greece, 9\u201314 May 2004, Springer.","DOI":"10.1007\/978-3-540-24693-0_15"},{"key":"ref_22","unstructured":"Chen, B., Rouskas, G.N., and Dutta, R. (2004, January 25\u201329). Traffic Grooming in Star Networks. Proceedings of the BROADNETS, San Jose, CA, USA."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1109\/TNET.2010.2068309","article-title":"On the complexity of the regenerator placement problem in optical networks","volume":"19","author":"Flammini","year":"2011","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"7109","DOI":"10.1016\/j.tcs.2011.09.023","article-title":"Optimizing regenerator cost in traffic grooming","volume":"412","author":"Flammini","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1007\/s00453-012-9693-8","article-title":"On the Complexity of the Regenerator Cost Problem in General Networks with Traffic Grooming","volume":"68","author":"Flammini","year":"2014","journal-title":"Algorithmica"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Ellen, F., Kolokolova, A., and Sack, J.R. (2017). Busy Time Scheduling on a Bounded Number of Machines (Extended Abstract). Algorithms and Data Structures, Springer International Publishing.","DOI":"10.1007\/978-3-319-62127-2"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1007\/s10951-017-0531-3","article-title":"LP rounding and combinatorial algorithms for minimizing active and busy time","volume":"20","author":"Chang","year":"2017","journal-title":"J. Sched."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"3553","DOI":"10.1016\/j.tcs.2010.05.011","article-title":"Minimizing total busy time in parallel scheduling with application to optical networks","volume":"411","author":"Flammini","year":"2010","journal-title":"Theor. Comput. Sci."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"524","DOI":"10.1016\/j.tcs.2014.10.033","article-title":"Optimizing busy time on parallel machines","volume":"562","author":"Mertzios","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1007\/s10951-014-0411-z","article-title":"Real-time scheduling to minimize machine busy times","volume":"18","author":"Khandekar","year":"2015","journal-title":"J. Sched."},{"key":"ref_31","unstructured":"Winkler, P., and Zhang, L. (2003, January 12\u201314). Wavelength assignment and generalized interval graph coloring. Proceedings of the SODA, Baltimore, MD, USA."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1166","DOI":"10.1137\/S0097539792229507","article-title":"Graph Decomposition Is NP-Complete: A Complete Proof Of Holyer\u2019s Conjecture","volume":"26","author":"Dor","year":"1997","journal-title":"SIAM J. Comput."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1006\/jcss.2000.1727","article-title":"On the Complexity of k-SAT","volume":"62","author":"Impagliazzo","year":"2001","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/5\/151\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:59:12Z","timestamp":1760162352000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/5\/151"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,11]]},"references-count":33,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2021,5]]}},"alternative-id":["a14050151"],"URL":"https:\/\/doi.org\/10.3390\/a14050151","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,5,11]]}}}