{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T16:13:26Z","timestamp":1778256806139,"version":"3.51.4"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030197582","type":"print"},{"value":"9783030197599","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-19759-9_6","type":"book-chapter","created":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T07:47:10Z","timestamp":1556351230000},"page":"73-101","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Multi-commodity Flow with In-Network Processing"],"prefix":"10.1007","author":[{"given":"Moses","family":"Charikar","sequence":"first","affiliation":[]},{"given":"Yonatan","family":"Naamad","sequence":"additional","affiliation":[]},{"given":"Jenifer","family":"Rexford","sequence":"additional","affiliation":[]},{"given":"X. Kelvin","family":"Zou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,4,28]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"Anwer, B., Benson, T., Feamster, N., Levin, D.: Programming Slick network functions. In: Proceedings of Symposium on SDN Research, June 2015","DOI":"10.1145\/2774993.2774998"},{"issue":"1","key":"6_CR2","doi-asserted-by":"publisher","first-page":"121","DOI":"10.4086\/toc.2012.v008a006","volume":"8","author":"S Arora","year":"2012","unstructured":"Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a meta-algorithm and applications. Theor. Comput. 8(1), 121\u2013164 (2012)","journal-title":"Theor. Comput."},{"key":"6_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/3-540-48523-6_17","volume-title":"Automata, Languages and Programming","author":"P Berman","year":"1999","unstructured":"Berman, P., Karpinski, M.: On some tighter inapproximability results (extended abstract). In: Wiedermann, J., van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 200\u2013209. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-48523-6_17"},{"key":"6_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/978-3-642-40328-6_6","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"D Chakrabarty","year":"2013","unstructured":"Chakrabarty, D., Krishnaswamy, R., Li, S., Narayanan, S.: Capacitated network design on undirected graphs. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) APPROX\/RANDOM -2013. LNCS, vol. 8096, pp. 71\u201380. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40328-6_6"},{"key":"6_CR5","unstructured":"Chiosi, M., et al.: Network functions virtualisation: introductory white paper. In: SDN and OpenFlow World Congress, October 2012"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Cohen, R., Lewin-Eytan, L., Naor, J.S., Raz, D.: Near optimal placement of virtual network functions. In: IEEE Conference on Computer Communications (INFOCOM), pp. 1346\u20131354. IEEE (2015)","DOI":"10.1109\/INFOCOM.2015.7218511"},{"key":"6_CR7","doi-asserted-by":"publisher","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162, 439\u2013485 (2005)","journal-title":"Ann. Math."},{"key":"6_CR8","doi-asserted-by":"publisher","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Proceedings of the Annual ACM Symposium on Theory of Computing, pp. 624\u2013633. ACM, New York (2014). https:\/\/doi.org\/10.1145\/2591796.2591884 . http:\/\/doi.acm.org\/10.1145\/2591796.2591884","DOI":"10.1145\/2591796.2591884"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Even, G., Medina, M., Patt-Shamir, B.: Competitive path computation and function placement in SDNs. arXiv preprint arXiv:1602.06169 (2016)","DOI":"10.1007\/978-3-319-49259-9_11"},{"key":"6_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/978-3-319-48314-6_24","volume-title":"Structural Information and Communication Complexity","author":"G Even","year":"2016","unstructured":"Even, G., Rost, M., Schmid, S.: An approximation algorithm for path computation and function placement in SDNs. In: Suomela, J. (ed.) SIROCCO 2016. LNCS, vol. 9988, pp. 374\u2013390. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-48314-6_24"},{"key":"6_CR11","unstructured":"Fayazbakhsh, S.K., Chiang, L., Sekar, V., Yu, M., Mogul, J.C.: Enforcing network-wide policies in the presence of dynamic middlebox actions using flowtags. In: 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI 2014), pp. 543\u2013546. USENIX Association, Seattle, April 2014. https:\/\/www.usenix.org\/conference\/nsdi14\/technical-sessions\/presentation\/fayazbakhsh"},{"issue":"4","key":"6_CR12","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM (JACM) 45(4), 634\u2013652 (1998)","journal-title":"J. ACM (JACM)"},{"key":"6_CR13","unstructured":"Forrest, J.: Clp: Coin-or linear program solver. In: DIMACS Workshop on COIN-OR, pp. 17\u201320, July 2006"},{"key":"6_CR14","doi-asserted-by":"publisher","unstructured":"Gember-Jacobson, A., et al.: OpenNF: enabling innovation in network function control. In: Proceedings of the ACM Conference on SIGCOMM, pp. 163\u2013174. ACM (2014). https:\/\/doi.org\/10.1145\/2619239.2626313 . http:\/\/doi.acm.org\/10.1145\/2619239.2626313","DOI":"10.1145\/2619239.2626313"},{"key":"6_CR15","unstructured":"Heorhiadi, V., Reiter, M.K., Sekar, V.: Accelerating the development of software-defined network optimization applications using SOL. arXiv preprint arXiv:1504.07704 (2015)"},{"key":"6_CR16","unstructured":"Heorhiadi, V., Reiter, M.K., Sekar, V.: Simplifying software-defined network optimization using sol. In: 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 2016), pp. 223\u2013237. USENIX Association, Santa Clara, March 2016. https:\/\/www.usenix.org\/conference\/nsdi16\/technical-sessions\/presentation\/heorhiadi"},{"key":"6_CR17","doi-asserted-by":"publisher","unstructured":"Jin, Y., Wen, Y., Westphal, C.: Towards joint resource allocation and routing to optimize video distribution over future internet. In: IFIP Networking Conference (IFIP Networking) 2015, 1\u20139 May 2015. https:\/\/doi.org\/10.1109\/IFIPNetworking.2015.7145311","DOI":"10.1109\/IFIPNetworking.2015.7145311"},{"issue":"3","key":"6_CR18","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2- $$\\varepsilon $$ . J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR19","doi-asserted-by":"publisher","unstructured":"Li, X., Qian, C.: A survey of network function placement. In: 13th IEEE Annual Consumer Communications Networking Conference (CCNC), pp. 948\u2013953, January 2016. https:\/\/doi.org\/10.1109\/CCNC.2016.7444915","DOI":"10.1109\/CCNC.2016.7444915"},{"key":"6_CR20","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.jpdc.2018.06.006","volume":"120","author":"T Lukovszki","year":"2018","unstructured":"Lukovszki, T., Rost, M., Schmid, S.: Approximate and incremental network function placement. J. Parallel Distrib. Comput. 120, 159\u2013169 (2018)","journal-title":"J. Parallel Distrib. Comput."},{"key":"6_CR21","unstructured":"Martins, J., et al.: Clickos and the art of network function virtualization. In: 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI 2014), pp. 459\u2013473. USENIX Association, April 2014. https:\/\/www.usenix.org\/conference\/nsdi14\/technical-sessions\/presentation\/martins"},{"key":"6_CR22","unstructured":"OPNFV: OPNFV: an open platform to accelerate NFV, Linux Foundation. https:\/\/www.opnfv.org\/"},{"issue":"3","key":"6_CR23","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1002\/net.20371","volume":"55","author":"S Orlowski","year":"2010","unstructured":"Orlowski, S., Wess\u00e4ly, R., Pi\u00f3ro, M., Tomaszewski, A.: Sndlib 1.0\u2014survivable network design library. Networks 55(3), 276\u2013286 (2010)","journal-title":"Networks"},{"key":"6_CR24","doi-asserted-by":"publisher","unstructured":"Qazi, Z.A., Tu, C.C., Chiang, L., Miao, R., Sekar, V., Yu, M.: SIMPLE-fying middlebox policy enforcement using SDN. In: Proceedings of ACM SIGCOMM, pp. 27\u201338. ACM (2013). https:\/\/doi.org\/10.1145\/2486001.2486022 . http:\/\/doi.acm.org\/10.1145\/2486001.2486022","DOI":"10.1145\/2486001.2486022"},{"key":"6_CR25","unstructured":"Rajagopalan, S., Williams, D., Jamjoom, H., Warfield, A.: Split\/merge: system support for elastic execution in virtual middleboxes. In: Presented as Part of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 2013), pp. 227\u2013240. USENIX, Lombard (2013). https:\/\/www.usenix.org\/conference\/nsdi13\/technical-sessions\/presentation\/rajagopalan"},{"key":"6_CR26","doi-asserted-by":"crossref","unstructured":"Rost, M., Schmid, S.: Charting the complexity landscape of virtual network embeddings. In: IFIP Networking, May 2018. http:\/\/eprints.cs.univie.ac.at\/5580\/","DOI":"10.23919\/IFIPNetworking.2018.8696604"},{"key":"6_CR27","doi-asserted-by":"crossref","unstructured":"Rost, M., Schmid, S.: Virtual network embedding approximations: leveraging randomized rounding. In: IFIP Networking, May 2018. http:\/\/eprints.cs.univie.ac.at\/5579\/","DOI":"10.23919\/IFIPNetworking.2018.8696623"},{"key":"6_CR28","unstructured":"Sekar, V., Egi, N., Ratnasamy, S., Reiter, M.K., Shi, G.: Design and implementation of a consolidated middlebox architecture. In: Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation, NSDI 2012, p. 24. USENIX Association (2012). http:\/\/dl.acm.org\/citation.cfm?id=2228298.2228331"},{"key":"6_CR29","doi-asserted-by":"publisher","unstructured":"Sherry, J., Hasan, S., Scott, C., Krishnamurthy, A., Ratnasamy, S., Sekar, V.: Making middleboxes someone else\u2019s problem: network processing as a cloud service. In: Proceedings of the ACM SIGCOMM 2012 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, SIGCOMM 2012, pp. 13\u201324. ACM (2012). https:\/\/doi.org\/10.1145\/2342356.2342359 . http:\/\/doi.acm.org\/10.1145\/2342356.2342359","DOI":"10.1145\/2342356.2342359"},{"issue":"1","key":"6_CR30","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"M Sviridenko","year":"2004","unstructured":"Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32(1), 41\u201343 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"6_CR31","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1145\/1111322.1111341","volume":"36","author":"S Uhlig","year":"2006","unstructured":"Uhlig, S., Quoitin, B., Lepropre, J., Balon, S.: Providing public intradomain traffic matrices to the research community. ACM SIGCOMM Comput. Commun. Rev. 36(1), 83\u201386 (2006)","journal-title":"ACM SIGCOMM Comput. Commun. Rev."}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects of Cloud Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-19759-9_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,16]],"date-time":"2023-09-16T03:32:22Z","timestamp":1694835142000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-19759-9_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030197582","9783030197599"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-19759-9_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"28 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ALGOCLOUD","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Algorithmic Aspects of Cloud Computing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Helsinki","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Finland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 August 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 August 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"algocloud2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/algo2018.hiit.fi\/algocloud\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}