{"id":8645,"date":"2014-12-07T12:05:31","date_gmt":"2014-12-07T20:05:31","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=8645"},"modified":"2026-09-30T09:14:59","modified_gmt":"2026-09-30T17:14:59","slug":"lagrangian","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/obliv\/lagrangian\/","title":{"rendered":"Lagrangian-relaxation examples"},"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>Deriving Lagrangian-relaxation algorithms via randomized rounding.<\/em><\/center><\/p><\/blockquote>\n<p>  We systematically derive Lagrangian-relaxation algorithms by starting with randomized-rounding schemes whose analyses use Chernoff bounds, then applying the method of conditional probabilities. The pessimistic estimator gives the potential-function and invariant for 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\/modeling\">linear programming<\/a> \u2014 A very brief introduction to integer linear programming, including linear programs for Set Cover and Multicommodity Flow. <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/lagrangian-relaxation-example\">example algorithm<\/a> \u2014 An example of a prototypical Lagrangian-relaxation algorithm (for Multicommodity Flow), in case you\u2019re curious what one looks like. <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/randomized-rounding\">randomized rounding<\/a> \u2014 A brief introduction to randomized rounding. (See also <a href=\"http:\/\/algnotes.info\/on\/method-of-conditional-probabilities\">the method of conditional probabilities<\/a> and <a href=\"http:\/\/algnotes.info\/on\/pessimistic-estimators\">pessimistic estimators<\/a>.) <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/chernoff\">Chernoff bounds<\/a> \u2014 A review of a typical Chernoff bound. To derive Lagrangian-relaxation algorithms, you\u2019ll need to understand not only how to use the bound, but also <a href=\"http:\/\/algnotes.info\/on\/chernoff-proof\">the proof of the bound<\/a>. <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/obliv\">Introduction<\/a> \u2014 An introduction to the basic idea of using randomized rounding to derive greedy and Lagrangian-relaxation algorithms. <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/greedy\">deriving greedy algorithms<\/a> \u2014 The high-level concepts are the same for greedy algorithms and Lagrangian-relaxation algorithms. Greedy algorithms are technically a little simpler, so it might be easier to first learn the concepts in that setting. <\/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\">Four introductory examples<\/h1>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b><a href=\"http:\/\/algnotes.info\/on\/multicommodity-flow-uniform-capacities\">1. Multicommodity Flow with uniform capacities<\/a>.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> This example illustrates applying the method of conditional probabilities to a proof that is based on a standard Chernoff bound. The rounding scheme randomly samples a fixed number (about <script type=\"math\/tex;\">(1-\\varepsilon )|f|<\/script>) paths from the distribution <script type=\"math\/tex;\">f\/|f|<\/script> defined by the fractional solution <script type=\"math\/tex;\">f<\/script>. With each sample, it adds one unit of flow to the sampled path. By a standard Chernoff bound and the naive union bound, the expected number of over-capacity edges is less than 1. Applying the method of probabilities yields the algorithm. The pessimistic estimator is the sum of exponential penalty terms, one for each edge capacity. (Each exponential term comes from one application of Chernoff.) <\/p>\n<p>To keep things technically simple in this example, we assume each edge has the same capacity <script type=\"math\/tex;\">c<\/script>. The algorithm computes a <script type=\"math\/tex;\">(1-\\varepsilon )<\/script>-approximate maximum integer flow, as long as the edge capacity <script type=\"math\/tex;\">c<\/script> is <script type=\"math\/tex;\">\\Omega (\\log (m)\/\\varepsilon ^2)<\/script>. With appropriate scaling of the edge capacity, the number of iterations required is <script type=\"math\/tex;\">O(m\\log (m)\/\\varepsilon ^2)<\/script>. <\/p>\n<p>The algorithm can also be used to compute a <script type=\"math\/tex;\">(1-\\varepsilon )<\/script>-approximate <em>fractional<\/em> flow for arbitrary <script type=\"math\/tex;\">\\varepsilon \\in (0,1)<\/script>. We can view this as rounding to finer-than-integer units <script type=\"math\/tex;\">\\delta <\/script>, where <script type=\"math\/tex;\">\\delta <\/script> is chosen just small enough to make it probable that the rounding scheme gives a <script type=\"math\/tex;\">(1-\\varepsilon )<\/script>-approximate solution. <\/p>\n<\/div><\/div>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b><a href=\"http:\/\/algnotes.info\/on\/multicommodity-flow\">2. Multicommodity Flow (any capacities)<\/a>.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Next we drop the assumption that the edges all have the same capacity. This example illustrates how tweaking the analysis of the rounding scheme and adjusting the pessimistic estimator can lead to a more elegant algorithm. <\/p>\n<p>Assuming every edge capacity <script type=\"math\/tex;\">c_e<\/script> is <script type=\"math\/tex;\">\\Omega (\\log (m)\/\\varepsilon ^2)<\/script>, the algorithm computes a <script type=\"math\/tex;\">(1-\\varepsilon )<\/script>-approximate maximum integer flow. The algorithm can also be used to compute a <script type=\"math\/tex;\">(1-\\varepsilon )<\/script>-approximate fractional flow for arbitrary <script type=\"math\/tex;\">\\varepsilon \\in (0,1)<\/script>. The number of iterations required (with appropriate scaling of the edge capacities) is <script type=\"math\/tex;\">O\\big((\\sum _e c_e\/c_{\\min }) \\log (m)\/\\varepsilon ^2\\big)<\/script>, which can be exponential. <\/p>\n<p>The iteration bound is comparable to those by Plotkin et al.\u00a0<span class=\"cite\">[<a href=\"#Plotkin95Fast\">2<\/a>]<\/span>. This particular algorithm and analysis are from\u00a0<span class=\"cite\">[<a href=\"#Young95Randomized\">3<\/a>]<\/span>. <\/p>\n<\/div><\/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-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b><a href=\"http:\/\/algnotes.info\/on\/multicommodity-flow-weighted-via-expectations\">3. Weighted Multicommodity Flow<\/a>.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> For problems whose cost functions have weights, the increase in cost with each sample depends on the sample. Also, instead of sampling for a pre-determined number of samples, the most natural rounding scheme stops when some condition is met (such as when some edge reaches capacity). In this case, the standard Chernoff bound doesn\u2019t quite apply, but one can modify the Chernoff bound appropriately in various ways. <\/p>\n<p>In this example the goal is to compute a maximum-value feasible flow, where the value of each unit of flow depends on its commodity. The rounding scheme samples until an edge reaches capacity. With each sample, the increase in flow value depends on the sample. The analysis adapts the Chernoff bound to handle random stopping times. <\/p>\n<p>Assuming each edge capacity is at least <script type=\"math\/tex;\">2\\ln (m)\/\\varepsilon ^2<\/script>, the algorithm computes a <script type=\"math\/tex;\">(1-\\varepsilon )<\/script>-approximate maximum-value flow. The algorithm can also be used to compute a <script type=\"math\/tex;\">(1-\\varepsilon )<\/script>-approximate fractional flow for arbitrary <script type=\"math\/tex;\">\\varepsilon \\in (0,1)<\/script>. The number of iterations required is <script type=\"math\/tex;\">O\\big((\\sum _e c_e\/c_{\\min })\\log (m)\/\\varepsilon ^2\\big)<\/script>, which can be exponential. <\/p>\n<\/div><\/div>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b><a href=\"http:\/\/algnotes.info\/on\/multicommodity-flow-faster\">4. Faster Multicommodity Flow algorithm<\/a>.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> The algorithms in the examples above have a weakness: in general, they can take exponentially many iterations. To fix this, one more idea is needed: Garg and K\u00f6nemann\u2019s idea of <em>non-uniform increments<\/em>, that is, increasing the step size maximally in each iteration\u00a0<span class=\"cite\">[<a href=\"#garg2007faster\">1<\/a>]<\/span>. <\/p>\n<p>This example applies this idea to the <a href=\"http:\/\/algnotes.info\/on\/multicommodity-flow\">previous<\/a> Maximum Multicommodity Flow algorithm. In each iteration, the modified algorithm increases the flow on the chosen path <script type=\"math\/tex;\">p<\/script> by an integer <script type=\"math\/tex;\">\\delta _p<\/script> proportional to the minimum capacity of any edge in <script type=\"math\/tex;\">p<\/script>. (We can think of this as taking <script type=\"math\/tex;\">\\delta _p<\/script> steps at once, all with the same path <script type=\"math\/tex;\">p<\/script>.) The modification preserves the performance guarantee with a minor adjustment to the proof. The worst-case number of iterations required is <script type=\"math\/tex;\">O(m\\log (m)\/\\varepsilon ^2)<\/script> (with arbitrary edge capacities). The resulting algorithm is essentially equivalent to Garg and K\u00f6nemann\u2019s\u00a0<span class=\"cite\">[<a href=\"#garg2007faster\">1<\/a>]<\/span>. <\/p>\n<p>Instead of viewing the algorithm as a modification of the original algorithm, it is possible to derive the modified algorithm directly using randomized rounding. The rounding scheme, instead of incrementing <script type=\"math\/tex;\">\\tilde f_p<\/script> by 1 for each sampled path <script type=\"math\/tex;\">p<\/script>, increments <script type=\"math\/tex;\">\\tilde f_p<\/script> by <script type=\"math\/tex;\">\\delta _p<\/script>. The sampling distribution is adjusted accordingly: the probability of sampling a given path <script type=\"math\/tex;\">p<\/script> is made proportional to <script type=\"math\/tex;\">f_p\/\\delta _p<\/script> (where <script type=\"math\/tex;\">f<\/script> is the fractional solution being rounded), instead of <script type=\"math\/tex;\">f_p<\/script>. With this change, the rounding scheme has a random stopping time, and its analysis requires a modified Chernoff bound. We discuss this briefly in the example. <\/p>\n<\/div><\/div>\n<\/div>\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\">A few more examples<\/h1>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b>Remark.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> To apply this idea to <em>covering<\/em> problems requires one more technique: dropping covering constraints once they are met, and adjusting the increments accordingly. <\/p>\n<\/div><\/div>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b><a href=\"http:\/\/algnotes.info\/on\/sparse-strategies\">Sparse strategies for zero-sum games<\/a>.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Like the example for Multicommodity Flow with uniform edge capacities, this example uses a standard Chernoff bound. The algorithm computes a <script type=\"math\/tex;\">(1\\pm \\varepsilon )<\/script>-approximate (and sparse) mixed strategy for any two-player zero-sum matrix game with non-negative payoffs, given the payoff matrix. The number of iterations required (and the size of the support of the mixed strategy) is <script type=\"math\/tex;\">O(M \\log (m)\/\\varepsilon ^2)<\/script>. Here <script type=\"math\/tex;\">M<\/script> is the ratio of the maximum payoff to the value of the game. The number of iterations can be exponential. <\/p>\n<\/div><\/div>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b><a href=\"http:\/\/algnotes.info\/on\/set-cover-unweighted-fractional\">Fractional Unweighted Set Cover<\/a>.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> This example also uses a standard Chernoff bound. This main difference is that this example is for a covering problem (unweighted fractional set cover) instead of packing. The algorithm computes a <script type=\"math\/tex;\">(1+\\varepsilon )<\/script>-approximate minimum-size fractional set cover in <script type=\"math\/tex;\">O(m\\log (m)\/\\varepsilon ^2)<\/script> iterations. <\/p>\n<\/div><\/div>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b><a href=\"http:\/\/algnotes.info\/on\/set-cover-fractional\">Fractional Set Cover (weighted)<\/a>.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> This example is similar to the Weighted Multicommodity Flow example, in that it adapts the Chernoff bound to handle random stopping times, to deal with the fact that the objective function has weights. This example is for a covering problem. The number of iterations required to compute a <script type=\"math\/tex;\">(1+\\varepsilon )<\/script>-approximate minimum-cost fractional set cover is <script type=\"math\/tex;\">O\\big((\\sum _s c_s\/c_{\\min })\\log (m)\/\\varepsilon ^2\\big)<\/script>, which can be exponential. <\/p>\n<\/div><\/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=\"a0000000005\">Related<\/h1>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/greedy\">Deriving greedy algorithms<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/lagrangian-relaxation-discussion\">Discussion of Lagrangian relaxation<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<div>\n<h1 id=\"bibliography\">Bibliography<\/h1>\n<table class=\"bibliography\" cellspacing=\"0\" cellpadding=\"2\">\n<tr>\n<td valign=\"top\">[<a name=\"garg2007faster\">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. <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=\"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 class=\"latex-section\">\n<h1 id=\"a0000000006\">To add later<\/h1>\n<ul class=\"itemize\">\n<li>\n<p>localizing <\/p>\n<\/li>\n<li>\n<p>connection to boosting and expert advice <\/p>\n<\/li>\n<li>\n<p>covering example <\/p>\n<\/li>\n<li>\n<p>general packing and covering <\/p>\n<\/li>\n<\/ul>\n<\/div><\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Deriving Lagrangian-relaxation algorithms via randomized rounding. We systematically derive Lagrangian-relaxation algorithms by starting with randomized-rounding schemes whose analyses use Chernoff bounds, then applying the method of conditional probabilities. The pessimistic estimator gives the potential-function and invariant for the algorithm.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8643,"menu_order":10,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8645","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8645","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=8645"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8645\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8643"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=8645"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}