{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T01:09:29Z","timestamp":1776215369008,"version":"3.50.1"},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,2,20]],"date-time":"2019-02-20T00:00:00Z","timestamp":1550620800000},"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":["SIGCOMM Comput. Commun. Rev."],"published-print":{"date-parts":[[2019,2,20]]},"abstract":"<jats:p>This paper makes the case for a parametrized complexity approach to tackle the fundamental but notoriously hard Virtual Network Embedding Problem. In particular, we show that the structure of the to-be-embedded virtual network requests can be exploited toward fast (i.e.,fixed-parameter tractable) approximation algorithms, using dynamic as well as linear programming algorithms.<\/jats:p>\n          <jats:p>Our approach does provide formal guarantees on the runtime and solution quality and can safeguard also latency constraints. Using extensive computational experiments we demonstrate the practical relevance of our novel approach.<\/jats:p>","DOI":"10.1145\/3314212.3314214","type":"journal-article","created":{"date-parts":[[2019,2,22]],"date-time":"2019-02-22T17:01:44Z","timestamp":1550854904000},"page":"3-10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Parametrized complexity of virtual network embeddings"],"prefix":"10.1145","volume":"49","author":[{"given":"Matthias","family":"Rost","sequence":"first","affiliation":[{"name":"TU Berlin, Germany"}]},{"given":"Elias","family":"D\u00f6hne","sequence":"additional","affiliation":[{"name":"TU Berlin, Germany"}]},{"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[{"name":"University of Vienna, Austria"}]}],"member":"320","published-online":{"date-parts":[[2019,2,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043164.2018465"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2011.2159308"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-48314-6_24"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"A. Fischer J.F. Botero M. Till Beck H. de Meer and X. Hesselbach. 2013. Virtual Network Embedding: A Survey. Comm. Surveys Tutorials IEEE 15 4 (2013).  A. Fischer J.F. Botero M. Till Beck H. de Meer and X. Hesselbach. 2013. Virtual Network Embedding: A Survey. Comm. Surveys Tutorials IEEE 15 4 (2013).","DOI":"10.1109\/SURV.2013.013013.00155"},{"key":"e_1_2_1_6_1","volume-title":"Parameterized complexity theory","author":"Flum J\u00f6rg","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized complexity theory . Springer . J\u00f6rg Flum and Martin Grohe. 2006. Parameterized complexity theory. Springer."},{"key":"e_1_2_1_7_1","volume-title":"Geometric algorithms and combinatorial optimization","author":"Gr\u00f6tschel Martin","unstructured":"Martin Gr\u00f6tschel , L\u00e1szl\u00f3 Lov\u00e1sz , and Alexander Schrijver . 1988. Geometric algorithms and combinatorial optimization . Springer-Verlag Berlin Heidelberg . Martin Gr\u00f6tschel, L\u00e1szl\u00f3 Lov\u00e1sz, and Alexander Schrijver. 1988. Geometric algorithms and combinatorial optimization. Springer-Verlag Berlin Heidelberg."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSM.2016.2598420"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(01)00069-4"},{"key":"e_1_2_1_10_1","volume-title":"Proc. IFIP Networking","author":"Rost Matthias","year":"2018","unstructured":"Matthias Rost and Stefan Schmid . 2018 . NP-Completeness and Inapproximability of the Virtual Network Embedding Problem and Its Variants . In Proc. IFIP Networking 2018. Matthias Rost and Stefan Schmid. 2018. NP-Completeness and Inapproximability of the Virtual Network Embedding Problem and Its Variants. In Proc. IFIP Networking 2018."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.23919\/IFIPNetworking.2018.8696623"},{"key":"e_1_2_1_12_1","volume-title":"Proc. 25th Annual European Symposium on Algorithms (ESA).","author":"Tamaki Hisao","year":"2017","unstructured":"Hisao Tamaki . 2017 . Positive-Instance Driven Dynamic Programming for Treewidth . In Proc. 25th Annual European Symposium on Algorithms (ESA). Hisao Tamaki. 2017. Positive-Instance Driven Dynamic Programming for Treewidth. In Proc. 25th Annual European Symposium on Algorithms (ESA)."},{"key":"e_1_2_1_13_1","volume-title":"Proc. IFIP\/IEEE International Symposium on Integrated Network Management.","author":"Zhani M. F.","unstructured":"M. F. Zhani , Q. Zhang , G. Simona , and R. Boutaba . 2013. VDC Planner: Dynamic migration-aware Virtual Data Center embedding for clouds . In Proc. IFIP\/IEEE International Symposium on Integrated Network Management. M. F. Zhani, Q. Zhang, G. Simona, and R. Boutaba. 2013. VDC Planner: Dynamic migration-aware Virtual Data Center embedding for clouds. In Proc. IFIP\/IEEE International Symposium on Integrated Network Management."}],"container-title":["ACM SIGCOMM Computer Communication Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3314212.3314214","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3314212.3314214","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:22Z","timestamp":1750204402000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3314212.3314214"}},"subtitle":["dynamic &amp; linear programming approximations"],"short-title":[],"issued":{"date-parts":[[2019,2,20]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,2,20]]}},"alternative-id":["10.1145\/3314212.3314214"],"URL":"https:\/\/doi.org\/10.1145\/3314212.3314214","relation":{},"ISSN":["0146-4833"],"issn-type":[{"value":"0146-4833","type":"print"}],"subject":[],"published":{"date-parts":[[2019,2,20]]},"assertion":[{"value":"2019-02-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}