{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,5]],"date-time":"2025-06-05T04:12:26Z","timestamp":1749096746931,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662531730"},{"type":"electronic","value":"9783662531747"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53174-7_3","type":"book-chapter","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T14:50:06Z","timestamp":1470322206000},"page":"31-46","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Complexity of Approximation and Online Scheduling Problems with Applications to Optical Networks"],"prefix":"10.1007","author":[{"given":"Shmuel","family":"Zaks","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,5]]},"reference":[{"key":"3_CR1","first-page":"1","volume":"2","author":"J Akiyama","year":"1981","unstructured":"Akiyama, J., Chv\u00e1tal, V.: A short proof of the linear arboricity for cubic graphs. Bull. Liberal Arts Sci. Nippon Med. Sch. 2, 1\u20133 (1981)","journal-title":"Bull. Liberal Arts Sci. Nippon Med. Sch."},{"issue":"1\u20132","key":"3_CR2","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theoret. Comput. Sci. 237(1\u20132), 123\u2013134 (2000)","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0012-365X(84)90075-X","volume":"52","author":"J-C Bermond","year":"1984","unstructured":"Bermond, J.-C., Fouquet, J.L., Habib, M., P\u00e9roche, B.: On linear $$k$$ -arboricity. Discrete Math. 52, 123\u2013132 (1984)","journal-title":"Discrete Math."},{"key":"3_CR4","volume-title":"Online Computation and Competitive Analysis","author":"A Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)"},{"issue":"3","key":"3_CR5","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1002\/net.20366","volume":"55","author":"S Chen","year":"2010","unstructured":"Chen, S., Ljubic, I., Raghavan, S.: The regenerator location problem. Networks, 55(3), 205\u2013220 (2010)","journal-title":"Networks,"},{"issue":"1","key":"3_CR6","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1109\/49.974672","volume":"20","author":"G C\u0103linescu","year":"2002","unstructured":"C\u0103linescu, G., Frieder, O., Wan, P.-J.: Minimizing electronic line terminals for automatic ring protection in general wdm optical networks. IEEE J. Sel. Area Commun. 20(1), 183\u2013189 (2002)","journal-title":"IEEE J. Sel. Area Commun."},{"issue":"4","key":"3_CR7","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1023\/A:1019525904862","volume":"6","author":"G C\u0103linescu","year":"2002","unstructured":"C\u0103linescu, G., Wan, P.-J.: Traffic partition in wdm\/sonet rings to minimize sonet ADMs. J. Comb. Optim. 6(4), 425\u2013453 (2002)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"3_CR8","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1109\/49.974671","volume":"20","author":"T Eilam","year":"2002","unstructured":"Eilam, T., Moran, S., Zaks, S.: Lightpath arrangement in survivable rings to minimize the switching cost. IEEE J. Sel. Area Commun. 20(1), 172\u2013182 (2002)","journal-title":"IEEE J. Sel. Area Commun."},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"Epstein, L., Levin, A.: Better bounds for minimizing SONET ADMs. In: 2nd Workshop on Approximation and Online Algorithms, Bergen, Norway, September 2004","DOI":"10.1007\/978-3-540-31833-0_23"},{"key":"3_CR10","unstructured":"Fedrizzi, R., Galimberti, G.M., Gerstel, O., Martinelli, G., Salvadori, E., Saradhi, C.V., Tanzi, A., Zanardi, A.: Traffic independent heuristics for regenerator site selection for providing any-to-any optical connectivity. In: Proceedings of IEEE\/OSA Conference on Optical Fiber Communications (OFC) (2010)"},{"issue":"2","key":"3_CR11","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1109\/TNET.2010.2068309","volume":"19","author":"M Flammini","year":"2011","unstructured":"Flammini, M., Marchetti-Spaccamela, A., Monaco, G., Moscardelli, L., Zaks, S.: On the complexity of the regenerator placement problem in optical networks. IEEE\/ACM Trans. Networking 19(2), 498\u2013511 (2011)","journal-title":"IEEE\/ACM Trans. Networking"},{"issue":"40\u201342","key":"3_CR12","doi-asserted-by":"publisher","first-page":"3553","DOI":"10.1016\/j.tcs.2010.05.011","volume":"411","author":"M Flammini","year":"2010","unstructured":"Flammini, M., Monaco, G., Moscardelli, L., Shachnai, H., Shalom, M., Tamir, T., Zaks, S.: Minimizing total busy time in parallel scheduling with application to optical networks. Theor. Comput. Sci. 411(40\u201342), 3553\u20133562 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"3_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/11864219_32","volume-title":"Distributed Computing","author":"M Flammini","year":"2006","unstructured":"Flammini, M., Shalom, M., Zaks, S.: On minimizing the number of ADMs in a general topology optical network. In: Dolev, S. (ed.) DISC 2006. LNCS, vol. 4167, pp. 459\u2013473. Springer, Heidelberg (2006)"},{"key":"3_CR14","unstructured":"Gerstel, O., Lin, P., Sasaki, G.: Wavelength assignment in a WDM ring to minimize cost of embedded SONET rings. In: INFOCOM 1998, Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies (1998)"},{"issue":"1","key":"3_CR15","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1049\/ip-com:20010064","volume":"148","author":"SW Kim","year":"2001","unstructured":"Kim, S.W., Seo, S.W.: Regenerator placement algorithms for connection establishment in all-optical networks. IEEE Proc. Commun. 148(1), 25\u201330 (2001)","journal-title":"IEEE Proc. Commun."},{"key":"3_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/3-540-49543-6_19","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"S Leonardi","year":"1998","unstructured":"Leonardi, S., Vitaletti, A.: Randomized lower bounds for online path coloring. In: Rolim, J.D.P., Serna, M., Luby, M. (eds.) RANDOM 1998. LNCS, vol. 1518, pp. 232\u2013247. Springer, Heidelberg (1998)"},{"issue":"6","key":"3_CR17","doi-asserted-by":"publisher","first-page":"1870","DOI":"10.1109\/TNET.2012.2186462","volume":"20","author":"GB Mertzios","year":"2012","unstructured":"Mertzios, G.B., Sau, I., Shalom, M., Zaks, S.: Placing regenerators in optical networks to satisfy multiple sets of requests. IEEE Trans. Networking 20(6), 1870\u20131879 (2012)","journal-title":"IEEE Trans. Networking"},{"key":"3_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1007\/978-3-642-25873-2_2","volume-title":"Principles of Distributed Systems","author":"GB Mertzios","year":"2011","unstructured":"Mertzios, G.B., Shalom, M., Wong, P.W.H., Zaks, S.: Online regenerator placement. In: Fern\u00e0ndez Anta, A., Lipari, G., Roy, M. (eds.) OPODIS 2011. LNCS, vol. 7109, pp. 4\u201317. Springer, Heidelberg (2011)"},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"Pachnicke, S., Paschenda, T., Krummrich, P.M.: Physical impairment based regenerator placement and routing in translucent optical networks. In: Optical Fiber Communication Conference and Exposition and The National Fiber Optic Engineers Conference, p. OWA2. Optical Society of America (2008)","DOI":"10.1109\/OFC.2008.4528659"},{"issue":"2","key":"3_CR20","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.jda.2009.02.006","volume":"8","author":"M Shalom","year":"2010","unstructured":"Shalom, M., Wong, P.W., Zaks, S.: Optimal on-line colorings for minimizing the number of adms in optical networks. J. Discrete Algorithms 8(2), 174\u2013188 (2010)","journal-title":"J. Discrete Algorithms"},{"key":"3_CR21","doi-asserted-by":"crossref","unstructured":"Shalom, M., Zaks, S.: A 10\/7 + $$\\epsilon $$ approximation scheme for minimizing the number of ADMs in SONET rings. In: First Annual International Conference on Broadband Networks, San-Jos\u00e9, California, USA, pp. 254\u2013262, October 2004","DOI":"10.1109\/BROADNETS.2004.1"},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"Sriram, K., Griffith, D., Su, R., Golmie, N.: Static vs. Dynamic Regenerator Assignment in Optical Switches: models and Cost Trade-offs. Workshop on High Performance Switching and Routing (HPSR), pp. 151\u2013155 (2004)","DOI":"10.1109\/HPSR.2004.1303453"},{"issue":"1","key":"3_CR23","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1006\/jctb.1998.1868","volume":"75","author":"C Thomassen","year":"1999","unstructured":"Thomassen, C.: Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5. J. Comb. Theor. Ser. B 75(1), 100\u2013109 (1999)","journal-title":"J. Comb. Theor. Ser. B"},{"key":"3_CR24","unstructured":"Yang, X., Ramamurthy, B.: Dynamic routing in translucent WDM optical networks. In: Proceedings of the IEEE International Conference on Communications (ICC), pp. 955\u2013971 (2002)"},{"issue":"1","key":"3_CR25","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s11107-005-1694-y","volume":"10","author":"X Yang","year":"2005","unstructured":"Yang, X., Ramamurthy, B.: Sparse regeneration in translucent wavelength-routed optical networks: Architecture, network design and wavelength routing. Photonic Netw. Commun. 10(1), 39\u201353 (2005)","journal-title":"Photonic Netw. Commun."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53174-7_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T12:52:52Z","timestamp":1749041572000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53174-7_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662531730","9783662531747"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53174-7_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"5 August 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Garching","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2015","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 June 2015","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2015","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"41","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2015","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}