{"id":1102,"date":"2010-06-09T11:30:52","date_gmt":"2010-06-09T19:30:52","guid":{"rendered":"http:\/\/obliviousrounding.com\/blog\/?p=1102"},"modified":"2026-09-30T09:16:09","modified_gmt":"2026-09-30T17:16:09","slug":"randomized-rounding","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/randomized-rounding\/","title":{"rendered":"Randomized rounding"},"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>Randomly rounding a fractional LP solution to an integer solution.<\/em><\/center><\/p><\/blockquote>\n<p>  The idea, introduced by Raghavan and Thompson in 1987, is to use the probabilistic method to round the solution of a linear program, converting it into an approximately optimal integer solution\u00a0<span class=\"cite\">[<a href=\"#Raghavan87Randomized\">3<\/a>]<\/span>. It\u2019s a broadly useful technique. For many problems, randomized rounding yields algorithms with optimal approximation ratios (assuming P<script type=\"math\/tex;\">\\neq <\/script>NP). This note describes randomized rounding and gives a few examples.<!--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\/probabilistic-method\">the probabilistic method<\/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<p><a href=\"http:\/\/algnotes.info\/on\/modeling\">linear-program relaxations<\/a> and <a href=\"http:\/\/algnotes.info\/on\/rounding\">rounding LP solutions<\/a> <\/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\">Trivial example: Vertex Cover<\/h1>\n<p> Here is a very simple randomized-rounding scheme for Vertex Cover: <\/p>\n<blockquote class=\"quote\"><p><em> 1. Given any graph <script type=\"math\/tex;\">G<\/script>, compute a min-cost fractional vertex cover <script type=\"math\/tex;\">x^*<\/script>. <br \/>2. Return the random vertex cover <script type=\"math\/tex;\">\\tilde x<\/script> where <script type=\"math\/tex;\">\\tilde x_v = 1<\/script> with probability <script type=\"math\/tex;\">\\min (2x^*_v,1)<\/script>.<\/em> <\/p><\/blockquote>\n<p> The algorithm is a 2-approximation algorithm in expectation. Indeed, the rounded solution <script type=\"math\/tex;\">\\tilde x<\/script> is a cover because for any edge one of its two endpoints <script type=\"math\/tex;\">v<\/script> must have <script type=\"math\/tex;\">x^*_v \\ge 1\/2<\/script>, which forces <script type=\"math\/tex;\">v<\/script> into the cover <script type=\"math\/tex;\">\\tilde x<\/script>. By inspection, the expected cost of <script type=\"math\/tex;\">\\tilde x<\/script> is at most twice the cost of <script type=\"math\/tex;\">x^*<\/script>, which, since the cost of <script type=\"math\/tex;\">x^*<\/script> is a lower bound on the cost of the integral <span class=\"scshape\" style=\"font-variant:small-caps;text-transform:lowercase\">opt<\/span>, is at most <script type=\"math\/tex;\">2{\\textsc{opt}}<\/script>. <\/p>\n<\/div>\n<div class=\"latex-section\">\n<h1 id=\"a0000000004\">Relation to the probabilistic method in combinatorics<\/h1>\n<p> If you\u2019re already familiar with the probabilistic method, the new element here is that the fractional solution <script type=\"math\/tex;\">x^*<\/script> is used as basis for the probability distribution. This allows the cost of the rounded solution to be related to the cost of <script type=\"math\/tex;\">x^*<\/script>, and via that (since <script type=\"math\/tex;\">x^*<\/script> is an optimal solution to a relaxation) to the cost of <span class=\"scshape\" style=\"font-variant:small-caps;text-transform:lowercase\">opt<\/span>. In this way, one obtains the per-input worst-case performance guarantees necessary for approximation algorithms. <\/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=\"a0000000005\">Standard randomized-rounding scheme for Set Cover<\/h1>\n<p> Next is a more sophisticated example of randomized rounding: a standard randomized-rounding scheme for Set Cover. This example is comparable to one in\u00a0<span class=\"cite\">[<a href=\"#Vazirani03Approximation\">4<\/a>, Sec.14.2]<\/span>. For more examples, see\u00a0<span class=\"cite\">[<a href=\"#Motwani95\">1<\/a>, ch.4]<\/span>. <\/p>\n<div class=\"expandable\" id=\"a0000000006\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for the definition of Set Cover\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for the definition of Set Cover\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p>Given a collection <script type=\"math\/tex;\">S<\/script> of finite sets from a universe <script type=\"math\/tex;\">U<\/script> and a cost <script type=\"math\/tex;\">c_s<\/script> for each set <script type=\"math\/tex;\">s\\in S<\/script>, the problem is to choose a minimum-cost <em>set cover<\/em> \u2014 a collection <script type=\"math\/tex;\"> C<\/script> of sets in <script type=\"math\/tex;\"> S<\/script> such that each element <script type=\"math\/tex;\">e\\in U<\/script> is contained in at least one set in <script type=\"math\/tex;\"> C<\/script>. The cost of <script type=\"math\/tex;\"> C<\/script> is <script type=\"math\/tex;\">\\sum _{s\\in C} c_s<\/script>. <\/p>\n<\/div>\n<\/details>\n<\/div>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b>Rounding scheme.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Let <script type=\"math\/tex;\">x^*<\/script> be a minimum-cost fractional set cover <script type=\"math\/tex;\">x^*<\/script> (computed, say, by linear programming). Consider first the most natural scheme for rounding <script type=\"math\/tex;\">x^*<\/script>: <\/p>\n<blockquote class=\"quote\"><p><em> For each set <script type=\"math\/tex;\">s\\in S<\/script> independently, take <script type=\"math\/tex;\">\\tilde x_s = 1<\/script> with probability <script type=\"math\/tex;\">x^*_s<\/script>, otherwise take <script type=\"math\/tex;\">\\tilde x_s = 0<\/script>.<\/em> <\/p><\/blockquote>\n<p>With this rounding scheme, the expected cost of the chosen sets is <script type=\"math\/tex;\">\\sum _s c_s x^*_s<\/script>, the cost of the fractional cover. This is good. Unfortunately the coverage is not good in the worst case, when the set weights are relatively small, for then the probability that an element <script type=\"math\/tex;\">e<\/script> is not covered is about <\/p>\n<div id=\"a0000000007\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\prod _{s\\ni e} 1-x^*_s {\\, {\\approx }\\, }\\prod _{s\\ni e} \\exp (-x^*_s) {\\, {=}\\, }\\exp \\Big(-\\sum _{s\\ni e}x^*_s\\Big) {\\, {\\approx }\\, }\\exp (-1).  <\/script><\/div>\n<p> Only a constant fraction of the elements will be covered in expectation. To increase the coverage, the standard rounding scheme scales up the rounding probabilities by an appropriate factor <script type=\"math\/tex;\">\\lambda \\gt 1<\/script>: <\/p>\n<blockquote class=\"quote\"><p><em> For each set <script type=\"math\/tex;\">s\\in S<\/script> independently, take <script type=\"math\/tex;\">\\tilde x_s = 1<\/script> with probability <script type=\"math\/tex;\">p_s = \\min (\\lambda x^*_s, 1)<\/script>, otherwise take <script type=\"math\/tex;\">\\tilde x_s = 0<\/script>. <\/em> <\/p><\/blockquote>\n<p> Scaling the probabilities increases the expected cost by <script type=\"math\/tex;\">\\lambda <\/script>, but makes coverage of all elements likely. <\/p>\n<p>The next step is to show that this rounding scheme works with positive probability. <\/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 id=\"a0000000008\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma <\/b> (existence proof).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>  Fix <script type=\"math\/tex;\">\\lambda = \\ln (2n)<\/script>, where <script type=\"math\/tex;\">n<\/script> is the number of elements. With non-zero probability, the rounding scheme returns a set cover <script type=\"math\/tex;\">\\tilde x<\/script> of cost at most <script type=\"math\/tex;\">2\\ln (2 n)\\,  c\\cdot x^*<\/script> (and thus, of cost <script type=\"math\/tex;\">O(\\log n)<\/script> times <script type=\"math\/tex;\">{\\textsc{opt}}<\/script>). <\/p>\n<\/div><\/div>\n<p> (Note: with care the <script type=\"math\/tex;\">O(\\log n)<\/script> can be reduced to <script type=\"math\/tex;\">\\ln (n)+O(\\log \\log n)<\/script>.) <\/p>\n<p><div style=\"margin:0pt;padding:0pt;margin-bottom:12px\"><\/div>\n<\/p>\n<div id=\"a0000000009\" class=\"latex-paragraph latex-proof\">\n<div class=\"latex-paragraph-heading\">  <b>Proof. <\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>The output <script type=\"math\/tex;\">\\tilde x<\/script> of the random rounding scheme has the desired properties as long as none of the following \u201cbad\u201d events occur: <\/p>\n<ul class=\"itemize\">\n<li>\n<p>the cost <script type=\"math\/tex;\">c\\cdot \\tilde x<\/script> is too high: it exceeds <script type=\"math\/tex;\">2\\lambda c\\cdot x^*<\/script>, or <\/p>\n<\/li>\n<li>\n<p><script type=\"math\/tex;\">\\tilde x<\/script> is not a cover: it fails to cover one of the <script type=\"math\/tex;\">n<\/script> elements <script type=\"math\/tex;\">e<\/script>. <\/p>\n<\/li>\n<\/ul>\n<p>Regarding the cost, the expectation of each <script type=\"math\/tex;\">\\tilde x_s<\/script> is at most <script type=\"math\/tex;\">\\lambda x_s^*<\/script>. By linearity of expectation, the expectation of <script type=\"math\/tex;\">c\\cdot \\tilde x<\/script> is at most <script type=\"math\/tex;\">\\sum _s c_s\\lambda x_s^*=\\lambda c\\cdot x^*<\/script>. Thus, by the Markov bound, the probability of the first bad event (the cost is too high) is at most <script type=\"math\/tex;\">1\/2<\/script>. <\/p>\n<p>For the remaining bad events (coverage of each element <script type=\"math\/tex;\">e<\/script>), note that, for any given element <script type=\"math\/tex;\">e<\/script>, since <script type=\"math\/tex;\">\\sum _{s\\ni e} x^*_s \\ge 1<\/script>, the probability that <script type=\"math\/tex;\">e<\/script> is not covered is <\/p>\n<div id=\"a0000000010\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\prod _{s\\ni e} 1-p_s {\\, {<}\\, }\\prod _{s\\ni e} \\exp ({-}\\lambda x^*_s) {\\, {=}\\, }\\exp \\Big({-}\\lambda \\sum _{s\\ni e} x^*_s \\Big) {\\, {\\le }\\, }\\exp ({-}\\lambda ) {\\, {=}\\, }1\/(2n).  <\/script><\/div>\n<p> (The first step uses <script type=\"math\/tex;\">p_s = \\min (\\lambda x^*_s,1)<\/script> and <script type=\"math\/tex;\">1-z\\le e^{-z}<\/script>, which is strict for <script type=\"math\/tex;\">z\\ne 0<\/script>. The last step uses the definition of <script type=\"math\/tex;\">\\lambda <\/script>.) Thus, for each of the <script type=\"math\/tex;\">n<\/script> elements, the probability that the element is not covered is less than <script type=\"math\/tex;\">1\/(2n)<\/script>. By the naive union bound, the probability that one of the <script type=\"math\/tex;\">1+n<\/script> bad events happens is less than <script type=\"math\/tex;\">1\/2 + n\/(2n)=1<\/script>. Thus, with positive probability there are no bad events and <script type=\"math\/tex;\">\\tilde x<\/script> is a set cover of cost at most <script type=\"math\/tex;\">2\\lambda c\\cdot x^*<\/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>\n<\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000011\">Deconstructing the Set Cover existence proof to find <script type=\"math\/tex;\">Q<\/script><\/h1>\n<p> The argument above shows the existence of a set cover of cost <script type=\"math\/tex;\">O(\\log (n)c\\cdot x^*<\/script>). The next step is to apply the method of conditional probabilities to the existence proof. The resulting algorithm will consider each set <script type=\"math\/tex;\">s\\in S<\/script> in turn, and set <script type=\"math\/tex;\">\\tilde x_s<\/script> to either 0 or 1. Instead of setting <script type=\"math\/tex;\">\\tilde x_s<\/script> randomly based on <script type=\"math\/tex;\">x^*<\/script>, it will set <script type=\"math\/tex;\">\\tilde x_s<\/script> to keep the conditional probability of failure (defined with respect to the random experiment) below 1. <\/p>\n<p>Although the concept is simple, implementing it requires a careful calculation bounding the conditional probability of failure as the scheme proceeds. The original existence proof implicitly bounds the (unconditioned) probability of failure by the expectation of <\/p>\n<div id=\"a0000000012\" class=\"equation\"><script type=\"math\/tex; mode=display\">  Q = \\frac{c\\cdot \\tilde x}{2\\lambda c\\cdot x^*} {\\, {+}\\, }n_m  <\/script><\/div>\n<p> where <script type=\"math\/tex;\">n_m<\/script> is the number of elements left uncovered at the end that is, <script type=\"math\/tex;\">n_m<\/script> is the size of the set <script type=\"math\/tex;\"> U_m=\\{  e\\,  \\, |\\, \\,  \\forall s\\ni e.~  \\tilde x_s = 0 \\} <\/script>. <\/p>\n<p>The form of <script type=\"math\/tex;\">Q<\/script> mirrors the probabilistic proof in a systematic way.<a href=\"#a0000000013\" class=\"footnote\"><sup class=\"footnotemark\">1<\/sup><\/a> The first term in <script type=\"math\/tex;\">Q<\/script> comes from applying the Markov bound to bound the probability of the first bad event. It contributes at least 1 to <script type=\"math\/tex;\">Q<\/script> if the cost is too high. The second term <script type=\"math\/tex;\">n_m<\/script> counts the number of bad events of the second kind (uncovered elements). It contributes at least 1 to <script type=\"math\/tex;\">Q<\/script> if the coverage fails. Since failure implies <script type=\"math\/tex;\">Q\\ge 1<\/script>, by the Markov bound, the probability of failure is at most <script type=\"math\/tex;\">E[Q]<\/script>. Finally (as shown by calculation in the proof of the lemma) <script type=\"math\/tex;\">E[Q] \\lt 1<\/script>. <\/p>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000014\">Algorithm via the method of conditional probabilities<\/h1>\n<p> The algorithm will choose each set to keep the conditional expectation of <script type=\"math\/tex;\">Q<\/script>, given the choices made so far, below 1. Consider the state after the <script type=\"math\/tex;\">t<\/script>th choice. Let <script type=\"math\/tex;\">S_t=(s_1,s_2,\\ldots ,s_t)<\/script> denote the sets considered so far \u2014 for each set <script type=\"math\/tex;\">s\\in S_t<\/script>, the value of <script type=\"math\/tex;\">\\tilde x_s<\/script> has been set to 0 or 1; the values for the remaining sets have not yet been determined. The conditional expectation of <script type=\"math\/tex;\">Q<\/script>, given this state, is <\/p>\n<div id=\"a0000000015\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\phi _t ~ =~  \\frac{\\sum _{s\\in S_t} c_s \\tilde x_s + \\sum _{s\\not\\in S_t} c_s p_s}{2\\lambda c\\cdot x^*} ~ {\\, {+}\\, }~  \\sum _e \\prod _{s\\in S_t} (1-[e\\in s] \\tilde x_s) \\prod _{s\\not\\in S_t} (1-[e\\in s]p_s).  <\/script><\/div>\n<p>The algorithm will keep <script type=\"math\/tex;\">\\phi _t<\/script> (the conditional expectation of <script type=\"math\/tex;\">Q<\/script>) below 1 by setting each <script type=\"math\/tex;\">\\tilde x_{s_t}<\/script> to minimize the resulting value of <script type=\"math\/tex;\">\\phi _t<\/script>. Let <script type=\"math\/tex;\">s'=s_t<\/script> denote the <script type=\"math\/tex;\">t<\/script>th set. When the algorithm sets <script type=\"math\/tex;\">\\tilde x_{s'}<\/script>, each <script type=\"math\/tex;\">\\tilde x_s<\/script> for <script type=\"math\/tex;\">s\\in S_{t-1}<\/script> has already been set. Considered as a function of just <script type=\"math\/tex;\">\\tilde x_{s'}<\/script> (with all other quantities fixed) the quantity <script type=\"math\/tex;\">\\phi _t<\/script> is linear in <script type=\"math\/tex;\">\\tilde x_{s'}<\/script>. Let <script type=\"math\/tex;\">U= \\{ e \\, |\\, \\prod _{s\\in S_{t-1}} (1-[e\\in s] \\tilde x_s) = 1\\} <\/script> denote the set of elements not covered before <script type=\"math\/tex;\">s'<\/script> is considered. The coefficient of <script type=\"math\/tex;\">\\tilde x_{s'}<\/script> in <script type=\"math\/tex;\">\\phi _t<\/script> is <\/p>\n<div id=\"a0000000016\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\frac{c_{s'}}{2\\lambda c\\cdot x^*} {\\, {-}\\, }\\sum _{e\\in U}[e\\in s']\\prod _{s\\not\\in S_t} (1-[e\\in s]p_s).  <\/script><\/div>\n<p> To minimize <script type=\"math\/tex;\">\\phi _t<\/script>, if this coefficient is positive, then the algorithm sets <script type=\"math\/tex;\">\\tilde x_{s'}<\/script> to 0. Otherwise it sets <script type=\"math\/tex;\">\\tilde x_{s'}<\/script> to 1: <\/p>\n<table id=\"a0000000017\" 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> set system <script type=\"math\/tex;\">S<\/script>, universe <script type=\"math\/tex;\"> U<\/script>, cost vector <script type=\"math\/tex;\">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> set cover <script type=\"math\/tex;\">\\tilde x<\/script><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">1.<\/td>\n<td style=\"padding-left:0em\"> Compute min-cost fractional set cover <script type=\"math\/tex;\">x^*<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">2.<\/td>\n<td style=\"padding-left:0em\"> Take <script type=\"math\/tex;\">\\lambda \\leftarrow \\ln (2n)<\/script> and set <script type=\"math\/tex;\">p_s \\leftarrow \\max (\\lambda x^*_{s},1)<\/script> for each <script type=\"math\/tex;\">s<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:0em\"> For each <script type=\"math\/tex;\">s'\\in S<\/script> do: <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">4.<\/td>\n<td style=\"padding-left:1em\"> Let <script type=\"math\/tex;\">S \\leftarrow S - \\{ s'\\} <\/script>. <\/p>\n<div style=\"float:right;display:inline-block\"><em>...<script type=\"math\/tex;\">S<\/script> contains the not-yet-decided sets.<\/em><\/div>\n<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">5.<\/td>\n<td style=\"padding-left:1em\"> If\u00a0\u00a0 <script type=\"math\/tex;\">\\displaystyle \\frac{c_{s'}}{2\\lambda c\\cdot x^*} \\gt \\sum _{e\\in s'\\cap U} \\prod _{s\\in S, s\\ni e}(1-p_s) <\/script> <\/p>\n<div style=\"margin:0pt;padding:0pt;margin-bottom:5.5pt\"><\/div>\n<p>then set <script type=\"math\/tex;\">\\tilde x_s\\leftarrow 0<\/script>, else set <script type=\"math\/tex;\">\\tilde x_s\\leftarrow 1<\/script> and <script type=\"math\/tex;\"> U\\leftarrow U - s'<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">6.<\/td>\n<td style=\"padding-left:0em\"> Return <script type=\"math\/tex;\">\\tilde x<\/script>. <\/td>\n<\/tr>\n<\/table>\n<p>By ensuring <script type=\"math\/tex;\">\\phi _t \\le \\phi _{t-1}<\/script> at each step, the algorithm guarantees an outcome with <script type=\"math\/tex;\">Q\\le \\textrm{E}[Q]\\lt 1<\/script>, so that <script type=\"math\/tex;\">\\tilde x<\/script> has cost at most <script type=\"math\/tex;\">2\\ln (2n)c\\cdot x^*<\/script> and covers all elements: <\/p>\n<div id=\"a0000000018\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma <\/b> (rounding algorithm approximation guarantee).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>  The algorithm above returns a set cover <script type=\"math\/tex;\">\\tilde x<\/script> of cost at most <script type=\"math\/tex;\">2\\ln (2n)<\/script> times the minimum cost of any (fractional) set cover. <\/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=\"a0000000019\">Randomized rounding without solving the linear program<\/h1>\n<p> The algorithm\u2019s choice for each <script type=\"math\/tex;\">\\tilde x_{s'}<\/script> depends intrinsically on the individual values within <script type=\"math\/tex;\">x^*<\/script>. (For example, if each element <script type=\"math\/tex;\">e\\in s'<\/script> is contained in some not-yet-considered set <script type=\"math\/tex;\">s<\/script> with <script type=\"math\/tex;\">p_{s}=1<\/script>, then <script type=\"math\/tex;\">s'<\/script> will not be added to the cover even if <script type=\"math\/tex;\">p_{s'}=1<\/script>.) This dependence is not surprising, but it is not <em>inevitable<\/em>. By starting with a different randomized rounding scheme, the method of conditional probabilities can yield an algorithm that, in each step, makes a choice that is the same for any feasible <script type=\"math\/tex;\">x^*<\/script>. Thus, the algorithm can compute the approximate cover <script type=\"math\/tex;\">\\tilde x<\/script> without first computing <script type=\"math\/tex;\">x^*<\/script>. You can read more about that <a href=\"http:\/\/algnotes.info\/on\/obliv\">here<\/a>. <\/p>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000020\">Related<\/h2>\n<ul class=\"itemize\">\n<li>\n<p>Textbooks: \u00a0<span class=\"cite\">[<a href=\"#Vazirani03Approximation\">4<\/a>, Sec.14.2]<\/span>, \u00a0<span class=\"cite\">[<a href=\"#Motwani95\">1<\/a>, ch.4]<\/span>, \u00a0<span class=\"cite\">[<a href=\"#williamson2011design\">5<\/a>, ch.5]<\/span> (<a href=\"http:\/\/www.designofapproxalgs.com\/download.php\">online<\/a>) <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Randomized_rounding\">Randomized rounding (wikipedia)<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/obliv\">Randomized rounding without solving the linear program<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div>\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=\"Motwani95\">1<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;R+Motwani+&quot;+author:&quot;+P+Raghavan&quot;+intitle:&quot;+Randomized+Algorithms&quot;\">R.\u00a0Motwani and P.\u00a0Raghavan. <em>Randomized Algorithms<\/em>. Cambridge University Press, 1995. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Raghavan88Probabilistic\">2<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;P+Raghavan&quot;+intitle:&quot;+Probabilistic+construction+of+deterministic+algorithms+approximating+packing+integer+programs&quot;\">P.\u00a0Raghavan. Probabilistic construction of deterministic algorithms approximating packing integer programs. <em>J. Computer System Sciences<\/em>, 37(2):130\u2013143, Oct. 1988. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Raghavan87Randomized\">3<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;P+Raghavan+&quot;+author:&quot;+C+D++Thompson&quot;+intitle:&quot;+Randomized+rounding:+A+technique+for+provably+good+algorithms+and+algorithmic+proofs&quot;\">P.\u00a0Raghavan and C.\u00a0D. Thompson. Randomized rounding: A technique for provably good algorithms and algorithmic proofs. <em>Combinatorica<\/em>, 7:365\u2013374, 1987. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Vazirani03Approximation\">4<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;V+Vazirani&quot;+intitle:&quot;+Approximation+Algorithms&quot;\">V.\u00a0Vazirani. <em>Approximation Algorithms<\/em>. Springer Verlag, 2003. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"williamson2011design\">5<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;D+P++Williamson+&quot;+author:&quot;+D+B++Shmoys&quot;+intitle:&quot;+The+design+of+approximation+algorithms&quot;\">D.\u00a0P. Williamson and D.\u00a0B. Shmoys. <em>The design of approximation algorithms<\/em>. Cambridge University Press, 2011. (<a href=\"http:\/\/www.designofapproxalgs.com\">Available online<\/a>). <\/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=\"a0000000013\">(1) For an application of the Markov bound, (<script type=\"math\/tex;\">\\Pr [X\\ge {}c] {\\, {\\le }\\, }E[X]\/c<\/script>), the pessimistic estimator will be the conditional expectation of <script type=\"math\/tex;\">X\/(c\\textrm{E}[X])<\/script>. <br \/>(2) For an application of the naive union bound (<script type=\"math\/tex;\">\\Pr [A\\text{ or } B] {\\, {\\le }\\, }\\Pr [A] + \\Pr [B]<\/script>) the pessimistic estimator will be the sum of the pessimistic estimators of the individual events. <br \/>(3) For a bad event whose probability is computed (or estimated) directly, the pessimistic estimator will be the conditional probability (or the corresponding estimate). <\/li>\n<\/ol><\/div>\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Randomly rounding a fractional LP solution to an integer solution. The idea, introduced by Raghavan and Thompson in 1987, is to use the probabilistic method to round the solution of a linear program, converting it into an approximately optimal integer solution\u00a0[3]. It\u2019s a broadly useful technique. For many problems, randomized rounding yields algorithms with optimal [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8676,"menu_order":4,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1102","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/1102","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=1102"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/1102\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8676"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=1102"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}