{"id":8587,"date":"2014-12-07T10:44:38","date_gmt":"2014-12-07T18:44:38","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=8587"},"modified":"2026-09-30T09:13:53","modified_gmt":"2026-09-30T17:13:53","slug":"multicommodity-flow-slow","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/obliv\/lagrangian\/multicommodity-flow-slow\/","title":{"rendered":"Multicommodity Flow I: Lagrangian relaxation via Chernoff"},"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>Randomized rounding yields a Lagrangian-relaxation algorithm for Multicommodity Flow.<\/em><\/center><\/p><\/blockquote>\n<p>Applying the method of conditional probabilities to a sample-and-increment scheme for Multicommodity Flow yields a Lagrangian-relaxation algorithm with an approximation ratio comparable to the algorithm of Plotkin, Shmoys, and Tardos\u00a0<span class=\"cite\">[<a href=\"#Plotkin95Fast\">2<\/a>]<\/span>. The existence proof uses a standard Chernoff bound. This leads to exponential penalties (\u201cmultiplicative weights\u201d) in the algorithm.<!--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\/set-cover-unweighted\">a simpler example of oblivious randomized rounding (greedy Set Cover)<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/chernoff-proof\">Chernoff bound<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/randomized-rounding\">randomized rounding<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/method-of-conditional-probabilities\">the method of conditional probabilities<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/pessimistic-estimators\">pessimistic estimators<\/a> <\/p>\n<\/li>\n<li>\n<div class=\"subexpandable\" id=\"a0000000003\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\" Maximum multicommodity flow (click for definition)\" class=\"collapseomatic highlight\" tabindex=\"10\"> Maximum multicommodity flow (click for definition)<\/summary>\n<div class=\"collapseomatic_content\">\n<p> Fix a directed graph <script type=\"math\/tex;\">G<\/script> with capacity constraints <script type=\"math\/tex;\">c_e<\/script> for <script type=\"math\/tex;\">e\\in C<\/script>, and a collection of source-sink pairs <script type=\"math\/tex;\">(s_1,t_1), (s_2,t_2), \\ldots , (s_k, t_k)<\/script>. Let <script type=\"math\/tex;\">P<\/script> denote the set of paths from any source <script type=\"math\/tex;\">s_i<\/script> to its corresponding sink <script type=\"math\/tex;\">t_i<\/script>. A <em>flow<\/em> <script type=\"math\/tex;\">f<\/script> assigns an amount <script type=\"math\/tex;\">f_p\\ge 0<\/script> to each path <script type=\"math\/tex;\">p\\in P<\/script>. The <em>flow on edge <script type=\"math\/tex;\">e<\/script><\/em>, denoted <script type=\"math\/tex;\">f(e)<\/script>, is <script type=\"math\/tex;\">\\sum _{p\\ni e} f_p<\/script>. The flow is feasible if, for each edge <script type=\"math\/tex;\">e\\in C<\/script> the flow on <script type=\"math\/tex;\">e<\/script> is at most the capacity <script type=\"math\/tex;\">c_e<\/script>. The value of the flow, denoted <script type=\"math\/tex;\">|f|<\/script>, is the total flow on all the paths: <script type=\"math\/tex;\">\\sum _{p\\in P} f_p<\/script>. The goal is to find a feasible flow of maximum value. <\/p>\n<p>If each <script type=\"math\/tex;\">f_p<\/script> is an integer, then <script type=\"math\/tex;\">f<\/script> is an <em>integer flow<\/em>. <\/p>\n<\/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 for Multicommodity Flow<\/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{capacity constraints} C, c)<\/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\"> 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\">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> randomly from the distribution <script type=\"math\/tex;\">f^*\/|f^*|<\/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 1. <\/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>If the minimum edge capacity is sufficiently large, then the rounding scheme works with positive probability: <\/p>\n<div id=\"a0000000006\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma <\/b> (existence,\u00a0<span class=\"cite\">[<a href=\"#Young95Randomized\">3<\/a>]<\/span>).  <\/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 3(1+\\varepsilon )\\ln (m)\/\\varepsilon ^2<\/script>, with positive probability, the flow <script type=\"math\/tex;\">\\tilde f<\/script> returned by the rounding scheme is feasible and has size more than <script type=\"math\/tex;\">T=\\lfloor |f^*|\/(1+\\varepsilon )\\rfloor <\/script>. <\/p>\n<\/div><\/div>\n<p>The proof idea is that <script type=\"math\/tex;\">f^*<\/script> sends total flow at most <script type=\"math\/tex;\">c_e<\/script> on the paths crossing any given edge <script type=\"math\/tex;\">e<\/script>, so, in any given iteration the probability that the flow <script type=\"math\/tex;\">\\tilde f(e)<\/script> along <script type=\"math\/tex;\">e<\/script> increases (by 1) is at most <script type=\"math\/tex;\">c_e\/|f^*|<\/script>. Applying Chernoff, a calculation shows that event <em>\u201c<script type=\"math\/tex;\">\\tilde f(e) \\ge c_e<\/script> at the end of iteration <script type=\"math\/tex;\">T<\/script>\u201d<\/em> has probability less than <script type=\"math\/tex;\">1\/m<\/script>. Hence, the expected number of edges saturated at the end of iteration <script type=\"math\/tex;\">T<\/script> is less than 1. <\/p>\n<div class=\"expandable\" id=\"a0000000007\" 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> Fix any edge <script type=\"math\/tex;\">e<\/script>. With each sample, the probability that the sampled path contains <script type=\"math\/tex;\">e<\/script> is <script type=\"math\/tex;\">\\sum _{p\\ni e} f^*_p \/|f^*|<\/script>. Since <script type=\"math\/tex;\">f^*<\/script> is feasible, this is at most <script type=\"math\/tex;\">c_e\/|f^*|<\/script>. Thus, the expectation of the (rounded) flow <script type=\"math\/tex;\">\\tilde f(e)<\/script> on <script type=\"math\/tex;\">e<\/script> after <script type=\"math\/tex;\">T<\/script> samples is at most <script type=\"math\/tex;\">T c_e\/|f^*| \\le c_e\/(1+\\varepsilon )<\/script>. <\/p>\n<p>Note that <script type=\"math\/tex;\">\\tilde f(e)<\/script> is the sum <script type=\"math\/tex;\">\\sum _{t=1}^T [e \\in p_t]<\/script> of <script type=\"math\/tex;\">T<\/script> i.i.d.\u00a0random variables (the <script type=\"math\/tex;\">t<\/script>th of which is 1 if <script type=\"math\/tex;\">e<\/script> is in the <script type=\"math\/tex;\">t<\/script>th sampled path <script type=\"math\/tex;\">p_t<\/script>, and zero otherwise). By <a href=\"http:\/\/algnotes.info\/on\/chernoff-proof\">the Chernoff bound<\/a>, the probability that <script type=\"math\/tex;\">\\tilde f(e)<\/script> is <script type=\"math\/tex;\">(1+\\varepsilon ) c_e\/(1+\\varepsilon ) = c_e<\/script> (or more) is strictly less than <script type=\"math\/tex;\">\\exp (-\\varepsilon ^2 (c_e\/(1+\\varepsilon )) \/ 3 )<\/script>. <\/p>\n<p>By the assumption on <script type=\"math\/tex;\">\\min _e c_e<\/script> and <script type=\"math\/tex;\">\\varepsilon <\/script>, this quantity is at most <script type=\"math\/tex;\">1\/m<\/script>. Thus, the expected number of the <script type=\"math\/tex;\">m<\/script> edges <script type=\"math\/tex;\">e<\/script> with <script type=\"math\/tex;\">\\tilde f(e) \\ge c_e<\/script> is less than 1. So, with positive probability, after <script type=\"math\/tex;\">T<\/script> samples, every edge <script type=\"math\/tex;\">e<\/script> has <script type=\"math\/tex;\">\\tilde f(e) \\lt c_e<\/script>, so at least <script type=\"math\/tex;\">T+1<\/script> samples contribute to <script type=\"math\/tex;\">\\tilde f<\/script>. <\/p>\n<\/div>\n<\/details>\n<\/div>\n<p>Next we apply the method of conditional probabilities to derive the algorithm. <\/p>\n<div id=\"a0000000008\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma <\/b> (algorithm,\u00a0<span class=\"cite\">[<a href=\"#Young95Randomized\">3<\/a>]<\/span>).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Applying the method of conditional probabilities to the existence proof yields the following algorithm. <\/p>\n<\/div><\/div>\n<p>For the derivation, we need a pessimistic estimator <script type=\"math\/tex;\">\\phi _t<\/script> for the expectation of the number of edges saturated by iteration <script type=\"math\/tex;\">T<\/script>, conditioned on the current flow <script type=\"math\/tex;\">\\tilde f<\/script> at the end of a given iteration <script type=\"math\/tex;\">t \\le T<\/script>. The <a href=\"http:\/\/algnotes.info\/on\/chernoff-proof\">proof of the Chernoff bound<\/a> gives a pessimistic estimator for each edge. Summing over the edges gives the following pessimistic estimator: <\/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=\"a0000000009\">Multicommodity Flow via Chernoff<\/h1>\n<table id=\"a0000000010\" 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}=(G,P,C,c)<\/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><\/p>\n<div style=\"margin:0pt;padding:0pt;margin-bottom:6px\"><\/div>\n<\/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>. Set <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 a path <script type=\"math\/tex;\">p\\in P<\/script> minimizing <script type=\"math\/tex;\">\\sum _{e\\in p} w_e\/c_e<\/script>, where <script type=\"math\/tex;\">w_e = (1+\\varepsilon )^{\\tilde f(e) \\tilde c\/c_e}.<\/script> <br \/>(To choose <script type=\"math\/tex;\">p<\/script>, compute a shortest path in <script type=\"math\/tex;\">P<\/script> w.r.t.\u00a0edge weights <script type=\"math\/tex;\">w_e\/c_e<\/script>.)<\/p>\n<div style=\"margin:0pt;padding:0pt;margin-bottom:6px\"><\/div>\n<\/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 1. <\/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<div id=\"a0000000011\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\phi _t ~ =~  \\sum _{e\\in C} \\frac{ (1+\\varepsilon )^{\\tilde f(e)} \\exp \\big((T-t)\\,  \\varepsilon \\,  c_e\/|f^*|\\big)}{ (1+\\varepsilon )^{ c_e } }.  <\/script><\/div>\n<p>Unfortunately, to minimize this pessimistic estimator, the algorithm would need to know <script type=\"math\/tex;\">|f^*|<\/script>. <\/p>\n<p>To fix this, normalize each capacity constraint \u201c<script type=\"math\/tex;\">\\tilde f(e) \\le c_e<\/script>\u201d into the equivalent \u201c<script type=\"math\/tex;\">\\tilde f(e) \\tilde c\/c_e \\le \\tilde c<\/script>\u201d, where <script type=\"math\/tex;\">\\tilde c = 3(1+\\varepsilon )\\ln (m)\/\\varepsilon ^2<\/script> is the lower bound on <script type=\"math\/tex;\">\\min _e c_e<\/script>. Apply Chernoff to the now-normalized constraints. The proof still goes through, but now gives pessimistic estimator <\/p>\n<div id=\"a0000000012\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\phi '_t ~ =~  \\sum _{e\\in C} \\frac{ (1+\\varepsilon )^{\\tilde f(e) \\tilde c \/ c_e} \\,  \\exp \\big((T-t)\\,  \\varepsilon \\,  \\tilde c\/|f^*|\\big) }{ (1+\\varepsilon )^{\\tilde c } }.  <\/script><\/div>\n<p>The factors in <script type=\"math\/tex;\">\\phi '_t<\/script> that depend on <script type=\"math\/tex;\">f^*<\/script> are independent of <script type=\"math\/tex;\">e<\/script> (and <script type=\"math\/tex;\">\\tilde f<\/script>), so can be ignored. The algorithm makes each choice to minimize the pessimistic estimator (more precisely, an upper bound on it; see the verification of <script type=\"math\/tex;\">\\phi '_t<\/script> below). Hence, it guarantees a successful outcome. <\/p>\n<div class=\"expandable\" id=\"a0000000013\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for verification of pessimistic estimator..\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for verification of pessimistic estimator..<\/summary>\n<div class=\"collapseomatic_content\">\n<p> 1. <em>The pessimistic estimator is initially less than 1 <script type=\"math\/tex;\">(\\phi '_0 \\lt 1)<\/script>.<\/em> <\/p>\n<p>This is implicit in the existence proof and <a href=\"http:\/\/algnotes.info\/on\/chernoff-proof\">the proof of Chernoff<\/a>. (Namely, each summand in <script type=\"math\/tex;\">\\phi '_0<\/script> is less than <script type=\"math\/tex;\">1\/m<\/script>: by the choice of <script type=\"math\/tex;\">T\\le |f^*|\/(1+\\varepsilon )<\/script>, then using <script type=\"math\/tex;\">e^\\varepsilon \/(1+\\varepsilon )^{1+\\varepsilon } \\le e^{-\\varepsilon ^2\/3}<\/script> from the proof of Chernoff, <\/p>\n<div id=\"a0000000014\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{align*}  \\frac{\\exp (T\\, \\varepsilon \\, \\tilde c \/|f^*|)}{(1+\\varepsilon )^{\\tilde c}} ~ \\le ~  \\Big( \\frac{\\exp (\\varepsilon )}{(1+\\varepsilon )^{1+\\varepsilon }} \\Big)^{\\tilde c \/ (1+\\varepsilon )} ~ \\le ~  \\exp (-(\\varepsilon ^2\/3) \\tilde c\/(1+\\varepsilon )), \\end{align*}<\/script><\/div>\n<p> which is <script type=\"math\/tex;\">1\/m<\/script> or less by the choice of <script type=\"math\/tex;\">\\tilde c \\ge 3(1+\\varepsilon )\\ln (m)\/\\varepsilon ^2<\/script>.) <\/p>\n<p><div style=\"margin:0pt;padding:0pt;margin-bottom:6px\"><\/div>\n<\/p>\n<p>2. <em>The pessimistic estimator is a super-martingale with respect to the original randomized rounding scheme.<\/em> <\/p>\n<p>In iteration <script type=\"math\/tex;\">t<\/script>, letting <script type=\"math\/tex;\">\\omega ^e_t<\/script> denote the summand for <script type=\"math\/tex;\">e<\/script> in <script type=\"math\/tex;\">\\phi '_{t-1}<\/script> and <script type=\"math\/tex;\">p<\/script> the chosen path, <\/p>\n<div id=\"eqn:pess2\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{eqn:pess2} \\phi '_{t} ~ \\le ~  \\sum _{e\\in C} \\frac{ 1+\\varepsilon [e\\in p]\\tilde c\/c_e}{ 1+\\varepsilon \\tilde c\/|f^*|} \\omega ^e_t. \\end{equation}<\/script><\/div>\n<p> The probability that any given edge <script type=\"math\/tex;\">e<\/script> is in <script type=\"math\/tex;\">p<\/script> is at most <script type=\"math\/tex;\">c_e\/|f^*|<\/script>, so that the right-hand side above has expectation at most <script type=\"math\/tex;\">\\sum _{e\\in C} \\omega ^e_t = \\phi '_{t-1}<\/script>. <\/p>\n<p>3. <em>If the final pessimistic estimator is less than 1, the rounding scheme succeeds.<\/em> <\/p>\n<p>If <script type=\"math\/tex;\">\\phi '_T \\lt 1<\/script>, then for each edge <script type=\"math\/tex;\">e\\in C<\/script>, the summand in <script type=\"math\/tex;\">\\phi '_T<\/script> for <script type=\"math\/tex;\">e<\/script> is less than 1, which by inspection implies that <script type=\"math\/tex;\">\\tilde f(e) \\lt c_e<\/script> \u2014 no edges are saturated. <\/p>\n<hr \/>\n<p>Having verified correctness of the pessimistic estimator, we note that, in iteration <script type=\"math\/tex;\">t<\/script>, the algorithm above chooses <script type=\"math\/tex;\">p<\/script> to minimize the right-hand side of\u00a0\\eqref{eqn:pess2}. As that right-hand side has expectation at most <script type=\"math\/tex;\">\\phi '_{t-1}<\/script> for random <script type=\"math\/tex;\">p<\/script>, the algorithm ensures <script type=\"math\/tex;\">\\phi '_{t} \\le \\phi '_{t-1}<\/script>. <\/p>\n<\/div>\n<\/details>\n<\/div>\n<div id=\"a0000000015\" class=\"my-theorem latex-paragraph latex-thm\">\n<div class=\"latex-paragraph-heading\">   <b>Theorem <\/b> (<span class=\"cite\">[<a href=\"#Young95Randomized\">3<\/a>]<\/span>).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Let <script type=\"math\/tex;\">m=|V|<\/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 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>, the capacity constraints <script type=\"math\/tex;\">(C,c)<\/script>, and <script type=\"math\/tex;\">\\varepsilon <\/script>, the algorithm above returns a feasible integer flow <script type=\"math\/tex;\">\\tilde f<\/script> whose size is at least <script type=\"math\/tex;\">|f^*| \/ (1+\\varepsilon )<\/script>, where <script type=\"math\/tex;\">f^*<\/script> is any maximum-size feasible flow. <\/p>\n<\/div><\/div>\n<p>Algorithms with comparable performance guarantees were given (for example) by Plotkin, Shmoys, and Tardos\u00a0<span class=\"cite\">[<a href=\"#Plotkin95Fast\">2<\/a>]<\/span> and by Grigoriadis and Khachiyan\u00a0<span class=\"cite\">[<a href=\"#Grigoriadis94Fast\">1<\/a>]<\/span>. <\/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=\"a0000000016\">Discussion<\/h1>\n<p> Many technical questions remain. How do we find approximately optimal <em>fractional<\/em> solutions? How do we obtain a fast (strictly polynomial-time) algorithm? Can we generalize to other packing and covering problems? <\/p>\n<p>Fractional solutions can be obtained simply by scaling the capacities (given any <script type=\"math\/tex;\">\\varepsilon \\in (0,1)<\/script>, scale so <script type=\"math\/tex;\">\\min _e c_e \\ge 3(1+\\varepsilon )\\ln (m)\/\\varepsilon ^2<\/script>, then the algorithm will give a <script type=\"math\/tex;\">(1+\\varepsilon )<\/script>-approximate solution). Polynomial time can be ensured using Garg and K\u00f6nemann\u2019s <em>non-uniform increments<\/em>. And, yes, the approach generalizes to other problems. We address these questions in detail in other entries. <\/p>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000017\">Related<\/h2>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/chernoff-proof\/#Pessimistic_estimators\">various pessimistic estimators for the Chernoff bound<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/pessimistic-estimators\">flexibility in pessimistic estimators for Turan\u2019s theorem<\/a> <\/p>\n<\/li>\n<\/ul>\n<p><span style=\"float:right;margin:0.8em;margin-right:-0.5in;\"> <img decoding=\"async\" src=\"http:\/\/algnotes.info\/b\/wp-content\/uploads\/2014\/12\/img-00014.png\" alt=\"\\includegraphics[type=pdf,ext=.pdf,read=.pdf,width=.7in]{shared\/graphics\/work_in_progress}\" style=\"width:.7in\" class=\"zoooom\" \/> <\/span> <\/p>\n<\/div>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000018\">Questions for later<\/h2>\n<p> Can one formalize the notion of shifting slack into a pessimistic estimator to make it maximally oblivious? <\/p>\n<\/div>\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=\"Grigoriadis94Fast\">1<\/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=\"Plotkin95Fast\">2<\/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=\"Young95Randomized\">3<\/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","protected":false},"excerpt":{"rendered":"<p>Randomized rounding yields a Lagrangian-relaxation algorithm for Multicommodity Flow. Applying the method of conditional probabilities to a sample-and-increment scheme for Multicommodity Flow yields a Lagrangian-relaxation algorithm with an approximation ratio comparable to the algorithm of Plotkin, Shmoys, and Tardos\u00a0[2]. The existence proof uses a standard Chernoff bound. This leads to exponential penalties (\u201cmultiplicative weights\u201d) in [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8645,"menu_order":1,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8587","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8587","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=8587"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8587\/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=8587"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}