{"id":932,"date":"2010-01-31T06:38:34","date_gmt":"2010-01-31T14:38:34","guid":{"rendered":"http:\/\/obliviousrounding.com\/blog\/?p=932"},"modified":"2026-09-30T09:14:33","modified_gmt":"2026-09-30T17:14:33","slug":"lagrangian-relaxation-example","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/lagrangian-relaxation-example\/","title":{"rendered":"Lagrangian relaxation \/ example"},"content":{"rendered":"<div class=\"latex-file\">\n<div class=\"latex-document\">\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<blockquote class=\"quote\"><p><center><em>A simple example of a Lagrangian-relaxation algorithm.<\/em><\/center><\/p><\/blockquote>\n<p>  The algorithm is for Maximum Multicommodity Flow. It illustrates some prototypical aspects of Lagrangian relaxation.<!--more--><\/p>\n<p><div style=\"margin:0pt;padding:0pt;margin-bottom:12px\"><\/div>\n<\/p>\n<hr \/>\n<div class=\"expandable\" id=\"a0000000002\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for background material\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for background material\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<ul class=\"itemize\">\n<li>\n<p>the Maximum Multicommodity Flow problem. The input is a graph <script type=\"math\/tex;\">G=(V,E)<\/script>, a capacity <script type=\"math\/tex;\">c_e\\gt 0<\/script> for each edge <script type=\"math\/tex;\">e<\/script>, and a collection <script type=\"math\/tex;\">P<\/script> of paths in <script type=\"math\/tex;\">G<\/script>. The goal is to assign a non-negative flow value <script type=\"math\/tex;\">f_p<\/script> to each path <script type=\"math\/tex;\">p\\in P<\/script> so as to maximize the total flow assigned, subject to the constraint that no edge has more flow (on the paths going through the edge) than the capacity of the edge. <\/p>\n<p>We let <script type=\"math\/tex;\">f(e)<\/script> denote <script type=\"math\/tex;\">\\sum _{p\\ni e} f_p<\/script>, the flow <script type=\"math\/tex;\">f<\/script> sends along edge <script type=\"math\/tex;\">e<\/script>. <\/p>\n<p>The flow is <em>integer<\/em> if each <script type=\"math\/tex;\">f_p<\/script> is an integer. <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/details>\n<\/div>\n<hr \/>\n<\/p>\n<\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000003\">Algorithm<\/h1>\n<p> To ease presentation, assume that each edge capacity is at least 1. (If not, divide all edge capacities by the minimum edge capacity before running the algorithm.) The algorithm finds a near-maximum multicommodity flow. <\/p>\n<table id=\"a0000000004\" class=\"latex-alg\" cellspacing=\"0\" cellpadding=\"4\" width=\"100%\" style=\"border-top:1px solid #CCC;border-bottom:1px solid #CCC;margin-top:2ex;margin-bottom:2ex;\">\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">&nbsp;<\/td>\n<td style=\"padding-left:0em\"><b style=\"font-size:90%\">input:<\/b> graph <script type=\"math\/tex;\">G=(V,E)<\/script> with edge capacities; collection <script type=\"math\/tex;\">P<\/script> of paths in <script type=\"math\/tex;\">G<\/script><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">&nbsp;<\/td>\n<td style=\"padding-left:0em\"><b style=\"font-size:90%\">output:<\/b> multicommodity flow <script type=\"math\/tex;\">f<\/script><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">1.<\/td>\n<td style=\"padding-left:0em\"> Let <script type=\"math\/tex;\">f_p \\leftarrow 0<\/script> for each <script type=\"math\/tex;\">p\\in P<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">2.<\/td>\n<td style=\"padding-left:0em\"> Repeat until some edge <script type=\"math\/tex;\">e<\/script> has at least <script type=\"math\/tex;\">c_e \\ln (m)\/\\varepsilon <\/script> units of flow through it. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:1em\"> Send <script type=\"math\/tex;\">\\varepsilon <\/script> units of flow along a path <script type=\"math\/tex;\">p<\/script>, where <script type=\"math\/tex;\">p\\in P<\/script> minimizes <script type=\"math\/tex;\">\\sum _{e\\in p} \\exp (f(e)\/c_e)\/c_e<\/script>. <br \/>(Typically a shortest-path algorithm is used to find <script type=\"math\/tex;\">p<\/script>.) <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">4.<\/td>\n<td style=\"padding-left:0em\"> Let <script type=\"math\/tex;\">\\alpha \\leftarrow \\max _{e\\in E} f(e) \/ c_e<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">5.<\/td>\n<td style=\"padding-left:0em\"> Return <script type=\"math\/tex;\">f'<\/script> where <script type=\"math\/tex;\">f'_p = f_p \/ \\alpha <\/script> for <script type=\"math\/tex;\">p\\in P<\/script>. <\/p>\n<div style=\"float:right;display:inline-block\"><em>&#8230;Scale <script type=\"math\/tex;\">f<\/script> to make it feasible.<\/em><\/div>\n<\/td>\n<\/tr>\n<\/table>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000005\">Performance guarantee<\/h1>\n<p> In the 1990s, the following approximation guarantee was proved for algorithms similar to this one: <\/p>\n<div id=\"a0000000006\" class=\"my-theorem latex-paragraph latex-thm\">\n<div class=\"latex-paragraph-heading\">   <b>Theorem <\/b> (e.g.\u00a0<span class=\"cite\">[<a href=\"#Shahrokhi90Maximum\">5<\/a>, <a href=\"#Grigoriadis94Fast\">2<\/a>, <a href=\"#Klein94Faster\">3<\/a>, <a href=\"#Plotkin95Fast\">4<\/a>, <a href=\"#Young95Randomized\">6<\/a>, <a href=\"#Garg98Faster\">1<\/a>]<\/span>).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> The algorithm above returns a flow <script type=\"math\/tex;\">f<\/script> of size at least <script type=\"math\/tex;\">1-O(\\varepsilon )<\/script> times maximum. <\/p>\n<\/div><\/div>\n<div class=\"expandable\" id=\"a0000000007\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for proof sketch\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for proof sketch\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p>The maximum edge congestion (i.e., <script type=\"math\/tex;\">\\max _e\\,  x(e)\/c_e<\/script>) is at most <\/p>\n<div id=\"a0000000008\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\Phi (f) = \\ln \\sum _e \\exp (f(e)\/c_e). <\/script><\/div>\n<p> Let <script type=\"math\/tex;\">\\psi _e<\/script> denote <script type=\"math\/tex;\">\\exp (f(e)\/c_e)<\/script>. In an iteration where the algorithm sends <script type=\"math\/tex;\">\\varepsilon <\/script> units of flow along a path <script type=\"math\/tex;\">p<\/script>, the increase in <script type=\"math\/tex;\">\\Phi <\/script> is at most <\/p>\n<div id=\"eq:1\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation}  (1+O(\\varepsilon )) \\varepsilon \\frac{\\sum _{e\\in p} \\psi _e\/c_e}{\\sum _e \\psi _e}. \\label{eq:1} \\end{equation}<\/script><\/div>\n<p> (The bound (\\ref{eq:1}) follows by algebra<a href=\"#a0000000009\" class=\"footnote\"><sup class=\"footnotemark\">1<\/sup><\/a>, using the inequalities <script type=\"math\/tex;\">\\exp (\\delta ) \\le 1+\\delta +O(\\delta ^2)<\/script> for <script type=\"math\/tex;\">\\delta \\le \\varepsilon =O(1)<\/script> and <script type=\"math\/tex;\">\\ln (1+z)\\le z<\/script> .) <\/p>\n<p>Let <script type=\"math\/tex;\">f^*<\/script> be an optimal feasible flow. For a <em>random<\/em> path <script type=\"math\/tex;\">p<\/script> chosen from the distribution defined by <script type=\"math\/tex;\">f^*\/|f^*|<\/script>, the expectation of the numerator in (\\ref{eq:1}) is <\/p>\n<div id=\"a0000000010\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\sum _e\\Pr [e\\in p] \\frac{\\psi _e}{c_e} = \\sum _e \\frac{f^*(e)}{|f^*|} \\frac{\\psi _e}{c_e} \\le \\sum _e \\frac{\\psi _e}{|f^*|} = \\frac{\\sum _e \\psi _e}{|f^*|}.  <\/script><\/div>\n<p> Thus, if <script type=\"math\/tex;\">p<\/script> is chosen randomly from <script type=\"math\/tex;\">f^*\/|f^*|<\/script>, the expectation of (\\ref{eq:1}) is at most <script type=\"math\/tex;\">(1+O(\\varepsilon ))\\varepsilon \/|f^*|<\/script>. Thus, there <em>exists<\/em> a path <script type=\"math\/tex;\">p<\/script> to choose that would keep <script type=\"math\/tex;\">\\Phi <\/script> from increasing by more than <script type=\"math\/tex;\">(1+O(\\varepsilon ))\\varepsilon \/|f^*|<\/script> in the iteration. The algorithm chooses <script type=\"math\/tex;\">p<\/script> to <em>minimize<\/em> (\\ref{eq:1}), so in fact <script type=\"math\/tex;\">\\Phi <\/script> increases by at most <script type=\"math\/tex;\">(1+O(\\varepsilon ))\\varepsilon \/|f^*|<\/script> in each iteration of the algorithm. <\/p>\n<p>Since <script type=\"math\/tex;\">\\Phi <\/script> is initially <script type=\"math\/tex;\">\\ln m<\/script>, and the flow value <script type=\"math\/tex;\">|f|<\/script> increases by <script type=\"math\/tex;\">\\varepsilon <\/script> in each iteration, it follows by algebra that the algorithm maintains the invariant <\/p>\n<div id=\"a0000000011\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\frac{\\Phi - \\ln (m)}{(1+O(\\varepsilon ))\/|f^*|} \\le |f|.  <\/script><\/div>\n<p>Recall that the maximum edge congestion is at most <script type=\"math\/tex;\">\\Phi <\/script>. By the termination condition, at termination <script type=\"math\/tex;\">\\Phi <\/script> is at least <script type=\"math\/tex;\">\\ln (m)\/\\varepsilon <\/script>, so the <script type=\"math\/tex;\">\\ln m<\/script> term in the numerator above is <script type=\"math\/tex;\">O(\\varepsilon \\Phi )<\/script>. Substituting <script type=\"math\/tex;\">O(\\varepsilon \\Phi )<\/script> for <script type=\"math\/tex;\">\\ln m<\/script> and simplifying gives <\/p>\n<div id=\"a0000000012\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\frac{|f|}{\\Phi } \\ge (1-O(\\varepsilon ))|f^*|.  <\/script><\/div>\n<p> Thus, scaling <script type=\"math\/tex;\">f<\/script> down by <script type=\"math\/tex;\">\\Phi <\/script> would give a flow of value <script type=\"math\/tex;\">(1-O(\\varepsilon ))|f^*|<\/script>. Since the algorithm scales <script type=\"math\/tex;\">f<\/script> down by the maximum edge congestion, which is less than than <script type=\"math\/tex;\">\\Phi <\/script>, the algorithm returns a flow of value at least <script type=\"math\/tex;\">(1-O(\\varepsilon ))|f^*|<\/script>. <\/p>\n<\/div>\n<\/details>\n<\/div>\n<p>The potential <script type=\"math\/tex;\">\\Phi <\/script> in the proof combines all the hard edge-capacity constraints into a single smooth function. This is the hallmark of a Lagrangian-relaxation algorithm. <\/p>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000013\">Width-based bound on the convergence rate<\/h1>\n<p> Historically, Lagrangian-relaxation algorithms have generally been used heuristically, without proven bounds on their worst-case convergence rates. One of the main contributions of research since the 1990s has been to prove tight worst-case upper bounds on convergence rates, and to find potential functions and step sizes that lead to faster convergence rates. <\/p>\n<div id=\"a0000000014\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b \"=\"&quot;\">Lemma.<\/b>   <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>The algorithm above makes at most <script type=\"math\/tex;\">|f^*|\\ln (m)\/\\varepsilon ^2<\/script> iterations. <\/p>\n<\/div><\/div>\n<div id=\"a0000000015\" class=\"latex-paragraph latex-proof\">\n<div class=\"latex-paragraph-heading\">  <b>Proof. <\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>The algorithm scales <script type=\"math\/tex;\">f<\/script> down by roughly <script type=\"math\/tex;\">\\ln (m)\/\\varepsilon <\/script> at the end. The resulting flow <script type=\"math\/tex;\">f'<\/script> is feasible, so has value at most <script type=\"math\/tex;\">|f^*|<\/script>. It follows that before scaling <script type=\"math\/tex;\">|f|<\/script> has value at most about <script type=\"math\/tex;\">|f^*|\\ln (m)\/\\varepsilon <\/script>. Since each iteration increases <script type=\"math\/tex;\">|f|<\/script> by <script type=\"math\/tex;\">\\varepsilon <\/script>, it follows that there are at most <script type=\"math\/tex;\">|f^*|\\ln (m)\/\\varepsilon ^2<\/script> iterations. <\/p>\n<\/div>\n<div style=\"float:right;border:1px solid #444;width:0.45em;height:0.45em\">\u00a0<\/div>\n<div style=\"clear:both\">\u00a0<\/div>\n<\/p><\/div>\n<p>It is not hard to see that this upper bound is tight for this algorithm on all inputs. (It stops when the maximum edge congestion is about <script type=\"math\/tex;\">\\ln (m)\/\\varepsilon <\/script>, so that scaling <script type=\"math\/tex;\">f<\/script> down by <script type=\"math\/tex;\">\\ln (m)\/\\varepsilon ^2<\/script> gives a flow of value about <script type=\"math\/tex;\">|f^*|<\/script>.) <\/p>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<p>In general, the previous approach gives bounds on the number of iterations that depend on the so-called <em>width<\/em> of the problem instance. In this case the width is <script type=\"math\/tex;\">|f^*|\/\\min _e c_e<\/script>, which is at most <script type=\"math\/tex;\">\\sum _e c_e \/ \\min _e c_e<\/script>. In some problems of interest the width can be as small as <script type=\"math\/tex;\">O(1)<\/script>, but in general the width can be large. <\/p>\n<\/div>\n<div class=\"latex-section\">\n<h1 id=\"a0000000016\">Width-independent bounds on convergence rates<\/h1>\n<p> To reduce the number of iterations, modify the algorithm as follows (following Garg and K\u00f6nemann\u00a0<span class=\"cite\">[<a href=\"#Garg98Faster\">1<\/a>]<\/span>). In each iteration, instead of sending <script type=\"math\/tex;\">\\varepsilon <\/script> units of flow, send <script type=\"math\/tex;\">\\varepsilon \\, \\min _{e\\in p} c_e<\/script> units, where <script type=\"math\/tex;\">p<\/script> is the chosen path. It is not hard to modify the proof to show that the approximation ratio continues to hold. <\/p>\n<div id=\"a0000000017\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b \"=\"&quot;\">Lemma.<\/b>   <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>The modified algorithm does at most <script type=\"math\/tex;\">\\min (m, |f^*|)\\, \\ln (m)\/\\varepsilon ^2<\/script> iterations. <\/p>\n<\/div><\/div>\n<div id=\"a0000000018\" class=\"latex-paragraph latex-proof\">\n<div class=\"latex-paragraph-heading\">  <b>Proof. <\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>In each iteration, at least one edge <script type=\"math\/tex;\">e\\in p<\/script> has its flow increase by <script type=\"math\/tex;\">\\varepsilon c_e<\/script>. Thus, within <script type=\"math\/tex;\">m\\ln (m)\/\\varepsilon ^2<\/script> iterations, at least one of the <script type=\"math\/tex;\">m<\/script> edges <script type=\"math\/tex;\">e\\in E<\/script> must have flow at least <script type=\"math\/tex;\">c_e \\ln (m)\/\\varepsilon <\/script>, and the algorithm will terminate. <\/p>\n<p>The bound of <script type=\"math\/tex;\">|f^*|\\ln (m)\/\\varepsilon ^2<\/script> iterations also holds, because each iteration increases <script type=\"math\/tex;\">|f^*|<\/script> by at least <script type=\"math\/tex;\">\\varepsilon <\/script>. <\/p>\n<\/div>\n<div style=\"float:right;border:1px solid #444;width:0.45em;height:0.45em\">\u00a0<\/div>\n<div style=\"clear:both\">\u00a0<\/div>\n<\/p><\/div>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000019\">Exercise: fractional set cover<\/h1>\n<p> Given a <a href=\"http:\/\/algnotes.info\/on\/modeling\">fractional set cover<\/a> <script type=\"math\/tex;\">x<\/script>, let <script type=\"math\/tex;\">x(e) = \\sum _{s\\ni e} x_s<\/script> denote the coverage of any element <script type=\"math\/tex;\">e<\/script>. Consider the following algorithm for finding an approximately maximum-size fractional set cover: <\/p>\n<blockquote class=\"quote\"><p><em> Start with <script type=\"math\/tex;\">x_s = 0<\/script> for each set <script type=\"math\/tex;\">s<\/script>, then, in each iteration add <script type=\"math\/tex;\">\\varepsilon <\/script> to <script type=\"math\/tex;\">x_s<\/script> where <script type=\"math\/tex;\">s<\/script> maximizes <script type=\"math\/tex;\">\\sum _{e\\in s} \\exp (-x(e))<\/script>. Stop when every element is covered by at least a total weight of <script type=\"math\/tex;\">\\ln (m)\/\\varepsilon ^2<\/script>, and return <script type=\"math\/tex;\">x<\/script>, scaled by the minimum element coverage.<\/em> <\/p><\/blockquote>\n<p>Use the potential function <script type=\"math\/tex;\">-\\ln \\sum _e \\exp (-x(e))<\/script>, a lower bound on the minimum coverage of any element <script type=\"math\/tex;\">e<\/script>, to show that the algorithm is a <script type=\"math\/tex;\">(1-O(\\varepsilon ))<\/script>-approximation algorithm. (Hint: show that the potential increases by <em>at least<\/em> <script type=\"math\/tex;\">(1-O(\\varepsilon ))\\varepsilon \/|x^*|<\/script> in each iteration.) <\/p>\n<p>Modify the algorithm to delete elements as soon as their coverage exceeds <script type=\"math\/tex;\">\\ln (m)\/\\varepsilon ^2<\/script>. Show that the approximation ratio still holds, and that the resulting algorithm requires <script type=\"math\/tex;\">O(m\\ln (m)\/\\varepsilon ^2)<\/script> iterations, where <script type=\"math\/tex;\">m<\/script> is the number of elements to be covered. <\/p>\n<\/div>\n<div class=\"latex-section\">\n<h1 id=\"a0000000020\">Related<\/h1>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/lagrangian-relaxation-discussion\">A brief but long-winded discussion of Lagrangian-relaxation<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/obliv\">Using randomized rounding to derive Lagrangian-relaxation algorithms<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/multicommodity-flow\">Using randomized rounding to derive this algorithm<\/a> <\/p>\n<\/li>\n<li>\n<p>On Wikipedia: <a href=\"http:\/\/en.wikipedia.org\/wiki\/multi-commodity flow\">Multicommodity flow<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Lagrangian_relaxation\">Lagrangian relaxation<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div>\n<h1 id=\"bibliography\">Bibliography<\/h1>\n<table class=\"bibliography\" cellspacing=\"0\" cellpadding=\"2\">\n<tr>\n<td valign=\"top\">[<a name=\"Garg98Faster\">1<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;N+Garg+&quot;+author:&quot;+J+Konemann&quot;+intitle:&quot;+Faster+and+simpler+algorithms+for+multicommodity+flow+and+other+fractional+packing+problems&quot;\">N.\u00a0Garg and J.\u00a0K\u00f6nemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In <em>Thirty Ninth Annual Symposium on Foundations of Computer Science<\/em>, pages 300\u2013309, 1998. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Grigoriadis94Fast\">2<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;M+D++Grigoriadis+&quot;+author:&quot;+L+G++Khachiyan&quot;+intitle:&quot;+Fast+approximation+schemes+for+convex+programs+with+many+blocks+and+coupling+constraints&quot;\">M.\u00a0D. Grigoriadis and L.\u00a0G. Khachiyan. Fast approximation schemes for convex programs with many blocks and coupling constraints. <em>SIAM J. Optimization<\/em>, 4(1):86\u2013107, Feb. 1994. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Klein94Faster\">3<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;P+Klein&quot;+author:&quot;+S+A++Plotkin&quot;+author:&quot;+C+Stein&quot;+author:&quot;+&quot;+author:&quot;+E+Tardos&quot;+intitle:&quot;+Faster+approximation+algorithms+for+the+unit+capacity+concurrent+flow+problem+with+applications+to+routing+and+finding+sparse+cuts&quot;\">P.\u00a0Klein, S.\u00a0A. Plotkin, C.\u00a0Stein, and E.\u00a0Tardos. Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. <em>SIAM J. Comput.<\/em>, 23(3):466\u2013487, June 1994. Preliminary version in STOC\u201990. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Plotkin95Fast\">4<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;S+A++Plotkin&quot;+author:&quot;+D+B++Shmoys&quot;+author:&quot;+&quot;+author:&quot;+E+Tardos&quot;+intitle:&quot;+Fast+approximation+algorithms+for+fractional+packing+and+covering+problems&quot;\">S.\u00a0A. Plotkin, D.\u00a0B. Shmoys, and E.\u00a0Tardos. Fast approximation algorithms for fractional packing and covering problems. <em>Math. Operations Research<\/em>, 20(2):257\u2013301, 1995. Preliminary version in FOCS\u201991. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Shahrokhi90Maximum\">5<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;F+Shahrokhi+&quot;+author:&quot;+D+W++Matula&quot;+intitle:&quot;+The+maximum+concurrent+flow+problem&quot;\">F.\u00a0Shahrokhi and D.\u00a0W. Matula. The maximum concurrent flow problem. <em>J. ACM<\/em>, 37:318\u2013334, 1990. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Young95Randomized\">6<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;N+E++Young&quot;+intitle:&quot;+Randomized+rounding+without+solving+the+linear+program&quot;\">N.\u00a0E. Young. Randomized rounding without solving the linear program. In <em>Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms<\/em>, pages 170\u2013178, San Francisco, California, 22\u201324\u00a0Jan. 1995. <\/a><\/td>\n<\/tr>\n<\/table><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<div id=\"footnotes\">\n<div>\n<h2>Footnotes<\/h2>\n<ol>\n<li id=\"a0000000009\">Here is a full proof of bound (\\ref{eq:1}). Let <script type=\"math\/tex;\">\\delta _e = \\varepsilon [e\\in p]\/c_e<\/script> denote the increase in congestion on edge <script type=\"math\/tex;\">e<\/script>. Using <script type=\"math\/tex;\">\\delta _e\\le \\varepsilon \\le 1<\/script>,\n<div id=\"a0000000021\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\exp (f(e)\/c_e+\\delta _e) \\, =\\,  \\psi _e\\exp (\\delta _e) \\, =\\,  \\psi _e (1+\\delta _e +O(\\delta _e^2)) \\, \\le \\,  \\psi _e (1+(1+O(\\varepsilon ))\\delta _e). <\/script><\/div>\n<p> So the increase in <script type=\"math\/tex;\">\\Phi (f)<\/script> is at most <\/p>\n<div id=\"a0000000022\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\textstyle \\ln (\\sum _e \\psi _e(1+(1+O(\\varepsilon ))\\delta _e)) -\\ln (\\sum _e \\psi _e) ~ =~ \\displaystyle \\ln \\frac{\\sum _e \\psi _e(1+(1+O(\\varepsilon ))\\delta _e\\psi _e)}{\\sum _e \\psi _e}  <\/script><\/div>\n<div id=\"a0000000023\" class=\"equation\"><script type=\"math\/tex; mode=display\">  =~  \\ln \\Big[1 + (1+O(\\varepsilon ))\\frac{\\sum _e \\delta _e\\psi _e}{\\sum _e \\psi _e}\\Big] ~ \\le ~  (1+O(\\varepsilon ))\\frac{\\sum _e \\delta _e\\psi _e}{\\sum _e \\psi _e}.  <\/script><\/div>\n<\/li>\n<\/ol><\/div>\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"<p>A simple example of a Lagrangian-relaxation algorithm. The algorithm is for Maximum Multicommodity Flow. It illustrates some prototypical aspects of Lagrangian relaxation.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8676,"menu_order":7,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-932","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/932","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/comments?post=932"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/932\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8676"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=932"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}