{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:37:48Z","timestamp":1787341068459,"version":"build-2736575974"},"reference-count":27,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>We study a basic resource allocation problem that arises in cloud computing environments. The physical network of the cloud is represented as a graph with vertices representing servers and edges corresponding to communication links. A workload is a set of processes with processing requirements and mutual communication requirements. The workloads arrive and depart over time, and the resource allocator must map each workload upon arrival to the physical network. We consider the objective of minimizing the congestion. We show that solving a subproblem (\\sf SingleMap) about mapping a single workload to the physical graph essentially suffices for solving the general problem. In particular, an $\\alpha$-approximation algorithm for \\sf SingleMap gives an $O(\\alpha \\log nD)$ competitive algorithm for the general problem, where $n$ is the number of nodes in the physical network and $D$ is the maximum to minimum workload duration ratio. We then consider the \\sf SingleMap problem for two natural classes of workloads, namely depth-$d$ trees and complete-graph workloads. For depth-$d$ trees, we give an $n^{O(d)}$ time $O(d^2 \\log (nd))$-approximation algorithm based on a strong LP relaxation inspired by the Sherali--Adams hierarchy. For complete graphs, we give a polylogarithmic approximation algorithm using R\u00e4cke decompositions.<\/jats:p>","DOI":"10.1137\/110845239","type":"journal-article","created":{"date-parts":[[2015,6,18]],"date-time":"2015-06-18T14:19:51Z","timestamp":1434637191000},"page":"819-843","source":"Crossref","is-referenced-by-count":9,"title":["Minimum Congestion Mapping in a Cloud"],"prefix":"10.1137","volume":"44","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kang-Won","family":"Lee","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Murtaza","family":"Zafer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,6,18]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/016\/02"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"N. Alon and J. H. Spencer,\n                      The Probabilistic Method\n                      , Wiley, New York, 2008.","DOI":"10.1002\/9780470277331"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/258128.258201"},{"key":"atypb5","first-page":"119","author":"Azar Y.","year":"1993","journal-title":"Montreal"},{"key":"atypb6","first-page":"17","author":"Bansal N.","year":"2011","journal-title":"Palm Springs"},{"key":"atypb7","first-page":"267","author":"Bansal N.","year":"2011","journal-title":"San Jose"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1070"},{"key":"atypb9","unstructured":"A. Borodin and R. El-Yaniv,\n                      Online Computation and Competitive Analysis\n                      , Cambridge University Press, Cambridge, UK, 1998."},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"E. Cela,\n                      The Quadratic Assignment Problem: Theory and Algorithms\n                      , Springer, New York, 1998.","DOI":"10.1007\/978-1-4757-2787-6"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"N. Chowdhury, M. Rahman, and R. Boutaba,\n                      Virtual network embedding with coordinated node and link mapping\n                      , in Proceedings of the 28th IEEE Conference on Computer Communications (INFOCOM), 2009, pp. 783-791.","DOI":"10.1109\/INFCOM.2009.5061987"},{"key":"atypb12","first-page":"233","author":"Chuzhoy J.","year":"2012","journal-title":"NJ"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver,\n                      Combinatorial Optimization\n                      , John Wiley and Sons, New York, 1998.","DOI":"10.1002\/9781118033142"},{"key":"atypb14","first-page":"16","author":"Golovin D.","year":"2006","journal-title":"Denver"},{"key":"atypb15","first-page":"34","author":"Harrelson C.","year":"2003","journal-title":"San Diego"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1145\/1644015.1644033"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"atypb18","first-page":"594","author":"Makarychev K.","year":"2010","journal-title":"Bordeaux"},{"key":"atypb19","first-page":"1154","author":"Meng X.","year":"2010","journal-title":"San Diego"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0418"},{"key":"atypb21","first-page":"43","author":"R\u00e4cke H.","year":"2002","journal-title":"Vancouver"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"atypb23","first-page":"755","author":"Raghavendra P.","year":"2010","journal-title":"MA"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"P. Raghavendra, D. Steurer, and M. Tulsiani,\n                      Reductions between expansion problems\n                      , in Proceedings of the 27th Conference on Computational Complexity (CCC), 2012, pp. 64-73.","DOI":"10.1109\/CCC.2012.43"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1145\/1355734.1355737"},{"key":"atypb27","first-page":"1","author":"Zhu Y.","year":"2006","journal-title":"Barcelona"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110845239","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:04:13Z","timestamp":1787339053000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110845239"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/110845239"],"URL":"https:\/\/doi.org\/10.1137\/110845239","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}