{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T19:57:26Z","timestamp":1725479846839},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642366932"},{"type":"electronic","value":"9783642366949"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-36694-9_5","type":"book-chapter","created":{"date-parts":[[2013,3,11]],"date-time":"2013-03-11T10:08:39Z","timestamp":1362996519000},"page":"49-61","source":"Crossref","is-referenced-by-count":6,"title":["Content Placement via the Exponential Potential Function Method"],"prefix":"10.1007","author":[{"given":"David","family":"Applegate","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aaron","family":"Archer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vijay","family":"Gopalakrishnan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seungjoon","family":"Lee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K. K.","family":"Ramakrishnan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"Applegate, D., Archer, A., Gopalakrishnan, V., Lee, S., Ramakrishnan, K.K.: Optimal content placement for a large-scale VoD system. In: CoNEXT, pp. 4:1\u20134:12 (2010)","DOI":"10.1145\/1921168.1921174"},{"key":"5_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.\u00a08, 121\u2013164 (2012)","journal-title":"Theor. Comput."},{"key":"5_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/11561071_6","volume-title":"Algorithms \u2013 ESA 2005","author":"G. Batra","year":"2005","unstructured":"Batra, G., Garg, N., Gupta, G.: Heuristic Improvements for Computing Maximum Multicommodity Flow and Minimum Multicut. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 35\u201346. Springer, Heidelberg (2005)"},{"key":"5_CR4","volume-title":"Potential Function Methods for Approximately Solving Linear Programming Problems: Theory and Practice","author":"D. Bienstock","year":"2002","unstructured":"Bienstock, D.: Potential Function Methods for Approximately Solving Linear Programming Problems: Theory and Practice. Kluwer, Boston (2002)"},{"key":"5_CR5","unstructured":"Bienstock, D.: Personal communication (2011)"},{"issue":"4","key":"5_CR6","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1137\/S0097539705447293","volume":"35","author":"D. Bienstock","year":"2006","unstructured":"Bienstock, D., Iyengar, G.: Approximating fractional packings and coverings in O(1\/\u03b5) iterations. SIAM J. Comput.\u00a035(4), 825\u2013854 (2006)","journal-title":"SIAM J. Comput."},{"key":"5_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-13036-6_1","volume-title":"Integer Programming and Combinatorial Optimization","author":"D. Bienstock","year":"2010","unstructured":"Bienstock, D., Zuckerberg, M.: Solving LP Relaxations of Large-Scale Precedence Constrained Problems. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol.\u00a06080, pp. 1\u201314. Springer, Heidelberg (2010)"},{"key":"5_CR8","doi-asserted-by":"crossref","unstructured":"Borger, J.M., Kang, T.S., Klein, P.N.: Approximating concurrent flow with unit demands and capacities: an implementation. In: Johnson, D.S., McGeoch, C.C. (eds.) Network Flows and Matching: First DIMACS Implementation Challenge, pp. 371\u2013386. American Mathematical Society (1993)","DOI":"10.1090\/dimacs\/012\/14"},{"issue":"4","key":"5_CR9","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1137\/S0097539701398594","volume":"34","author":"M. Charikar","year":"2005","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location problems. SIAM J. Comput.\u00a034(4), 803\u2013824 (2005)","journal-title":"SIAM J. Comput."},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"Duffield, N.G., Lund, C., Thorup, M.: Priority sampling for estimation of arbitrary subset sums. J. ACM 54(6) (2007)","DOI":"10.1145\/1314690.1314696"},{"issue":"4","key":"5_CR11","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/S0895480199355754","volume":"13","author":"L. Fleischer","year":"2000","unstructured":"Fleischer, L.: Approximating fractional multicommodity flow independent of the number of commodities. SIAM J. Discrete Math.\u00a013(4), 505\u2013520 (2000)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"5_CR12","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1002\/net.3230030202","volume":"3","author":"L. Fratta","year":"1973","unstructured":"Fratta, L., Gerla, M., Kleinrock, L.: The flow deviation method: An approach to store-and-forward communication network design. Networks\u00a03(2), 97\u2013133 (1973)","journal-title":"Networks"},{"issue":"2","key":"5_CR13","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1137\/S0097539704446232","volume":"37","author":"N. Garg","year":"2007","unstructured":"Garg, N., K\u00f6nemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput.\u00a037(2), 630\u2013652 (2007)","journal-title":"SIAM J. Comput."},{"key":"5_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1007\/3-540-69346-7_26","volume-title":"Integer Programming and Combinatorial Optimization","author":"A.V. Goldberg","year":"1998","unstructured":"Goldberg, A.V., Oldham, J.D., Plotkin, S., Stein, C.: An Implementation of a Combinatorial Approximation Algorithm for Minimum-Cost Multicommodity Flow. In: Bixby, R.E., Boyd, E.A., R\u00edos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol.\u00a01412, pp. 338\u2013352. Springer, Heidelberg (1998)"},{"key":"5_CR15","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1016\/j.ejor.2011.09.017","volume":"218","author":"J. Gondzio","year":"2012","unstructured":"Gondzio, J.: Interior point methods 25 years later. Eur. J. Oper. Res.\u00a0218, 587\u2013601 (2012)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"5_CR16","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1137\/0804004","volume":"4","author":"M.D. Grigoriadis","year":"1994","unstructured":"Grigoriadis, M.D., Khachiyan, L.G.: Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM J. Optimiz.\u00a04(1), 86\u2013107 (1994)","journal-title":"SIAM J. Optimiz."},{"key":"5_CR17","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.3230260202","volume":"26","author":"M.D. Grigoriadis","year":"1995","unstructured":"Grigoriadis, M.D., Khachiyan, L.G.: An exponential-function reduction method for block-angular convex programs. Networks\u00a026, 59\u201368 (1995)","journal-title":"Networks"},{"key":"5_CR18","unstructured":"Jang, Y.: Development and implementation of heuristic algorithms for multicommodity flow problems. PhD thesis, Columbia University (1996)"},{"key":"5_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/3-540-48777-8_24","volume-title":"Integer Programming and Combinatorial Optimization","author":"P.N. Klein","year":"1999","unstructured":"Klein, P.N., Young, N.: On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms. In: Cornu\u00e9jols, G., Burkard, R.E., Woeginger, G.J. (eds.) IPCO 1999. LNCS, vol.\u00a01610, pp. 320\u2013327. Springer, Heidelberg (1999)"},{"key":"5_CR20","doi-asserted-by":"crossref","unstructured":"Koufogiannakis, C., Young, N.E.: Beating simplex for fractional packing and covering linear programs. In: FOCS, pp. 494\u2013504 (2007)","DOI":"10.1109\/FOCS.2007.62"},{"key":"5_CR21","doi-asserted-by":"crossref","unstructured":"Leong, T., Shor, P., Stein, C.: Implementation of a combinatorial multicommodity flow algorithm. In: Johnson, D.S., McGeoch, C.C. (eds.) Network Flows and Matching: First DIMACS Implementation Challenge, pp. 387\u2013406. American Mathematical Society (1993)","DOI":"10.1090\/dimacs\/012\/15"},{"key":"5_CR22","doi-asserted-by":"crossref","unstructured":"M\u0105dry, A.: Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. In: STOC, pp. 121\u2013130 (2010)","DOI":"10.1145\/1806689.1806708"},{"key":"5_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s12532-011-0023-y","volume":"3","author":"D. M\u00fcller","year":"2011","unstructured":"M\u00fcller, D., Radke, K., Vygen, J.: Faster min-max resource sharing in theory and practice. Math. Program. Comput.\u00a03, 1\u201335 (2011)","journal-title":"Math. Program. Comput."},{"key":"5_CR24","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s10107-004-0552-5","volume":"103","author":"Y. Nesterov","year":"2005","unstructured":"Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. Ser. A\u00a0103, 127\u2013152 (2005)","journal-title":"Math. Program. Ser. A"},{"key":"5_CR25","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"S.A. Plotkin","year":"1995","unstructured":"Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9.: Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res.\u00a020, 257\u2013301 (1995)","journal-title":"Math. Oper. Res."},{"key":"5_CR26","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0025-5610(96)00072-X","volume":"77","author":"T. Radzik","year":"1997","unstructured":"Radzik, T.: Fast deterministic approximation for the multicommodity flow problem. Math. Program.\u00a077, 43\u201358 (1997)","journal-title":"Math. Program."},{"key":"5_CR27","unstructured":"Radzik, T.: Experimental study of a solution method for the multicommodity flow problem. In: ALENEX 2000, pp. 79\u2013102 (2000)"},{"issue":"2","key":"5_CR28","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1145\/77600.77620","volume":"37","author":"F. Shahrokhi","year":"1990","unstructured":"Shahrokhi, F., Matula, D.W.: The maximum concurrent flow problem. J. ACM\u00a037(2), 318\u2013334 (1990)","journal-title":"J. ACM"},{"key":"5_CR29","doi-asserted-by":"crossref","unstructured":"Spring, N., Mahajan, R., Wetherall, D.: Measuring ISP topologies with Rocketfuel. In: SIGCOMM, pp. 133\u2013145 (2002)","DOI":"10.1145\/633025.633039"},{"key":"5_CR30","doi-asserted-by":"crossref","unstructured":"Szegedy, M.: The DLT priority sampling is essentially optimal. In: STOC, pp. 150\u2013158 (2006)","DOI":"10.1145\/1132516.1132539"},{"key":"5_CR31","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Confidence intervals for priority sampling. In: SIGMETRICS, pp. 252\u2013263 (2006)","DOI":"10.1145\/1140277.1140307"},{"key":"5_CR32","unstructured":"Wunderling, R.: The kernel simplex method. Talk at ISMP (August 2012)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-36694-9_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,20]],"date-time":"2019-01-20T12:46:47Z","timestamp":1547988407000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-36694-9_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642366932","9783642366949"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36694-9_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}