{"id":8582,"date":"2014-12-07T10:44:13","date_gmt":"2014-12-07T18:44:13","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=8582"},"modified":"2026-09-30T09:14:56","modified_gmt":"2026-09-30T17:14:56","slug":"multicommodity-flow-increments","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/obliv\/lagrangian\/multicommodity-flow-increments\/","title":{"rendered":"Multicommodity Flow II: width-independence via non-uniform increments"},"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>Speeding up the algorithm by increasing the step size.<\/em><\/center><\/p><\/blockquote>\n<p>  The previous rounding schemes increase the chosen variable <script type=\"math\/tex;\">\\tilde x_j<\/script> by 1 with each sample. This can be exponentially slow. To speed it up, we modify the rounding scheme (or algorithm) to take larger steps, with the step size varying each iteration. Here we use the idea to speed up the Multicommodity-Flow algorithm. <\/p>\n<p>This specific algorithm comes from Garg and K\u00f6nemann\u00a0<span class=\"cite\">[<a href=\"#Garg98Faster\">1<\/a>, <a href=\"#garg2007faster\">2<\/a>, <a href=\"#Konemann98Fast\">3<\/a>]<\/span>, although the basic idea (called a trust region) is well known. <\/p>\n<p>While we\u2019re at it, we also generalize the algorithm to handle maximum-weight Multicommodity Flow.<!--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><a href=\"http:\/\/algnotes.info\/on\/multicommodity-flow-slow\">The \u201cslow\u201d Multicommodity-Flow algorithm<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/set-cover-weighted\">Analyzing a scheme with a random stopping time<\/a> <\/p>\n<\/li>\n<li>\n<div class=\"subexpandable\" id=\"a0000000003\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\" Maximum-weight Multicommodity Flow (click for definition)\" class=\"collapseomatic highlight\" tabindex=\"10\"> Maximum-weight Multicommodity Flow (click for definition)<\/summary>\n<div class=\"collapseomatic_content\"> An instance is specified by a regular instance of Multicommodity flow, along with a weight (or value) <script type=\"math\/tex;\">v_p<\/script> for each path <script type=\"math\/tex;\">p<\/script>. The value <script type=\"math\/tex;\">v(f)<\/script> of a flow <script type=\"math\/tex;\">f<\/script> is then <script type=\"math\/tex;\">\\sum _{p\\in P} v_p f_p<\/script>. The goal is to find a feasible flow of maximum value. For the algorithm, one may require that the value <script type=\"math\/tex;\">v_p<\/script> of flow along a path <script type=\"math\/tex;\">p<\/script> depends only on, say, the commodity that the path serves. <\/div>\n<\/details>\n<\/div>\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=\"a0000000004\">Rounding scheme with non-uniform increments<\/h1>\n<table id=\"a0000000005\" class=\"latex-scheme\" 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> instance <script type=\"math\/tex;\">{\\cal I}=(\\mbox{graph } G, \\mbox{set of paths } P, \\mbox{capacities } (C,c), \\mbox{values } v)<\/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> integer flow <script type=\"math\/tex;\">\\tilde f<\/script> for <script type=\"math\/tex;\">{\\cal I}<\/script><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">0.<\/td>\n<td style=\"padding-left:0em\"> Compute a maximum-value fractional 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\"> Initialize <script type=\"math\/tex;\">\\tilde{f_p}=0<\/script> for every path <script type=\"math\/tex;\">p\\in P<\/script>. Let <script type=\"math\/tex;\">\\tilde c = 3(1+\\varepsilon )\\ln (m)\/\\varepsilon ^2<\/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 is saturated <script type=\"math\/tex;\">(\\exists e\\in C.~  \\tilde f(e) = c_e):<\/script> <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:1em\">  For each path <script type=\"math\/tex;\">p\\in P<\/script>, define increment <script type=\"math\/tex;\">\\delta _p = \\lfloor \\min _{e\\in C} \\min (c_e-\\tilde f(e), c_e\/\\tilde c) \\rfloor <\/script>, then choose path <script type=\"math\/tex;\">p\\in P<\/script> randomly from the probability distribution <script type=\"math\/tex;\">q<\/script> such that <script type=\"math\/tex;\">q_p = \\alpha \\,  f^*_p \/ \\delta _p<\/script> (choosing <script type=\"math\/tex;\">\\alpha <\/script> so that <script type=\"math\/tex;\">|q|=1<\/script>).<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">4.<\/td>\n<td style=\"padding-left:1em\"> Increase <script type=\"math\/tex;\">\\tilde{f_p}<\/script> by <script type=\"math\/tex;\">\\delta _p<\/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;\">\\tilde f<\/script>. <\/td>\n<\/tr>\n<\/table>\n<p>For each sample, the scheme fixes an increment <script type=\"math\/tex;\">\\delta _p\\gt 0<\/script> for each path <script type=\"math\/tex;\">p<\/script>, then samples a random path <script type=\"math\/tex;\">p<\/script> and increases the flow on the sampled path <script type=\"math\/tex;\">\\tilde{f_p}<\/script> by <script type=\"math\/tex;\">\\delta _p<\/script> (instead of 1). The sampling distribution is chosen so that the expected increase in each variable <script type=\"math\/tex;\">\\tilde{f_p}<\/script> is <script type=\"math\/tex;\">\\alpha \\,  f^*_p<\/script> for some <script type=\"math\/tex;\">\\alpha <\/script>. <\/p>\n<div id=\"a0000000006\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma <\/b> (existence).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Let <script type=\"math\/tex;\">m<\/script> be the number of edges with capacity constraints. For any <script type=\"math\/tex;\">\\varepsilon \\in (0,1)<\/script> such that <script type=\"math\/tex;\">\\min _e c_e \\ge \\tilde c = 3(1+\\varepsilon )\\ln (m)\/\\varepsilon ^2<\/script>, the flow <script type=\"math\/tex;\">\\tilde f<\/script> returned by the rounding scheme is feasible and has expected value at least <script type=\"math\/tex;\">v(f^*)\/(1+\\varepsilon )<\/script>. <\/p>\n<\/div><\/div>\n<p>Because the analysis must use a random stopping time, the standard Chernoff bound doesn\u2019t quite give the right proof. We adapt Chernoff to handle the random stopping time. It is possible to adapt it to give a tail bound on the probability of failure, but instead we adapt it to bound the expected flow size directly. This allows us to localize the bound later. <\/p>\n<p>Define <\/p>\n<div id=\"a0000000007\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\psi (\\tilde f) ~ =~  v(\\tilde f) ~ +~  {\\textstyle \\frac{\\ln (1+\\varepsilon )}{\\tilde c\\,  \\varepsilon }}\\,  \\Big[\\tilde c - \\operatorname {smax}_{e\\in C} \\frac{\\tilde f(e) \\tilde c}{c_e} \\Big] \\, v(f^*)  <\/script><\/div>\n<p> where <script type=\"math\/tex;\"> \\operatorname {smax}_{e\\in C} z_e ~ =~  \\log _{1+\\varepsilon }{\\textstyle \\sum _{e\\in C}} (1+\\varepsilon )^{z_e}. <\/script> This is a smooth approximation to <script type=\"math\/tex;\">\\max _{e\\in C} z_e<\/script>. <\/p>\n<p>To prove the lemma we show that <script type=\"math\/tex;\">\\psi (\\tilde f)<\/script> is a valid pessimistic estimator for the conditional expectation of the final flow size, and has initial value at least <script type=\"math\/tex;\">|f^*|\/(1+\\varepsilon )<\/script>. <\/p>\n<p>For the case of unit values <script type=\"math\/tex;\">(v_p=1)<\/script>, in fact, <script type=\"math\/tex;\">\\psi (\\tilde f)<\/script> is the (linearly scaled and translated)<a href=\"#a0000000008\" class=\"footnote\"><sup class=\"footnotemark\">1<\/sup><\/a> logarithm of the pessimistic estimator <script type=\"math\/tex;\">\\phi <\/script> for the algorithm for the <a href=\"http:\/\/algnotes.info\/on\/multicommodity-flow-slow\">\u201cslow\u201d multicommodity flow algorithm<\/a>. The calculations in this proof are somewhat forbidding, but they are essentially just the calculations underlying that proof in a different guise. <\/p>\n<div class=\"expandable\" id=\"a0000000009\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for proof details\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for proof details\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p> i) <em>At termination, the flow value <script type=\"math\/tex;\">v(\\tilde f)<\/script> is at least <script type=\"math\/tex;\">\\psi (\\tilde f)<\/script>.<\/em> <\/p>\n<p>Note that <script type=\"math\/tex;\">\\operatorname {smax}_{e\\in C} z_e<\/script> is an upper bound on <script type=\"math\/tex;\">\\max _{e\\in C} z_e<\/script>. At termination, some edge <script type=\"math\/tex;\">e<\/script> is saturated, so <script type=\"math\/tex;\">\\max _{e\\in C} \\tilde f(e) \\tilde c\/c_e<\/script> is at least <script type=\"math\/tex;\">\\tilde c<\/script>, so <script type=\"math\/tex;\">\\operatorname {smax}_{e\\in C} \\tilde f(e) \\tilde c\/c_e<\/script> is also at least <script type=\"math\/tex;\">\\tilde c<\/script>. Hence, in <script type=\"math\/tex;\">\\psi (\\tilde f)<\/script>, the factor <script type=\"math\/tex;\">[\\tilde c-\\cdots ]<\/script> in square brackets is negative, so <script type=\"math\/tex;\">\\psi (\\tilde f)<\/script> is at most <script type=\"math\/tex;\">v(\\tilde f)<\/script>. <\/p>\n<p>ii) <em>The quantity <script type=\"math\/tex;\">\\psi (\\tilde f)<\/script> is a sub-martingale.<\/em> <\/p>\n<p>At the start of a given iteration, let <script type=\"math\/tex;\">p<\/script> be the path chosen in the iteration. Let <script type=\"math\/tex;\">\\Delta _e<\/script> denote the increase in the flow <script type=\"math\/tex;\">\\tilde f(e)<\/script> on edge <script type=\"math\/tex;\">e\\in C<\/script> during the iteration: <script type=\"math\/tex;\">\\Delta _e = [e\\in p] \\delta _p<\/script>. <\/p>\n<p>Consider first the increase in <script type=\"math\/tex;\">\\operatorname {smax}_{e\\in C} \\tilde f(e) \\tilde c\/c_e<\/script>. Let <script type=\"math\/tex;\">w_e=(1+\\varepsilon )^{\\tilde f(e) \\tilde c\/c_e}<\/script> denote the summand for <script type=\"math\/tex;\">e<\/script> in the sum inside the <script type=\"math\/tex;\">\\operatorname {smax}<\/script>. The rounding scheme\u2019s restrictions on <script type=\"math\/tex;\">\\delta _p<\/script> ensure that <script type=\"math\/tex;\">\\Delta _e\\tilde c\/c_e \\in [0,1]<\/script> for each edge <script type=\"math\/tex;\">e<\/script>. Using this and <script type=\"math\/tex;\">(1+\\varepsilon )^z \\le 1+\\varepsilon z<\/script> for <script type=\"math\/tex;\">z\\in [0,1]<\/script>, the iteration increases the sum inside the <script type=\"math\/tex;\">\\operatorname {smax}<\/script> from <script type=\"math\/tex;\">\\sum _e w_e<\/script> to <\/p>\n<div id=\"a0000000010\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{align*}  \\sum _{e} w_e (1+\\varepsilon )^{\\Delta _e \\tilde c\/c_e} ~ & \\le ~  \\sum _{e} w_e (1+\\varepsilon \\Delta _e \\tilde c\/c_e) \\\\ ~ & =~  \\Big(\\sum _{e} w_e\\Big) \\Big(1+\\frac{\\varepsilon \\tilde c \\sum _{e} w_e \\Delta _e\/c_e}{\\sum _{e}w_e}\\Big). \\end{align*}<\/script><\/div>\n<p> Using <script type=\"math\/tex;\">\\log _{1+\\varepsilon }[W (1+Z)] =\\log _{1+\\varepsilon }(W)+\\log _{1+\\varepsilon }(1+Z) \\le \\log _{1+\\varepsilon }(W) + Z\/\\ln (1+\\varepsilon )<\/script>, it follows that the value of <script type=\"math\/tex;\">\\operatorname {smax}_{e\\in C} \\tilde f(e) \\tilde c\/c_e<\/script> itself increases by at most <\/p>\n<div id=\"a0000000011\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\frac{\\varepsilon \\, \\tilde c}{\\ln (1+\\varepsilon )} \\frac{\\sum _{e} w_e \\Delta _e\/c_e}{\\sum _{e} w_e}.  <\/script><\/div>\n<p> In turn, it follows that the value of <script type=\"math\/tex;\">\\psi (\\tilde f)<\/script> increases by at least <\/p>\n<div id=\"eqn:pess2\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{eqn:pess2} \\delta _p v_p ~ -~  \\frac{\\sum _{e} w_e \\Delta _e\/c_e}{\\sum _{e} w_e} v(f^*) ~ =~  \\delta _p v_p ~ -~  \\frac{\\sum _{e\\in p} \\delta _p w_e\/c_e}{\\sum _{e} w_e} v(f^*). \\end{equation}<\/script><\/div>\n<p> The expectation of <script type=\"math\/tex;\">\\delta _p v_p<\/script> is <script type=\"math\/tex;\">\\sum _p (\\alpha f^*_p\/\\delta _p) v_p\\delta _p = \\alpha v(f^*)<\/script>. The expectation of each <script type=\"math\/tex;\">\\Delta _e<\/script> is <script type=\"math\/tex;\">\\sum _{p\\ni e} (\\alpha f^*_p\/\\delta _p)\\delta _p \\le \\alpha c_e<\/script>. Hence, the lower bound above has non-negative expectation. <\/p>\n<p>iii) <em>At any time during the rounding scheme, the conditional expectation of the final flow value at termination, given the current flow <script type=\"math\/tex;\">\\tilde f<\/script>, is at least <script type=\"math\/tex;\">\\psi (\\tilde f)<\/script>.<\/em> <\/p>\n<p>Point (i) implies that the conditional expectation of the final flow value at termination is at least the conditional expectation of <script type=\"math\/tex;\">\\psi (\\tilde f)<\/script> at termination. Point (ii) above and Wald\u2019s equation imply that the latter is at least the current value of <script type=\"math\/tex;\">\\psi (\\tilde f)<\/script>. <\/p>\n<hr \/>\n<p>From point (iii) above it follows that, at the start of the rounding scheme, the expected value of the final flow is at least <script type=\"math\/tex;\">\\psi (\\overline0)<\/script>, which by calculation and the choice of <script type=\"math\/tex;\">\\tilde c = 3(1+\\varepsilon )\\ln (m)\/\\varepsilon ^2<\/script> is <\/p>\n<div id=\"a0000000012\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{align*} &  \\frac{\\ln (1+\\varepsilon )}{\\tilde c\\, \\varepsilon }\\Big[\\tilde c - \\frac{\\ln m}{\\ln (1+\\varepsilon )}\\Big] v(f^*) \\\\ ~ =~ &  \\frac{\\ln (1+\\varepsilon )}{\\varepsilon }\\Big[1 - \\frac{\\varepsilon ^2}{3(1+\\varepsilon )\\ln (1+\\varepsilon )}\\Big] v(f^*) \\\\ ~ \\ge ~ &  \\frac{1}{1+\\varepsilon }\\,  v(f^*). \\end{align*}<\/script><\/div>\n<p> The latter inequality above follows by algebra from <script type=\"math\/tex;\">(1+\\varepsilon )\\ln (1+\\varepsilon ) \\ge \\varepsilon +\\varepsilon ^2\/3<\/script> for <script type=\"math\/tex;\">\\varepsilon \\in [0,1]<\/script>. (Not coincidentally this is the same inequality that is used at the end of <a href=\"http:\/\/algnotes.info\/on\/chernoff-proof\">the proof of Chernoff<\/a>.) <\/p>\n<\/div>\n<\/details>\n<\/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=\"a0000000013\">Algorithm with non-uniform increments<\/h1>\n<table id=\"a0000000014\" 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> instance <script type=\"math\/tex;\">{\\cal I}=(\\mbox{graph } G, \\mbox{set of paths } P, \\mbox{capacities } c, \\mbox{values } v)<\/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> integer flow <script type=\"math\/tex;\">\\tilde f<\/script> for <script type=\"math\/tex;\">{\\cal I}<\/script><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">1.<\/td>\n<td style=\"padding-left:0em\"> Initialize <script type=\"math\/tex;\">\\tilde{f_p}=0<\/script> for every path <script type=\"math\/tex;\">p\\in P<\/script>. Let <script type=\"math\/tex;\">\\tilde c = 3(1+\\varepsilon )\\ln (m)\/\\varepsilon ^2<\/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 is saturated <script type=\"math\/tex;\">(\\exists e\\in C.~  \\tilde f(e) = c_e):<\/script> <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:1em\"> Choose path <script type=\"math\/tex;\">p\\in P<\/script> to minimize <script type=\"math\/tex;\">\\sum _{e\\in p} w_e\/(v_pc_e)<\/script>, where <script type=\"math\/tex;\">w_e = (1+\\varepsilon )^{\\tilde f(e) \\tilde c \/ c_e}<\/script>.<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">4.<\/td>\n<td style=\"padding-left:1em\"> Increase <script type=\"math\/tex;\">\\tilde{f_p}<\/script> by <script type=\"math\/tex;\">\\delta _p = \\lfloor \\min _{e\\in C} \\min (c_e-\\tilde f(e), c_e\/\\tilde c) \\rfloor <\/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;\">\\tilde f<\/script>. <\/td>\n<\/tr>\n<\/table>\n<p>Next we apply the method of conditional probabilities to derive the algorithm. <\/p>\n<p>We simply reuse the pessimistic estimator <script type=\"math\/tex;\">\\psi (\\tilde f)<\/script> (on the conditional expectation of the final flow size) from the existence proof. The algorithm chooses the path <script type=\"math\/tex;\">p<\/script> in each iteration to keep the pessimistic estimator from decreasing, and so guarantees a successful outcome. <\/p>\n<div class=\"expandable\" id=\"a0000000015\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for details\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for details\u2026<\/summary>\n<div class=\"collapseomatic_content\"> Bound\u00a0\\eqref{eqn:pess2} of the existence proof shows that in a given iteration the pessimistic estimator increases by at least <\/p>\n<div id=\"a0000000016\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\delta _p v_p ~ -~  \\frac{\\sum _{e\\in p} \\delta _p w_e\/c_e}{\\sum _{e\\in C} w_e} v(f^*)  <\/script><\/div>\n<p> and that there is always a path <script type=\"math\/tex;\">p\\in P<\/script> that makes this lower bound non-negative. Gathering terms that depend on <script type=\"math\/tex;\">p<\/script> (and factoring out <script type=\"math\/tex;\">\\delta _p<\/script>) this lower bound is non-negative for a given <script type=\"math\/tex;\">p<\/script> iff <\/p>\n<div id=\"a0000000017\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\textstyle \\sum _{e\\in p} w_e\/(v_pc_e) \\le (\\sum _{e\\in C} w_e) |f^*|.  <\/script><\/div>\n<p> Since the algorithm chooses <script type=\"math\/tex;\">p<\/script> to minimize the left-hand side above, the choice guarantees that the above inequality holds, so that the choice of <script type=\"math\/tex;\">p<\/script> does not decrease the pessimistic estimator. Hence, at termination the pessimistic estimator is at least its initial value. As shown in the existence proof, this implies that the final flow size is at least <script type=\"math\/tex;\">|f^*|\/(1+\\varepsilon )<\/script>. <\/div>\n<\/details>\n<\/div>\n<p>The performance guarantee follows: <\/p>\n<div id=\"a0000000018\" class=\"my-theorem latex-paragraph latex-thm\">\n<div class=\"latex-paragraph-heading\">   <b>Theorem <\/b> (<span class=\"cite\">[<a href=\"#Garg98Faster\">1<\/a>, <a href=\"#garg2007faster\">2<\/a>, <a href=\"#Konemann98Fast\">3<\/a>]<\/span>).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Let <script type=\"math\/tex;\">m=|C|<\/script> be the number of capacity constraints. For any <script type=\"math\/tex;\">\\varepsilon \\in (0,1)<\/script> such that <script type=\"math\/tex;\">\\min _{e\\in C} c_e \\ge 3(1+\\varepsilon )\\ln (m)\/\\varepsilon ^2<\/script>, given the graph <script type=\"math\/tex;\">G<\/script>, the set of paths <script type=\"math\/tex;\">P<\/script>, and <script type=\"math\/tex;\">\\varepsilon <\/script>, the algorithm above returns a feasible integer flow <script type=\"math\/tex;\">\\tilde f<\/script> whose value is at least <script type=\"math\/tex;\">v(f^*) \/ (1+\\varepsilon )<\/script>, where <script type=\"math\/tex;\">f^*<\/script> is any maximum-value feasible flow. <\/p>\n<\/div><\/div>\n<p>Finally, we bound the number of iterations that the algorithm (and rounding scheme) take. <\/p>\n<div id=\"a0000000019\" class=\"my-theorem latex-paragraph latex-thm\">\n<div class=\"latex-paragraph-heading\">   <b>Theorem <\/b> (<span class=\"cite\">[<a href=\"#Garg98Faster\">1<\/a>, <a href=\"#garg2007faster\">2<\/a>, <a href=\"#Konemann98Fast\">3<\/a>]<\/span>).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> The number of iterations taken by the algorithm is at most <script type=\"math\/tex;\">1+6 \\min (m, \\rho ) (1+\\varepsilon )\\ln (m)\/\\varepsilon ^2<\/script>, where <script type=\"math\/tex;\">\\rho = |f^*|\/\\min _{e\\in C} c_e<\/script> is the \u201cwidth\u201d of the problem instance. <\/p>\n<\/div><\/div>\n<div id=\"a0000000020\" 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>Recall <script type=\"math\/tex;\">\\tilde c = 3(1+\\varepsilon )\\ln (m)\/\\varepsilon ^2<\/script>, so the desired bound is <script type=\"math\/tex;\">2\\min (m, \\rho ) \\tilde c<\/script>. <\/p>\n<p>Each iteration except the last increases the flow on some edge <script type=\"math\/tex;\">e\\in p<\/script> (the bottleneck edge, the one determining the minimum in the definition of <script type=\"math\/tex;\">\\delta _p<\/script>) by <script type=\"math\/tex;\">\\lfloor c_e\/\\tilde c \\rfloor <\/script>, which is at least <script type=\"math\/tex;\">0.5 c_e\/\\tilde c<\/script>, so the number of iterations (before some edge is saturated) is at most <script type=\"math\/tex;\">2m \\tilde c<\/script>. <\/p>\n<p>Each iteration except the last increases the total flow <script type=\"math\/tex;\">|\\tilde f|<\/script> by at least <script type=\"math\/tex;\">\\lfloor \\min _{e\\in C} c_e\/\\tilde c \\rfloor <\/script>, which is at least <script type=\"math\/tex;\">0.5 \\min _{e\\in C} c_e\/\\tilde c<\/script>, so the number of iterations is at most <script type=\"math\/tex;\">2 |\\tilde f| \\tilde c \/ \\min _{e\\in C} c_e \\le 2\\rho \\tilde c<\/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<div class=\"latex-subsection\">\n<h2 id=\"a0000000021\">Related<\/h2>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/stopping-time-chernoff\">Chernoff bounds for random stopping times (probabilities of deviations).<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/expected-maximum-sum\">Chernoff bounds for random stopping times (expected maximums and minimums).<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Trust_region\">Trust region<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<\/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=\"garg2007faster\">2<\/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. <em>SIAM Journal on Computing<\/em>, 37:630, 2007. Preliminary version in FOCS\u201998 (pp.\u00a0300\u2013309). <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Konemann98Fast\">3<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;J+Konemann&quot;+intitle:&quot;+Fast+combinatorial+algorithms+for+packing+and+covering+problems&quot;\">J.\u00a0K\u00f6nemann. Fast combinatorial algorithms for packing and covering problems. Master\u2019s thesis, Universit\u00e4t des Saarlandes, 1998. <\/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=\"a0000000008\">Let <script type=\"math\/tex;\">\\phi (\\tilde f)<\/script> denote that pessimistic estimator with <script type=\"math\/tex;\">T=|f^*|\/(1+\\varepsilon )<\/script>. Then\n<div id=\"a0000000022\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\psi (\\tilde f) = \\frac{|f^*|}{1+\\varepsilon } - \\frac{|f^*| \\ln (1+\\varepsilon )}{\\tilde c\\,  \\varepsilon } \\log _{1+\\varepsilon } \\phi (\\tilde f). <\/script><\/div>\n<p> For intuition, note that if <script type=\"math\/tex;\">\\phi (\\tilde f)<\/script> is a super-martingale, then so is <script type=\"math\/tex;\">\\log _{1+\\varepsilon } \\phi (\\tilde f)<\/script>, which would make <script type=\"math\/tex;\">\\psi (\\tilde f)<\/script> a sub-martingale. But note that we haven\u2019t in fact shown that <script type=\"math\/tex;\">\\phi (\\tilde f)<\/script> is a super-martingale with respect to the rounding scheme <em>with increments<\/em>.<\/li>\n<\/ol><\/div>\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Speeding up the algorithm by increasing the step size. The previous rounding schemes increase the chosen variable by 1 with each sample. This can be exponentially slow. To speed it up, we modify the rounding scheme (or algorithm) to take larger steps, with the step size varying each iteration. Here we use the idea to [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8645,"menu_order":2,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8582","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8582","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=8582"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8582\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8645"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=8582"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}