{"id":8598,"date":"2014-12-07T10:45:45","date_gmt":"2014-12-07T18:45:45","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=8598"},"modified":"2026-09-30T09:15:09","modified_gmt":"2026-09-30T17:15:09","slug":"set-cover-fractional","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/obliv\/lagrangian\/set-cover-fractional\/","title":{"rendered":"Fractional Set Cover"},"content":{"rendered":"<div class=\"latex-file\">\n<div class=\"latex-document\">\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<p>Here we derive a <a href=\"http:\/\/algnotes.info\/on\/lagrangian-relaxation-example\">Lagrangian-relaxation algorithm<\/a> for fractional set cover. The derivation illustrates the use of random stopping times to handle weights in the cost function. <\/p>\n<p><!--more--><\/p>\n<div class=\"expandable\" id=\"a0000000002\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for problem definition\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for problem definition\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p> An instance is specified by a collection <script type=\"math\/tex;\">S<\/script> of subsets of a universe <script type=\"math\/tex;\">U<\/script> and a cost vector <script type=\"math\/tex;\">c<\/script>, where <script type=\"math\/tex;\">c_s\\ge 0<\/script> is the cost of set <script type=\"math\/tex;\">s\\in S<\/script>. A <em>(fractional set) cover<\/em> <script type=\"math\/tex;\">x<\/script> assigns a non-negative weight <script type=\"math\/tex;\">x_s<\/script> to each set <script type=\"math\/tex;\">s\\in S<\/script>. The <em>size<\/em> of the cover is <script type=\"math\/tex;\">|x| = \\sum _s x_s<\/script>. The <em>cost<\/em> of the cover is <script type=\"math\/tex;\">c\\cdot x = \\sum _s c_s x_s<\/script>. Its <em>coverage<\/em> is <script type=\"math\/tex;\">\\min _{e\\in U} x(e)<\/script>. Its <em>coverage of element <script type=\"math\/tex;\">e<\/script><\/em> is <script type=\"math\/tex;\">x(e) = \\sum _{s\\ni e} x_e<\/script>. The cover is <em>feasible<\/em> if its coverage is at least 1. The goal is to find a minimum size feasible cover. <\/p>\n<p>The cover is an <em>integer cover<\/em> if each <script type=\"math\/tex;\">x_s<\/script> is an integer. <\/p>\n<\/div>\n<\/details>\n<\/div>\n<p>A fractional cover <script type=\"math\/tex;\">x<\/script> is a <em><script type=\"math\/tex;\">C<\/script>-multicover<\/em> if its coverage of every element is at least <script type=\"math\/tex;\">C<\/script>. <\/p>\n<p>We use <script type=\"math\/tex;\">C<\/script>-multicovers with <script type=\"math\/tex;\">C\\gt 1<\/script> as a stepping stone for finding fractional set covers. We apply the method of conditional probabilities to a randomized-rounding scheme to derive the following algorithm to find an approximately minimum-cost integer <script type=\"math\/tex;\">C<\/script>-multicover. Then we\u2019ll use that algorithm, and scaling, to compute an approximately minimum-cost fractional set cover. <\/p>\n<table id=\"a0000000003\" 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> Collection <script type=\"math\/tex;\">S<\/script> of subsets of <script type=\"math\/tex;\">U<\/script>, cost vector <script type=\"math\/tex;\">c<\/script>, coverage <script type=\"math\/tex;\">C<\/script>, and <script type=\"math\/tex;\">\\varepsilon \\in (0,1)<\/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 cover <script type=\"math\/tex;\">\\tilde x<\/script> of near-minimum cost with coverage at least <script type=\"math\/tex;\">C<\/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 x_s=0<\/script> for every set <script type=\"math\/tex;\">s\\in S<\/script>. Recall that <script type=\"math\/tex;\">\\tilde x(e)<\/script> denotes <script type=\"math\/tex;\">\\sum _{s\\ni e} \\tilde x_s<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">2.<\/td>\n<td style=\"padding-left:0em\"> While <script type=\"math\/tex;\">\\tilde x<\/script>\u2019s coverage is less than <script type=\"math\/tex;\">C<\/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 set <script type=\"math\/tex;\">s\\in S<\/script> maximizing <script type=\"math\/tex;\">\\sum _{e\\ni s} (1-\\varepsilon )^{\\tilde x(e)} \/ c_s<\/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 x_s<\/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 x<\/script>. <\/td>\n<\/tr>\n<\/table>\n<p>Let <script type=\"math\/tex;\">n=|U|<\/script> be the number of elements. <\/p>\n<div id=\"a0000000004\" class=\"my-theorem latex-paragraph latex-thm\">\n<div class=\"latex-paragraph-heading\">   <b>Theorem <\/b> (performance guarantee).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Assume <script type=\"math\/tex;\">C<\/script> is an integer. For any <script type=\"math\/tex;\">\\varepsilon \\in (0,1)<\/script> such that <script type=\"math\/tex;\">C \\ge \\ln (n)\/\\varepsilon ^2<\/script>, the algorithm returns an integer cover <script type=\"math\/tex;\">\\tilde x<\/script> of coverage <script type=\"math\/tex;\">C<\/script> whose cost <script type=\"math\/tex;\">|c\\cdot \\tilde x|<\/script> is at most <script type=\"math\/tex;\">c\\cdot x^*\/(1-2\\varepsilon )<\/script>, where <script type=\"math\/tex;\">x^*<\/script> is any minimum-cost cover with coverage <script type=\"math\/tex;\">C<\/script>. <\/p>\n<\/div><\/div>\n<p>We prove the theorem by applying the method of conditional probabilities to the following rounding scheme. <\/p>\n<p>Fix any fractional cover <script type=\"math\/tex;\">x<\/script> with coverage <script type=\"math\/tex;\">C<\/script>. <\/p>\n<blockquote class=\"quote\"><p><em> Initialize <script type=\"math\/tex;\">\\tilde x_s = 0<\/script> for all <script type=\"math\/tex;\">s\\in S<\/script>. <br \/>Randomly sample sets independently from the distribution <script type=\"math\/tex;\">x\/|x|<\/script>; <br \/>with each sample <script type=\"math\/tex;\">s<\/script>, increment <script type=\"math\/tex;\">\\tilde x_s<\/script>. <br \/>When <script type=\"math\/tex;\">\\tilde x<\/script> achieves coverage <script type=\"math\/tex;\">C<\/script>, stop and return <script type=\"math\/tex;\">\\tilde x<\/script>.<\/em> <\/p><\/blockquote>\n<p>To analyze the rounding scheme, we use the following variant of the Chernoff bound. Suppose a random process starts in some fixed start state <script type=\"math\/tex;\">S_0<\/script>, then goes through a random sequence of states <script type=\"math\/tex;\">S_1,S_2,S_3,\\ldots <\/script>. As it goes, it maintains <script type=\"math\/tex;\">n<\/script> values (each initially zero). In state <script type=\"math\/tex;\">S_t<\/script>, each of the <script type=\"math\/tex;\">n<\/script> values <script type=\"math\/tex;\">y^t(i)<\/script> is determined. (In our setting, the state <script type=\"math\/tex;\">S_t<\/script> consists of the first <script type=\"math\/tex;\">t<\/script> samples. Value <script type=\"math\/tex;\">y^t(e)<\/script> represents the coverage of element <script type=\"math\/tex;\">e<\/script> by those samples.) <\/p>\n<div id=\"a0000000005\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma <\/b> (Chernoff variant).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Let <script type=\"math\/tex;\">T<\/script> be a stopping time for the system. Fix <script type=\"math\/tex;\">\\varepsilon \\in (0,1)<\/script>, and <script type=\"math\/tex;\">\\mu \\gt 0<\/script>. Assume that, at each time step, each of the <script type=\"math\/tex;\">n<\/script> counters increases by at most 1 and by at least <script type=\"math\/tex;\">\\mu <\/script> in expectation. Then the expectation of the minimum of the values at time <script type=\"math\/tex;\">T<\/script> is at least <script type=\"math\/tex;\">(1-\\varepsilon )\\big(\\mu \\,  \\textrm{E}[T] \\, -\\,  \\varepsilon ^{-1}\\ln n\\big)<\/script>. <\/p>\n<\/div><\/div>\n<div class=\"expandable\" id=\"a0000000006\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for proof of lemma\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for proof of lemma\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p> Given the state <script type=\"math\/tex;\">S_t<\/script> after <script type=\"math\/tex;\">t<\/script> samples, define <script type=\"math\/tex;\">\\phi _t ~ =~  \\log _{1-\\varepsilon } \\sum _{j=1}^n \\big(1-\\varepsilon \\big)^{\\textstyle y^t(j)}. <\/script> <\/p>\n<p>Note that <script type=\"math\/tex;\">\\phi _t<\/script> is a lower bound on the minimum of the values at time <script type=\"math\/tex;\">t<\/script>: <\/p>\n<div id=\"a0000000007\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\phi _t ~ \\le ~  \\log _{1-\\varepsilon } \\max _j\\,  (1-\\varepsilon )^{y^t(j)} ~ =~  \\min _j y^t(j).  <\/script><\/div>\n<p> After the first <script type=\"math\/tex;\">t<\/script> steps, let <script type=\"math\/tex;\">\\omega _j<\/script> denote the term for <script type=\"math\/tex;\">j<\/script> in the sum in <script type=\"math\/tex;\">\\phi _t<\/script>, so <script type=\"math\/tex;\">\\phi _t = \\log _{1-\\varepsilon } \\sum _{j=1}^n \\omega _j<\/script>. <\/p>\n<p><div style=\"margin:0pt;padding:0pt;margin-bottom:6px\"><\/div>\n<\/p>\n<p>Let <script type=\"math\/tex;\">\\delta _j = y^{t+1}(j) - y^t(j)<\/script> denote the increase in the <script type=\"math\/tex;\">j<\/script>th counter in the next step. By calculation, using that <script type=\"math\/tex;\">\\delta _j \\in [0,1]<\/script> and <script type=\"math\/tex;\">\\log _{1-\\varepsilon } 1-\\varepsilon z \\ge (1-\\varepsilon )z<\/script>, <\/p>\n<div id=\"a0000000008\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\phi _{t+1} - \\phi _t ~ =~  \\log _{1-\\varepsilon }\\frac{\\sum _j (1-\\varepsilon )^{\\delta _j}\\omega _j}{\\sum _j \\omega _j} ~ \\ge ~  \\log _{1-\\varepsilon }\\frac{\\sum _j (1-\\varepsilon \\delta _j)\\omega _j}{\\sum _j \\omega _j}  <\/script><\/div>\n<div id=\"eq:1\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation}  \\label{eq:1} ~ =~  \\log _{1-\\varepsilon } \\Big( 1 - \\varepsilon \\frac{\\sum _j \\delta _j\\omega _j}{\\sum _j \\omega _j}\\Big) ~ \\ge ~  (1-\\varepsilon ) \\frac{\\sum _j \\delta _j\\omega _j}{\\sum _j \\omega _j}. \\end{equation}<\/script><\/div>\n<p> For any <script type=\"math\/tex;\">j<\/script>, the expectation of <script type=\"math\/tex;\">\\delta _j<\/script> is at least <script type=\"math\/tex;\">\\mu <\/script>, so, by\u00a0(\\ref{eq:1}), the expectation of <script type=\"math\/tex;\">\\phi _{t+1}-\\phi _t<\/script>, given <script type=\"math\/tex;\">\\phi _t<\/script> is <\/p>\n<div id=\"a0000000009\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\textrm{E}[\\phi _{t+1}-\\phi _t ~ |~  \\phi _t] ~ \\ge ~  (1-\\varepsilon )\\mu .  <\/script><\/div>\n<p> Thus, in expectation, <script type=\"math\/tex;\">\\phi <\/script> increases by at least <script type=\"math\/tex;\">(1-\\varepsilon )\\mu <\/script> in each iteration. By Wald\u2019s equation, <\/p>\n<div id=\"a0000000010\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\textrm{E}[\\phi _T] ~ \\ge ~  \\phi _0 + (1-\\varepsilon )\\mu \\,  \\textrm{E}[T] ~ \\ge ~  (1-\\varepsilon )\\big({-\\varepsilon }^{-1}\\ln n + \\mu \\,  \\textrm{E}[T]\\big).  <\/script><\/div>\n<p> Since <script type=\"math\/tex;\">\\min _j y^T(j)\\ge \\phi _T<\/script>, the lemma follows. <\/p>\n<\/div>\n<\/details>\n<\/div>\n<p>(Note: there is a <a href=\"http:\/\/algnotes.info\/on\/chernoff-wald\/#Bound_on_expected_deviation_below_the_mean\">tighter<\/a> version of this lemma.) <\/p>\n<p>Now we analyze the rounding scheme. <\/p>\n<div id=\"a0000000011\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma <\/b> (rounding scheme).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Assume <script type=\"math\/tex;\">C<\/script> is an integer. Fix any <script type=\"math\/tex;\">\\varepsilon \\in (0,1)<\/script> such that <script type=\"math\/tex;\">C\\ge \\ln (n)\/\\varepsilon ^2<\/script>. Let <script type=\"math\/tex;\">x<\/script> be any fractional cover with coverage at least <script type=\"math\/tex;\">C<\/script>. Given <script type=\"math\/tex;\">x<\/script>, the rounding scheme returns an integer cover <script type=\"math\/tex;\">\\tilde x<\/script> with coverage at least <script type=\"math\/tex;\">C<\/script> and whose expected cost is at most <script type=\"math\/tex;\">c\\cdot x\/(1-2\\varepsilon )<\/script>. <\/p>\n<\/div><\/div>\n<div class=\"expandable\" id=\"a0000000012\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for proof of lemma\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for proof of lemma\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p> Since <script type=\"math\/tex;\">C<\/script> is an integer, and the rounding scheme stops sampling when <script type=\"math\/tex;\">\\tilde x<\/script> has coverage at least <script type=\"math\/tex;\">C<\/script>, the final cover <script type=\"math\/tex;\">\\tilde x<\/script> inevitably has coverage exactly <script type=\"math\/tex;\">C<\/script>. <\/p>\n<p>By Wald\u2019s equation, the total expected cost of all the samples is the expected number of samples, <script type=\"math\/tex;\">\\textrm{E}[T]<\/script>, times the expected cost per sample, which is <script type=\"math\/tex;\">c\\cdot x\/|x|<\/script>. To finish we show that <script type=\"math\/tex;\">\\textrm{E}[T]<\/script> is at most <script type=\"math\/tex;\">|x|\/(1-2\\varepsilon )<\/script>. <\/p>\n<p>For any element <script type=\"math\/tex;\">e\\in U<\/script>, with each sample, the probability that the sampled set contains <script type=\"math\/tex;\">e<\/script> is <script type=\"math\/tex;\">\\sum _{s\\ni e} x_s \/|x|<\/script>, which, since <script type=\"math\/tex;\">x<\/script> has coverage <script type=\"math\/tex;\">C<\/script>, is at least <script type=\"math\/tex;\">\\mu = C\/|x|<\/script>. Thus, with each sample, the expected increase in the coverage of each element is at least <script type=\"math\/tex;\">\\mu <\/script>. Applying the Chernoff variant to the coverages of the <script type=\"math\/tex;\">n<\/script> elements, the expectation of the coverage of any element at termination is at least <script type=\"math\/tex;\">(1-\\varepsilon )(\\mu \\textrm{E}[T] \\, -\\,  \\varepsilon ^{-1}\\ln n)<\/script>. Since the coverage at termination is inevitably <script type=\"math\/tex;\">C<\/script>, <\/p>\n<div id=\"a0000000013\" class=\"equation\"><script type=\"math\/tex; mode=display\">  C~  \\ge ~  (1-\\varepsilon )(\\mu \\textrm{E}[T] \\, -\\,  \\varepsilon ^{-1}\\ln n) ~  =~  (1-\\varepsilon )(\\textrm{E}[T] C\/|x| \\, -\\,  \\varepsilon ^{-1}\\ln n).  <\/script><\/div>\n<p> Rewriting and using the assumption on <script type=\"math\/tex;\">C<\/script>, <\/p>\n<div id=\"a0000000014\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\frac{(1-\\varepsilon )\\textrm{E}[T]}{|x|} ~ \\le ~  1 + \\frac{\\ln n}{\\varepsilon C} ~ \\le ~  1 + \\varepsilon .  <\/script><\/div>\n<p> This implies <script type=\"math\/tex;\">\\textrm{E}[T]\/|x| \\le (1+\\varepsilon )\/(1-\\varepsilon ) \\lt 1\/(1-2\\varepsilon )<\/script>. <\/p>\n<\/div>\n<\/details>\n<\/div>\n<p>Next, to prove the theorem, we describe how applying the method of conditional probabilities to the rounding scheme gives the algorithm. <\/p>\n<div class=\"expandable\" id=\"a0000000015\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for proof of theorem\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for proof of theorem\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p> The algorithm will emulate the rounding scheme, but instead of choosing each set <script type=\"math\/tex;\">s<\/script> randomly, it will choose each set so as to keep the conditional expectation of the final cost below <script type=\"math\/tex;\">c\\cdot x\/(1-2\\varepsilon )<\/script>. <\/p>\n<p>Recall that <script type=\"math\/tex;\">T<\/script> is the total number of samples, and, for each <script type=\"math\/tex;\">t=0,\\ldots ,T<\/script>, the \u201cstate\u201d <script type=\"math\/tex;\">S_t<\/script> consists of the sequence of the first <script type=\"math\/tex;\">t<\/script> samples. To get the pessimistic estimator, we first bound the expected number of remaining samples, <script type=\"math\/tex;\">\\textrm{E}[T-t~ | S_t]<\/script>, given the state after <script type=\"math\/tex;\">t<\/script> samples. <\/p>\n<p>Define <script type=\"math\/tex;\">\\mu =C\/|x|<\/script> as in the proof of the second lemma, and <script type=\"math\/tex;\">\\phi _t<\/script> as in the proof of the Chernoff variant. As shown the proof of the variant, with each sample, <script type=\"math\/tex;\">\\phi _t<\/script> decreases in expectation by at least <script type=\"math\/tex;\">(1-\\varepsilon )\\mu <\/script>. But <script type=\"math\/tex;\">\\phi _T<\/script> is finally at least <script type=\"math\/tex;\">C<\/script>. So, by Wald\u2019s equation, the expected number of samples remaining, <script type=\"math\/tex;\">\\textrm{E}[T-t~ |~ \\phi _t]<\/script>, is at most <script type=\"math\/tex;\">(\\phi _t - C) \/ (1-\\varepsilon )\\mu <\/script>. <\/p>\n<p>Given <script type=\"math\/tex;\">S_t<\/script>, the expected final cost is the cost of the sets in <script type=\"math\/tex;\">S_t<\/script> plus the expected cost of the remaining sets. By Wald\u2019s equation (since each sample costs <script type=\"math\/tex;\">c\\cdot x\/|x|<\/script> in expectation) the expected cost of the remaining sets is <script type=\"math\/tex;\">\\textrm{E}[T-t\\, |\\, \\phi _t]<\/script> times <script type=\"math\/tex;\">c\\cdot x\/|x|<\/script>. Substituting in the bound on <script type=\"math\/tex;\">\\textrm{E}[T-t\\, |\\, \\phi _t]<\/script> from the previous paragraph, the expected final cost, given <script type=\"math\/tex;\">S_t<\/script>, is at most <\/p>\n<div id=\"a0000000016\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\psi _t ~ =~  c\\cdot \\tilde x + \\frac{c\\cdot x}{|x|}\\cdot \\frac{C - \\phi _t}{(1-\\varepsilon )\\mu }.  <\/script><\/div>\n<p>The algorithm will choose each set to keep this pessimistic estimator from increasing. Given <script type=\"math\/tex;\">\\psi _t<\/script>, if it chooses the next set to be <script type=\"math\/tex;\">s<\/script>, using Bound\u00a0(\\ref{eq:1}) from the proof of the Chernoff variant, the increase <script type=\"math\/tex;\">\\psi _{t+1}-\\psi _t<\/script> in the pessimistic estimator is <\/p>\n<div id=\"a0000000017\" class=\"equation\"><script type=\"math\/tex; mode=display\">  c_s - \\frac{c\\cdot x}{|x| (1-\\varepsilon )\\mu } \\,  (\\phi _{t+1}-\\phi _t) ~ \\le ~  c_s - \\frac{c\\cdot x}{|x|\\mu }\\cdot \\frac{\\sum _{e\\in s} \\omega _e}{\\sum _{e\\in U}\\omega _e},  <\/script><\/div>\n<p> where <script type=\"math\/tex;\">\\omega _e = (1-\\varepsilon )^{\\tilde x^t(e)}<\/script> and <script type=\"math\/tex;\">\\mu =C\/|x|<\/script>. <\/p>\n<p>If <script type=\"math\/tex;\">s<\/script> is chosen randomly, then (since <script type=\"math\/tex;\">\\Pr [e\\in s] \\ge \\mu <\/script> for all <script type=\"math\/tex;\">e<\/script> and <script type=\"math\/tex;\">\\textrm{E}[c_s] = c\\cdot x\/|x|<\/script>) the expectation of the right-hand-side above is non-positive. Thus, some choice of set <script type=\"math\/tex;\">s<\/script> makes it non-positive. Rearranging terms to gather on the left those that depend on <script type=\"math\/tex;\">s<\/script>, it is non-positive iff <\/p>\n<div id=\"a0000000018\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\frac{\\sum _{e\\in s} \\omega _e}{c_s} ~ \\ge ~  \\frac{C\\sum _{e\\in U} \\omega _e}{c\\cdot x}.  <\/script><\/div>\n<p> Since the algorithm chooses <script type=\"math\/tex;\">s<\/script> to maximize the left-hand side above, it keeps the pessimistic estimator from increasing. Thus, the algorithm keeps the conditional expectation of the final cost below <script type=\"math\/tex;\">c\\cdot x\/(1-\\varepsilon )<\/script>. This proves the theorem. <\/p>\n<\/div>\n<\/details>\n<\/div>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000019\">Finding a near-optimal fractional set cover<\/h2>\n<p>Given an instance <script type=\"math\/tex;\">S<\/script> and <script type=\"math\/tex;\">c<\/script>, and an arbitrary <script type=\"math\/tex;\">\\varepsilon \\in (0,1\/2)<\/script>, one can also use the algorithm to compute a <script type=\"math\/tex;\">1\/(1-2\\varepsilon )<\/script>-approximate fractional (non-integer) set cover, as follows. <\/p>\n<p>Define coverage <script type=\"math\/tex;\">C<\/script> to be <script type=\"math\/tex;\">C = \\lceil 2(1-\\varepsilon )\\ln (n)\/\\varepsilon ^2\\rceil <\/script>. Run the algorithm with coverage <script type=\"math\/tex;\">C<\/script> to find a <script type=\"math\/tex;\">1\/(1-2\\varepsilon )<\/script>-approximate integer <script type=\"math\/tex;\">C<\/script>-multicover <script type=\"math\/tex;\">\\tilde x<\/script>, then scale <script type=\"math\/tex;\">\\tilde x<\/script> by <script type=\"math\/tex;\">1\/C<\/script> to obtain the fractional set cover <script type=\"math\/tex;\">x=\\tilde x\/C<\/script> for the original problem, with coverage 1. The cover <script type=\"math\/tex;\">x<\/script> will have cost at most <script type=\"math\/tex;\">1\/(1-2\\varepsilon )<\/script> times the minimum cost of any fractional set cover (with coverage 1). <\/p>\n<\/div>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000020\">Running time<\/h2>\n<p> The number of iterations for this algorithm can be large, even when <script type=\"math\/tex;\">C<\/script> is small. (Consider an example with <script type=\"math\/tex;\">C=1<\/script> and <script type=\"math\/tex;\">\\varepsilon =1\/2<\/script>, and with two sets <script type=\"math\/tex;\">s=\\{ e\\} <\/script> and <script type=\"math\/tex;\">s'=\\{ e'\\} <\/script>, where <script type=\"math\/tex;\">c_s<\/script> equals <script type=\"math\/tex;\">1<\/script> and <script type=\"math\/tex;\">c_{s'}<\/script> is arbitrarily large. The algorithm will choose set <script type=\"math\/tex;\">s<\/script> about <script type=\"math\/tex;\">\\log _2 c_{s'}<\/script> times before choosing <script type=\"math\/tex;\">s'<\/script>.) <\/p>\n<p>As discussed in other notes here, it is possible to modify the algorithm to guarantee a polynomial running time. <\/p>\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=\"a0000000021\">Related<\/h1>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/stopping-time-chernoff\">stopping-time Chernoff bounds<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/lagrangian\">Summary of notes on Lagrangian relaxation<\/a> <\/p>\n<\/li>\n<\/ul>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000022\">Background<\/h2>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/set-cover-unweighted-fractional\">Algorithm for unweighted fractional set cover<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/chernoff\">Chernoff bound<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/lagrangian-relaxation-discussion\">Discussion of Lagrangian-relaxation algorithms<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/obliv\">About deriving greedy and Lagrangian-relaxation algorithms<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div><\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Here we derive a Lagrangian-relaxation algorithm for fractional set cover. The derivation illustrates the use of random stopping times to handle weights in the cost function.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8645,"menu_order":6,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8598","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8598","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=8598"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8598\/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=8598"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}