{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,20]],"date-time":"2025-10-20T09:54:25Z","timestamp":1760954065162},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,4,23]],"date-time":"2018-04-23T00:00:00Z","timestamp":1524441600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2019,2]]},"DOI":"10.1007\/s00224-018-9863-4","type":"journal-article","created":{"date-parts":[[2018,4,23]],"date-time":"2018-04-23T01:50:30Z","timestamp":1524448230000},"page":"306-325","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["On-Line Path Computation and Function Placement in SDNs"],"prefix":"10.1007","volume":"63","author":[{"given":"Guy","family":"Even","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moti","family":"Medina","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boaz","family":"Patt-Shamir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,4,23]]},"reference":[{"issue":"3","key":"9863_CR1","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1145\/258128.258201","volume":"44","author":"J Aspnes","year":"1997","unstructured":"Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., Waarts, O.: On-line routing of virtual circuits with applications to load balancing and machine scheduling. J. ACM) 44(3), 486\u2013504 (1997)","journal-title":"J. ACM)"},{"key":"9863_CR2","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Plotkin, S.: Throughput-competitive on-line routing. In: Proc.34th IEEE Annual Symp. on Foundations of Computer Science, pp. 32\u201340 (1993)","DOI":"10.1109\/SFCS.1993.366884"},{"issue":"3","key":"9863_CR3","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1006\/jcss.1999.1662","volume":"62","author":"B Awerbuch","year":"2001","unstructured":"Awerbuch, B., Azar, Y., Plotkin, S., Waarts, O.: Competitive routing of virtual circuits with unknown duration. J. Comput. Syst. Sci. 62(3), 385\u2013397 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"9863_CR4","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Naor, J.S.: Improved bounds for online routing and packing via a primal-dual approach. In: 47th Ann. IEEE Symp.on Foundations of Computer Science, pp. 293\u2013304 (2006)","DOI":"10.1109\/FOCS.2006.39"},{"issue":"2","key":"9863_CR5","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1287\/moor.1080.0363","volume":"34","author":"N Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.S.: Online primal-dual algorithms for covering and packing. Math. Oper. Res. 34(2), 270\u2013286 (2009)","journal-title":"Math. Oper. Res."},{"key":"9863_CR6","doi-asserted-by":"crossref","unstructured":"Cohen, R., Lewin-Eytan, L., Naor, J. S., Raz, D.: Near optimal placement of virtual network functions. In: 2015 IEEE Conference on Computer Communications (INFOCOM), pp. 1346\u20131354 (2015)","DOI":"10.1109\/INFOCOM.2015.7218511"},{"key":"9863_CR7","doi-asserted-by":"crossref","unstructured":"Even, G., Medina, M.: Online multi-commodity flow with high demands. In: Proc. 10th Int.Workshop on Approximation and Online Algorithms (WAOA), pp 16\u201329 (2012)","DOI":"10.1007\/978-3-642-38016-7_3"},{"key":"9863_CR8","doi-asserted-by":"crossref","unstructured":"Even, G, Medina, M., Patt-Shamir, B.: On-line path computation and function placement in sdns. In: Bonakdarpour, B., Petit, F. (eds.) Stabilization, Safety, and Security of Distributed Systems - 18th International Symposium, SSS 2016, Lyon, France, November 7-10, 2016, Proceedings, volume 10083 of Lecture Notes in Computer Science, pp. 131\u2013147 (2016)","DOI":"10.1007\/978-3-319-49259-9_11"},{"issue":"0","key":"9863_CR9","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1016\/j.tcs.2012.10.036","volume":"496","author":"G Even","year":"2013","unstructured":"Even, G., Medina, M., Schaffrath, G., Schmid, S.: Competitive and deterministic embeddings of virtual networks. Theor. Comput. Sci. 496(0), 184\u2013194 (2013). Distributed Computing and Networking (ICDCN 2012)","journal-title":"Theor. Comput. Sci."},{"key":"9863_CR10","doi-asserted-by":"crossref","unstructured":"Even, G., Rost, M., Schmid, S.: An approximation algorithm for path computation and function placement in sdns. arXiv: 1603.09158\/ 2016 Appeared in SIROCCO (2016)","DOI":"10.1007\/978-3-319-48314-6_24"},{"key":"9863_CR11","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation), 3rd edn. Pearson, Boston (2006)"},{"key":"9863_CR12","unstructured":"Kleinberg, J.M.: Approximation algorithms for disjoint paths problems. PhD thesis Massachusetts Institute of Technology (1996)"},{"issue":"1","key":"9863_CR13","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1109\/JPROC.2014.2371999","volume":"103","author":"D Kreutz","year":"2015","unstructured":"Kreutz, D., Ramos, F., Esteves Verissimo, P., Esteve Rothenberg, C., Azodolmolky, S., Uhlig, S.: Software-defined networking: A comprehensive survey. Proc. IEEE 103(1), 14\u201376 (2015)","journal-title":"Proc. IEEE"},{"issue":"2","key":"9863_CR14","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"key":"9863_CR15","doi-asserted-by":"crossref","unstructured":"Soul\u00e9, R., Basu, S., Kleinberg, R., Sirer, E.G., Foster, N.: Managing the network with merlin. In: Proc. 12th ACM Workshop on Hot Topics in Networks. ACM, p. 24 (2013)","DOI":"10.1145\/2535771.2535792"},{"key":"9863_CR16","doi-asserted-by":"crossref","unstructured":"Soul\u00e9, R., Basu, S., Marandi, P.J., Pedone, F., Kleinberg, R., Sirer, E.G., Foster, N.: Merlin: A language for provisioning network resources. In: Proc. 10th ACM Int. Conf. on emerging Networking Experiments and Technologies. ACM, pp. 213\u2013226 (2014)","DOI":"10.1145\/2674005.2674989"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9863-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-018-9863-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9863-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,16]],"date-time":"2019-10-16T16:49:32Z","timestamp":1571244572000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-018-9863-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,23]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,2]]}},"alternative-id":["9863"],"URL":"https:\/\/doi.org\/10.1007\/s00224-018-9863-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4,23]]},"assertion":[{"value":"23 April 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}