{"id":8584,"date":"2014-12-07T10:44:25","date_gmt":"2014-12-07T18:44:25","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=8584"},"modified":"2026-09-30T09:14:53","modified_gmt":"2026-09-30T17:14:53","slug":"multicommodity-flow-local","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/obliv\/lagrangian\/multicommodity-flow-local\/","title":{"rendered":"Multicommodity Flow III: better approximation via localization"},"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>Strengthening the approximation ratio by \u201clocalizing\u201d the analysis.<\/em><\/center><\/p><\/blockquote>\n<p>  Localizing the previous existence proof improves the approximation ratio, replacing the number of edges <script type=\"math\/tex;\">m<\/script> by the maximum number of edges per path. It likewise gives a modest improvement in the running time.<!--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-increments\">Multicommodity Flow II: width-independence using non-uniform increments (for maximum-value Multicommodity Flow)<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/set-cover-local\">Greedy Set Cover III: weighted H(d)-approximation via localization<\/a> (for the idea of localization) <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/details>\n<\/div>\n<hr \/>\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\">Localized rounding scheme<\/h1>\n<table id=\"a0000000004\" 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-size 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\"> Let <script type=\"math\/tex;\">\\tilde c = 3(1+\\varepsilon )\\ln (d)\/\\varepsilon ^2<\/script> where <script type=\"math\/tex;\">d=\\max _{p\\in P} |p|<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">2.<\/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>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:0em\"> Define <script type=\"math\/tex;\">P'(\\tilde f) = \\{ p\\in P\\, |\\, \\forall e\\in p.~  \\tilde f(e) \\lt c_e\\} <\/script> (the non-saturated paths). <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">4.<\/td>\n<td style=\"padding-left:0em\"> Repeat until all paths in <script type=\"math\/tex;\">P<\/script> are saturated: <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">5.<\/td>\n<td style=\"padding-left:1em\"> For each path <script type=\"math\/tex;\">p\\in P'(\\tilde f)<\/script>, define <script type=\"math\/tex;\">\\delta _p = \\lfloor \\min _{e\\in E} \\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\">6.<\/td>\n<td style=\"padding-left:1em\"> Choose path <script type=\"math\/tex;\">p\\in P'(\\tilde f)<\/script> randomly from distribution <script type=\"math\/tex;\">q<\/script> on <script type=\"math\/tex;\">P'(\\tilde f)<\/script>, where <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\">7.<\/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\">8.<\/td>\n<td style=\"padding-left:0em\"> Return <script type=\"math\/tex;\">\\tilde f<\/script>. <\/td>\n<\/tr>\n<\/table>\n<div id=\"a0000000005\" 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>Let <script type=\"math\/tex;\">d<\/script> be the maximum number of capacity constraints on any path. For any <script type=\"math\/tex;\">\\varepsilon \\in (0,1)<\/script> such that <script type=\"math\/tex;\">\\min _{e\\in C} c_e \\ge \\tilde c = 3(1+\\varepsilon )\\ln (d)\/\\varepsilon ^2<\/script>, the flow <script type=\"math\/tex;\">\\tilde f<\/script> returned by the rounding scheme is feasible and has expected size at least <script type=\"math\/tex;\">|f^*|\/(1+\\varepsilon )<\/script>. <\/p>\n<\/div><\/div>\n<div id=\"a0000000006\" 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>Fix any instance <script type=\"math\/tex;\">{\\cal I}<\/script>. For any path <script type=\"math\/tex;\">p<\/script>, let <script type=\"math\/tex;\">{\\cal I}_p<\/script> be the subproblem of <script type=\"math\/tex;\">{\\cal I}<\/script> obtained by deleting all capacity constraints from <script type=\"math\/tex;\">{\\cal I}<\/script> except those on edges in <script type=\"math\/tex;\">p<\/script>, and giving value <script type=\"math\/tex;\">v_p<\/script> to path <script type=\"math\/tex;\">p<\/script> and value zero to all other paths. <\/p>\n<p>For any given path <script type=\"math\/tex;\">p<\/script>, if we were to run the original rounding scheme on <script type=\"math\/tex;\">{\\cal I}_p<\/script> with fractional flow <script type=\"math\/tex;\">f^*<\/script>, the existence proof for that rounding scheme implies that it would give <script type=\"math\/tex;\">\\tilde{f_p}<\/script> expectation at least <script type=\"math\/tex;\">f^*_p\/(1+\\varepsilon )<\/script>. Since the localized rounding scheme will increment <script type=\"math\/tex;\">\\tilde{f_p}<\/script> as much (or more)<a href=\"#a0000000007\" class=\"footnote\"><sup class=\"footnotemark\">1<\/sup><\/a> than that rounding scheme would, the localized scheme also gives <script type=\"math\/tex;\">\\tilde{f_p}<\/script> expectation at least <script type=\"math\/tex;\">f^*_p\/(1+\\varepsilon )<\/script>. <\/p>\n<p>By linearity of expectation, summing over the paths, in expectation, the value <script type=\"math\/tex;\">v(\\tilde f)<\/script> of the flow <script type=\"math\/tex;\">\\tilde f<\/script> returned by the localized scheme is at least <script type=\"math\/tex;\">\\sum _p v_pf^*_p\/(1+\\varepsilon ) = v(f^*)\/(1+\\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<p>Next we apply the method of conditional probabilities to derive the algorithm. As usual for a localized scheme, the pessimistic estimator is the value-weighted sum of the pessimistic estimators of the subproblems <script type=\"math\/tex;\">{\\cal I}_p<\/script> of the individual paths. <\/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=\"a0000000008\">Localized algorithm<\/h1>\n<table id=\"a0000000009\" 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,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\"> Let <script type=\"math\/tex;\">\\tilde c = 3(1+\\varepsilon )\\ln (d)\/\\varepsilon ^2<\/script> where <script type=\"math\/tex;\">d=\\max _{p\\in P} |p|<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">2.<\/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>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:0em\"> Define <script type=\"math\/tex;\">P'(\\tilde f) = \\{ p\\in P\\, |\\, \\forall e\\in p.~  \\tilde f(e) \\lt c_e\\} <\/script> (the non-saturated paths). <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">4.<\/td>\n<td style=\"padding-left:0em\"> Repeat until all paths in <script type=\"math\/tex;\">P<\/script> are saturated: <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">5.<\/td>\n<td style=\"padding-left:1em\"> Choose <script type=\"math\/tex;\">p\\in P<\/script> minimizing <script type=\"math\/tex;\">\\sum _{e\\in p} w_e\/v_p<\/script>, where <script type=\"math\/tex;\">w_e =\\infty <\/script> if <script type=\"math\/tex;\">e<\/script> is saturated; else <script type=\"math\/tex;\">w_e = (1+\\varepsilon )^{\\tilde c\\,  \\tilde f(e) \/ c_e}<\/script>.<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">6.<\/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 E} \\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\">7.<\/td>\n<td style=\"padding-left:0em\"> Return <script type=\"math\/tex;\">\\tilde f<\/script>. <\/td>\n<\/tr>\n<\/table>\n<p>The conditional expectation of the final flow value, given the current flow <script type=\"math\/tex;\">\\tilde f<\/script>, is at least the pessimistic estimator <script type=\"math\/tex;\"> \\psi (\\tilde f) ~ =~  \\sum _{p\\in P} v_p\\,  \\psi _p(\\tilde f), <\/script> where <\/p>\n<div id=\"a0000000010\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\psi _p(\\tilde f) ~ =~  f_p ~ +~  [p\\in P'(\\tilde f)]\\,  {\\textstyle \\frac{\\ln (1+\\varepsilon )}{\\tilde c\\,  \\varepsilon }}\\,  \\Big[\\tilde c - \\operatorname {smax}_{e\\in p} \\frac{\\tilde f(e) \\tilde c}{c_e} \\Big] \\, f^*_p.  <\/script><\/div>\n<p>The algorithm above makes each choice to keep <script type=\"math\/tex;\">\\psi (\\tilde f)<\/script> from decreasing, guaranteeing a successful outcome. (Curiously, this algorithm differs from the non-localized algorithm in that it does not scale the edge weights by <script type=\"math\/tex;\">1\/c_e<\/script>.) <\/p>\n<div class=\"expandable\" id=\"a0000000011\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for verification of pessimistic estimator\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for verification of pessimistic estimator\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p> We reuse the proof details of <a href=\"http:\/\/algnotes.info\/on\/multicommodity-flow-increments\">the non-localized scheme<\/a> to show that the localized algorithm maintains the invariant <script type=\"math\/tex;\">\\psi (\\tilde f) \\ge v(f^*)\/(1+\\varepsilon )<\/script>, and that the invariant implies the performance guarantee. <\/p>\n<p>1. <em>The invariant holds initially: <script type=\"math\/tex;\">(\\psi (\\overline0) \\ge v(f^*)\/(1+\\varepsilon ))<\/script>.<\/em> <\/p>\n<p>From the end of the proof details in <a href=\"http:\/\/algnotes.info\/on\/multicommodity-flow-increments\">the non-localized scheme<\/a>, recall that <script type=\"math\/tex;\">\\psi _p(\\overline0) \\ge f^*_p\/(1+\\varepsilon )<\/script> for each <script type=\"math\/tex;\">p\\in P<\/script>. Taking the weighted sum over <script type=\"math\/tex;\">p<\/script> shows <script type=\"math\/tex;\">\\psi (\\overline0) \\ge v(f^*)\/(1+\\varepsilon )<\/script>. <\/p>\n<p>2. <em>The algorithm chooses each path to keep <script type=\"math\/tex;\">\\psi (\\tilde f)<\/script> from decreasing.<\/em> <\/p>\n<p>Consider the pessimistic estimator <script type=\"math\/tex;\">\\psi _{p'}(\\tilde f)<\/script> for any given path <script type=\"math\/tex;\">p'\\in P<\/script>. From the proof details, when a path <script type=\"math\/tex;\">p<\/script> is chosen in a given iteration, this pessimistic estimator <script type=\"math\/tex;\">\\psi _{p'}(\\tilde f)<\/script> increases by at least <\/p>\n<div id=\"a0000000012\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\delta _p [p'=p] ~ -~  \\frac{\\sum _{e\\in p\\cap p'} \\delta _p w_e\/c_e}{\\sum _{e'\\in p'} w_{e'}} f^*_{p'}.  <\/script><\/div>\n<p> where <script type=\"math\/tex;\">w_{e}=(1+\\varepsilon )^{\\tilde f(e) \\tilde c\/c_e}<\/script>. (And if <script type=\"math\/tex;\">p'<\/script> leaves <script type=\"math\/tex;\">P'(\\tilde f)<\/script>, that can only increase <script type=\"math\/tex;\">\\psi _{p'}(\\tilde f)<\/script> more.) <\/p>\n<p>Taking the weighted sum over <script type=\"math\/tex;\">p<\/script>, the pessimistic estimator <script type=\"math\/tex;\">\\psi (\\tilde f)<\/script> increases by at least <script type=\"math\/tex;\">\\delta _p<\/script> times <\/p>\n<div id=\"a0000000013\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{align} &  v_p ~ -~  \\sum _{p'\\in P'} \\frac{\\sum _{e\\in p\\cap p'} w_e\/c_e}{\\sum _{e'\\in p'} w_{e'}} v_{p'} f^*_{p'} \\notag \\\\ ~ =~ &  v_{p} ~ -~  \\sum _{e\\in p} w_{e} \\sum _{p'\\in P', p'\\ni e} \\frac{f^*_{p'}}{c_{e}} \\Big[\\frac{v_{p'}}{\\sum _{e'\\in p'}w_{e'}}\\Big]. \\label{desired} \\end{align}<\/script><\/div>\n<p> The algorithm chooses the path <script type=\"math\/tex;\">p \\in P'<\/script> to maximize the ratio <script type=\"math\/tex;\">v_{p} \/ \\sum _{e'\\in p} w_{e'}<\/script>, which then dominates the ratio in square brackets for each <script type=\"math\/tex;\">p'\\in P'<\/script> in\u00a0\\eqref{desired} above, making sure\u00a0\\eqref{desired} is at least <\/p>\n<div id=\"a0000000014\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{align} & v_{p} \\,  - \\,  \\Big[\\frac{v_{p}}{\\sum _{e\\in p} w_e}\\Big] \\sum _{e\\in p} w_e \\sum _{p' \\in P', p'\\ni e} \\frac{f^*_{p'}}{c_{e}} &  (\\text{by the choice of } p' ) \\notag \\\\ ~ \\ge ~  & v_{p} \\,  - \\,  \\Big[\\frac{v_{p}}{\\sum _{e\\in p} w_e}\\Big] \\sum _{e\\in p} w_{e} &  (\\text{since } f^*(e) \\le c_{e}) \\notag \\\\ ~ =~  &  0. \\notag \\end{align}<\/script><\/div>\n<\/div>\n<\/details>\n<\/div>\n<p>The performance guarantee follows as a corollary: <\/p>\n<div id=\"a0000000015\" class=\"my-theorem latex-paragraph latex-thm\">\n<div class=\"latex-paragraph-heading\">   <b>Theorem <\/b> (localized algorithm).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Let <script type=\"math\/tex;\">d<\/script> be the maximum number of capacity constraints on any path. For any <script type=\"math\/tex;\">\\varepsilon \\in (0,1)<\/script> such that the minimum edge capacity is at least <script type=\"math\/tex;\">3(1+\\varepsilon )\\ln (d)\/\\varepsilon ^2<\/script>, the value <script type=\"math\/tex;\">v(\\tilde{f_p})<\/script> of the flow <script type=\"math\/tex;\">\\tilde f<\/script> returned by the algorithm is at least <script type=\"math\/tex;\">v(f^*)\/(1+\\varepsilon )<\/script>, where <script type=\"math\/tex;\">f^*<\/script> is a maximum-value feasible flow. <\/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 (d)\/\\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<p> (The iteration bound has the same proof as for <a href=\"http:\/\/algnotes.info\/on\/multicommodity-flow-increments\">the non-localized algorithm<\/a>.) <\/p>\n<\/div><\/div>\n<\/div>\n<\/div>\n<\/div>\n<div id=\"footnotes\">\n<div>\n<h2>Footnotes<\/h2>\n<ol>\n<li id=\"a0000000007\"> It can be more, because in the localized rounding scheme some path <script type=\"math\/tex;\">p'<\/script> that overlaps with <script type=\"math\/tex;\">p<\/script> may acquire a saturated edge before <script type=\"math\/tex;\">p<\/script> does, which can allow <script type=\"math\/tex;\">p<\/script> to be incremented for longer. <\/li>\n<\/ol><\/div>\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Strengthening the approximation ratio by \u201clocalizing\u201d the analysis. Localizing the previous existence proof improves the approximation ratio, replacing the number of edges by the maximum number of edges per path. It likewise gives a modest improvement in the running time.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8645,"menu_order":3,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8584","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8584","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=8584"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8584\/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=8584"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}