{"id":8600,"date":"2014-12-07T10:46:02","date_gmt":"2014-12-07T18:46:02","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=8600"},"modified":"2026-09-30T09:15:14","modified_gmt":"2026-09-30T17:15:14","slug":"set-cover-unweighted-fractional","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/obliv\/lagrangian\/set-cover-unweighted-fractional\/","title":{"rendered":"Fractional Set Cover \/ unweighted"},"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 unweighted fractional set cover. <\/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>. 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>. 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>. Its <em>minimum coverage<\/em> is <script type=\"math\/tex;\">\\min _{e\\in U} x(e)<\/script>. The cover is <em>feasible<\/em> if its minimum 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\u2019ll first apply the method of conditional probabilities to a randomized-rounding scheme to derive the following algorithm to find an approximately minimum-size integer <script type=\"math\/tex;\">C<\/script>-multicover. <\/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>, 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 size with minimum 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 the minimum 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)}<\/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> For any <script type=\"math\/tex;\">\\varepsilon \\in (0,1)<\/script>, assuming <script type=\"math\/tex;\">C \\ge 2\\ln (n)\/(1-\\varepsilon )\\varepsilon ^2<\/script>, the algorithm returns an integer cover <script type=\"math\/tex;\">\\tilde x<\/script> of minimum coverage <script type=\"math\/tex;\">C<\/script> whose size <script type=\"math\/tex;\">|\\tilde x|<\/script> is at most <script type=\"math\/tex;\">\\lceil |x^*|\/(1-\\varepsilon )\\rceil <\/script>, where <script type=\"math\/tex;\">x^*<\/script> is any minimum-size cover with minimum coverage <script type=\"math\/tex;\">C<\/script>. <\/p>\n<\/div><\/div>\n<p>The algorithm and the derivation are essentially from\u00a0<span class=\"cite\">[<a href=\"#Young95Randomized\">1<\/a>]<\/span>. <\/p>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000005\">Deriving the algorithm<\/h2>\n<p> We derive the algorithm by applying <a href=\"http:\/\/algnotes.info\/on\/method-of-conditional-probabilities\">the method of conditional probabilities<\/a> to the following rounding scheme. Fix any fractional cover <script type=\"math\/tex;\">x<\/script> with minimum coverage <script type=\"math\/tex;\">C<\/script>. <\/p>\n<blockquote class=\"quote\"><p><em> Fix <script type=\"math\/tex;\">N=\\lceil |x|\/(1-\\varepsilon ) \\rceil <\/script>. <br \/>Randomly sample <script type=\"math\/tex;\">N<\/script> sets independently from the distribution <script type=\"math\/tex;\">x\/|x|<\/script>. <br \/>Return the integer cover <script type=\"math\/tex;\">\\tilde x<\/script> such that, for each set <script type=\"math\/tex;\">s\\in S<\/script>, the weight <script type=\"math\/tex;\">\\tilde x_s<\/script> of <script type=\"math\/tex;\">s<\/script> equals the number of times <script type=\"math\/tex;\">s<\/script> was sampled.<\/em> <\/p><\/blockquote>\n<div id=\"a0000000006\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b \"=\"&quot;\">Lemma.<\/b>   <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>Let <script type=\"math\/tex;\">x<\/script> be any fractional cover with minimum coverage at least <script type=\"math\/tex;\">C<\/script>. For any <script type=\"math\/tex;\">\\varepsilon \\in (0,1)<\/script> such that <script type=\"math\/tex;\">C\\ge 2(1-\\varepsilon )\\ln (m)\\varepsilon ^2<\/script>, given <script type=\"math\/tex;\">x<\/script>, with positive probability, the rounding scheme returns an integer cover <script type=\"math\/tex;\">\\tilde x<\/script> of size <script type=\"math\/tex;\">N=\\lceil |x|\/(1-\\varepsilon ) \\rceil <\/script> whose minimum coverage is at least <script type=\"math\/tex;\">C<\/script>. <\/p>\n<\/div><\/div>\n<div class=\"expandable\" id=\"a0000000007\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for proof\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for proof\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p> The size of the cover <script type=\"math\/tex;\">\\tilde x<\/script> is inevitably <script type=\"math\/tex;\">N<\/script>, because each of the <script type=\"math\/tex;\">N<\/script> samples increases the size by 1. Next we bound the coverage. <\/p>\n<p>Fix any element <script type=\"math\/tex;\">e\\in U<\/script>. With each of the <script type=\"math\/tex;\">N<\/script> samples, 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 minimum coverage <script type=\"math\/tex;\">C<\/script>, is at least <script type=\"math\/tex;\">C\/|x|<\/script>. Thus, the expectation of <script type=\"math\/tex;\">\\tilde x(s)<\/script> is at least <script type=\"math\/tex;\">N\\cdot C\/|x| \\ge C\/(1-\\varepsilon )<\/script>. <\/p>\n<p>Consider <script type=\"math\/tex;\">\\tilde x(s)<\/script> as the sum <script type=\"math\/tex;\">\\sum _{t=1}^N [e \\in s_t]<\/script> of <script type=\"math\/tex;\">N<\/script> independent random indicator variables (the <script type=\"math\/tex;\">t<\/script>th of which is 1 the <script type=\"math\/tex;\">t<\/script>th sampled set <script type=\"math\/tex;\">s_t<\/script> contains <script type=\"math\/tex;\">e<\/script>, and zero otherwise). By <a href=\"http:\/\/algnotes.info\/on\/chernoff\">the Chernoff bound<\/a>, the probability that <script type=\"math\/tex;\">\\tilde x(e)<\/script> is less than <script type=\"math\/tex;\">C=(1-\\varepsilon ) C\/(1-\\varepsilon )<\/script> is less than <\/p>\n<div id=\"a0000000008\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\exp (-\\varepsilon ^2 (C\/(1-\\varepsilon ))\/2) ~ \\le ~  1\/n.  <\/script><\/div>\n<p> (The inequality follows from the assumption on <script type=\"math\/tex;\">C<\/script>.) <\/p>\n<p>Thus, the expected number of elements <script type=\"math\/tex;\">e<\/script> with <script type=\"math\/tex;\">\\tilde x(e) \\lt C<\/script> is less than 1. So, with positive probability, <script type=\"math\/tex;\">\\tilde x<\/script> has minimum coverage at least <script type=\"math\/tex;\">C<\/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=\"a0000000009\" 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> Say that an element <script type=\"math\/tex;\">e<\/script> is \u201cundercovered\u201d (when the rounding scheme finishes) if <script type=\"math\/tex;\">\\tilde x(e) \\lt C<\/script>. 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 number of undercovered elements below 1. <\/p>\n<p>Recall that <script type=\"math\/tex;\">s_t<\/script> is the <script type=\"math\/tex;\">t<\/script>th sampled set. In using the Chernoff bound for each element, the analysis of the rounding scheme implicitly bounds the number of undercovered elements by <\/p>\n<div id=\"a0000000010\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\Phi ~ =~  \\sum _{e\\in U} \\frac{(1-\\varepsilon )^{\\tilde x(e)} }{ (1-\\varepsilon )^{(1-\\varepsilon )C\/(1-\\varepsilon ) } } ~ =~  \\sum _{e\\in U} \\frac{ \\prod _{t=1}^N (1-\\varepsilon [e \\in s_t])}{ (1-\\varepsilon )^{ C } },  <\/script><\/div>\n<p> then shows the expectation of <script type=\"math\/tex;\">\\Phi <\/script> is at most 1. <\/p>\n<p>(To understand where <script type=\"math\/tex;\">\\Phi <\/script> comes from requires a good understanding of <a href=\"http:\/\/algnotes.info\/on\/chernoff-proof\">the proof of the Chernoff bound<\/a>. Here are the essentials. For each undercovered element <script type=\"math\/tex;\">e<\/script>, the term for <script type=\"math\/tex;\">e<\/script> in the sum is at least 1, so the number of undercovered elements is at most <script type=\"math\/tex;\">\\Phi <\/script>. <a href=\"http:\/\/algnotes.info\/on\/chernoff-proof\">The proof of the Chernoff bound<\/a> shows that the expectation of the term for each <script type=\"math\/tex;\">e<\/script> in <script type=\"math\/tex;\">\\Phi <\/script> is less than <script type=\"math\/tex;\">\\exp (-\\varepsilon ^2 (C\/(1-\\varepsilon ))\/ 2)<\/script>. By the assumption on <script type=\"math\/tex;\">C<\/script> in the analysis of the rounding scheme, this is at most <script type=\"math\/tex;\">1\/n<\/script>, so the expectation of <script type=\"math\/tex;\">\\Phi <\/script> is less than 1.) <\/p>\n<p>Since <script type=\"math\/tex;\">\\Phi <\/script> is an upper bound on the number of undercovered elements, to keep the conditional expectation of the number of undercovered elements below 1, it suffices to keep the conditional expectation of <script type=\"math\/tex;\">\\Phi <\/script> below 1. This is what the algorithm will do. <\/p>\n<p>Fix any <script type=\"math\/tex;\">t\\in \\{ 0,1,\\ldots ,N\\} <\/script>. Recall that, for any element <script type=\"math\/tex;\">e<\/script>, <script type=\"math\/tex;\">\\Pr [e\\in s_t] \\ge C\/|x|<\/script>. One <a href=\"http:\/\/algnotes.info\/on\/chernoff-proof\">pessimistic estimator<\/a> for the conditional expectation of <script type=\"math\/tex;\">\\Phi <\/script>, given the first <script type=\"math\/tex;\">t<\/script> elements, is <\/p>\n<div id=\"eq:1\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation}  \\label{eq:1} \\phi _t ~ =~  \\sum _{e\\in U} \\frac{ \\prod _{r=1}^t (1-\\varepsilon [e\\in s_t]) \\times \\prod _{r=t+1}^N (1-\\varepsilon C\/|x|) }{ (1-\\varepsilon )^{ C } }. \\end{equation}<\/script><\/div>\n<p>To reach a successful outcome, it suffices for the algorithm to choose each element to ensure that <script type=\"math\/tex;\">\\phi _t<\/script> does not increase, so that <script type=\"math\/tex;\">\\Phi = \\phi _N \\le \\phi _{N-1} \\le \\cdots \\le \\phi _0 \\lt 1<\/script>. How can it choose <script type=\"math\/tex;\">e_{t+1}<\/script> to ensure <script type=\"math\/tex;\">\\phi _{t+1} \\le \\phi _t<\/script>? Letting <script type=\"math\/tex;\">\\omega ^s_t<\/script> denote the term for <script type=\"math\/tex;\">s<\/script> in <script type=\"math\/tex;\">\\phi _t<\/script> (so <script type=\"math\/tex;\">\\phi _t = \\sum _s \\omega ^s_t<\/script>) if the algorithm takes some set <script type=\"math\/tex;\">s<\/script> to be <script type=\"math\/tex;\">s_{t+1}<\/script>, then <\/p>\n<div id=\"a0000000011\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\phi _{t+1} ~ =~  \\sum _{e\\in U} \\frac{ 1-\\varepsilon [e\\in s] }{ 1-\\varepsilon C\/|x|} \\omega ^s_t.  <\/script><\/div>\n<p> If <script type=\"math\/tex;\">s<\/script> were chosen randomly as in the sampling scheme, then (for any element <script type=\"math\/tex;\">e<\/script>), <script type=\"math\/tex;\">\\Pr [e\\in s] \\ge C\/|x|<\/script>, so (by inspection above) the expectation of <script type=\"math\/tex;\">\\phi _{t+1}<\/script> would be at most <script type=\"math\/tex;\">\\phi _t<\/script>. <\/p>\n<p>So, to ensure <script type=\"math\/tex;\">\\phi _{t+1}\\le \\phi _t<\/script>, it suffices to choose <script type=\"math\/tex;\">s<\/script> to minimize <script type=\"math\/tex;\">\\phi _{t+1}<\/script>. Inspecting\u00a0(\\ref{eq:1}), the second product in the numerator, and the denominator, can be ignored (not only are they the same for all elements <script type=\"math\/tex;\">e<\/script>, they are also independent of all choices so far). By calculation (factoring the irrelevant terms out and simplifying), choosing set <script type=\"math\/tex;\">s<\/script> minimizes <script type=\"math\/tex;\">\\phi '_{t+1}<\/script> if and only if it maximizes <\/p>\n<div id=\"a0000000012\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\sum _{e\\ni s} (1-\\varepsilon )^{\\textstyle \\tilde x(e)},  <\/script><\/div>\n<p> where <script type=\"math\/tex;\">\\tilde x<\/script> denotes the cover at the start of the iteration. Thus, the algorithm at the top chooses each element to minimize the pessimistic estimator. This keeps the pessimistic estimator from increasing, ensuring a successful outcome. <\/p>\n<p>Finally, note that to do this, the algorithm does not need to know <script type=\"math\/tex;\">x<\/script>, yet is guaranteed to do as well as the rounding scheme for any <script type=\"math\/tex;\">x<\/script>. This proves the theorem. <\/p>\n<\/div>\n<\/details>\n<\/div>\n<\/div>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000013\">Finding a near-optimal fractional set cover<\/h2>\n<p>Given a collection of sets <script type=\"math\/tex;\"> S<\/script>, and an arbitrary <script type=\"math\/tex;\">\\varepsilon \\in (0,1)<\/script>, one can also use the algorithm to compute a <script type=\"math\/tex;\">(1+O(\\varepsilon ))<\/script>-approximate fractional (non-integer) set cover for the given instance as follows. <\/p>\n<p>Define coverage <script type=\"math\/tex;\">C<\/script> to be <script type=\"math\/tex;\">C = 2(1-\\varepsilon )\\ln (m)\/\\varepsilon ^2<\/script>. Run the algorithm with coverage <script type=\"math\/tex;\">C<\/script> to find a <script type=\"math\/tex;\">(1\/(1-\\varepsilon ))<\/script>-approximate integer <script type=\"math\/tex;\">C<\/script>-multicover <script type=\"math\/tex;\">\\tilde x<\/script>, then scale it 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 minimum coverage 1. The cover <script type=\"math\/tex;\">x<\/script> will have size at most <script type=\"math\/tex;\">1+\\varepsilon +o(\\varepsilon ^2)<\/script> times the minimum size of any fractional set cover (with minimum coverage 1). <\/p>\n<p>The number of iterations will be <script type=\"math\/tex;\">O(n \\log (n)\/\\varepsilon ^2)<\/script>, because each iteration increases the size of <script type=\"math\/tex;\">\\tilde x<\/script> by 1, and the size of <script type=\"math\/tex;\">\\tilde x<\/script> is at most <script type=\"math\/tex;\">n C<\/script>. <\/p>\n<\/div>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000014\">Running time<\/h2>\n<p> The algorithm will take about <script type=\"math\/tex;\">|x^*|<\/script> iterations, where <script type=\"math\/tex;\">x^*<\/script> is the minimum-size fractional cover of minimum coverage <script type=\"math\/tex;\">C<\/script>. This is bounded by <script type=\"math\/tex;\">n C<\/script>, which can be exponential if <script type=\"math\/tex;\">C<\/script> is large. <\/p>\n<p>If the coverage <script type=\"math\/tex;\">C<\/script> is large (say, <script type=\"math\/tex;\">C \\ge 4\\ln (m)\/\\varepsilon ^2<\/script>), scaling the coverage can ensure polynomial running time. Replace <script type=\"math\/tex;\">C<\/script> by <script type=\"math\/tex;\">C' = C\/\\alpha <\/script>, where integer <script type=\"math\/tex;\">\\alpha = \\lceil C \\varepsilon ^2 \/ 2(1-\\varepsilon )\\ln (m) \\rceil <\/script> is chosen maximally such that <script type=\"math\/tex;\">C' \\ge 2(1-\\varepsilon )\\ln (m)\/\\varepsilon ^2<\/script>. Run the algorithm with coverage <script type=\"math\/tex;\">C'<\/script> to find a <script type=\"math\/tex;\">(1\/(1-\\varepsilon ))<\/script>-approximate integer cover <script type=\"math\/tex;\">\\tilde x<\/script> with respect to <script type=\"math\/tex;\">C'<\/script>, then scale <script type=\"math\/tex;\">\\tilde x<\/script> up by <script type=\"math\/tex;\">\\alpha <\/script> to obtain the integer cover <script type=\"math\/tex;\">x=\\alpha \\tilde x<\/script> for the original problem. <\/p>\n<p>The cover <script type=\"math\/tex;\">x<\/script> will have minimum coverage at least <script type=\"math\/tex;\">C<\/script>, and size at most <script type=\"math\/tex;\">1+\\varepsilon + o(\\varepsilon ^2)<\/script> times the minimum size of any fractional cover with minimum coverage <script type=\"math\/tex;\">C<\/script>. <\/p>\n<p>The number of iterations will be at most <script type=\"math\/tex;\">n C' = O(n\\log (n)\/\\varepsilon ^2)<\/script>. <\/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=\"a0000000015\">Related<\/h1>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/set-cover-fractional\">Dealing with weights in the cost function<\/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=\"a0000000016\">Background<\/h2>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/chernoff\">Introduction to the Chernoff bound<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/chernoff-proof\">Proof of the 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\">Using randomized rounding to derive Lagrangian-relaxation algorithms<\/a> <\/p>\n<\/li>\n<\/ul>\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=\"Young95Randomized\">1<\/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>Here we derive a Lagrangian-relaxation algorithm for unweighted fractional set cover.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8645,"menu_order":5,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8600","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8600","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=8600"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8600\/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=8600"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}