{"id":8565,"date":"2014-12-07T10:42:02","date_gmt":"2014-12-07T18:42:02","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=8565"},"modified":"2026-09-30T09:15:54","modified_gmt":"2026-09-30T17:15:54","slug":"set-cover-alterations","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-cover-alterations\/","title":{"rendered":"Set Cover \/ alterations"},"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>Yet another approximation ratio for Chv\u00e1tal\u2019s greedy set-cover algorithm.<\/em><\/center><\/p><\/blockquote>\n<p>  We show that the rounding scheme and algorithm give <script type=\"math\/tex;\">(1+\\ln (n\/{\\textsc{opt}}))<\/script>-approximate solutions, matching bounds of Srinivasan\u00a0<span class=\"cite\">[<a href=\"#Srinivasan99Improved\">2<\/a>, Thm.5.2(b)]<\/span> and Slavik\u00a0<span class=\"cite\">[<a href=\"#slavik1997tight\">1<\/a>]<\/span>. For unweighted set cover, this bound compares favorably to the <a href=\"http:\/\/algnotes.info\/on\/set-cover-local\"><script type=\"math\/tex;\">{\\rm H}(d)<\/script>-approximation<\/a> ratio, because <script type=\"math\/tex;\">n\/{\\textsc{opt}}<\/script> is always at most <script type=\"math\/tex;\">d<\/script> (the maximum set size). For the weighted case the bounds are incomparable. The proof is related to the so-called <em>method of alterations<\/em>.<!--more--><\/p>\n<p><div style=\"margin:0pt;padding:0pt;margin-bottom:12px\"><\/div>\n<\/p>\n<hr \/>\n<div class=\"expandable\" id=\"a0000000002\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for background material\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for background material\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/set-cover-unweighted\">Proof of <script type=\"math\/tex;\">{\\rm H}(n)<\/script>-approximation ratio.<\/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\">The algorithm<\/h1>\n<p>We prove the following theorem by applying the method of conditional probabilities to the localized rounding scheme: <\/p>\n<div id=\"a0000000004\" class=\"my-theorem latex-paragraph latex-thm\">\n<div class=\"latex-paragraph-heading\">   <b>Theorem <\/b> (\u00a0<span class=\"cite\">[<a href=\"#slavik1997tight\">1<\/a>]<\/span>).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Assuming the cost of each set is at most <script type=\"math\/tex;\">1<\/script>, Chv\u00e1tal\u2019s algorithm returns a cover of cost at most <script type=\"math\/tex;\">1 + {\\textsc{opt}}\\big(1+\\ln (n\/{\\textsc{opt}})\\big)<\/script>. <\/p>\n<\/div><\/div>\n<div class=\"expandable\" id=\"a0000000005\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click to see localized rounding scheme and algorithm\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click to see localized rounding scheme and algorithm\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<table id=\"a0000000006\" class=\"latex-scheme\" cellspacing=\"0\" cellpadding=\"4\" width=\"100%\" style=\"border-top:1px solid #CCC;border-bottom:1px solid #CCC;margin-top:2ex;margin-bottom:2ex;\">\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">&nbsp;<\/td>\n<td style=\"padding-left:0em\"><b style=\"font-size:90%\">input:<\/b> weighted Set-Cover instance <script type=\"math\/tex;\">{\\cal I}<\/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 for <script type=\"math\/tex;\">{\\cal I}<\/script><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">0.<\/td>\n<td style=\"padding-left:0em\"> Compute a 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\">1.<\/td>\n<td style=\"padding-left:0em\"> Repeat until the chosen sets form a cover: <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">2.<\/td>\n<td style=\"padding-left:1em\"> Choose a set randomly from the distribution defined by <script type=\"math\/tex;\">x^*\/|x^*|<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:0em\"> <em>Return the sets that, when chosen, contained not-yet-covered elements.<\/em> <\/td>\n<\/tr>\n<\/table>\n<table id=\"a0000000007\" 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> weighted Set-Cover instance <script type=\"math\/tex;\">{\\cal I}<\/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;\">C<\/script> for <script type=\"math\/tex;\">{\\cal I}<\/script><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">1.<\/td>\n<td style=\"padding-left:0em\"> Repeat until the chosen sets form a cover: <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">2.<\/td>\n<td style=\"padding-left:1em\"> Choose a set <script type=\"math\/tex;\">s<\/script> minimizing the cost of <script type=\"math\/tex;\">s<\/script> divided by the number of elements in <script type=\"math\/tex;\">s<\/script> not yet covered by chosen sets. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:0em\"> Return the chosen sets. <\/td>\n<\/tr>\n<\/table>\n<\/div>\n<\/details>\n<\/div>\n<p>To prove the theorem, we first analyze the rounding scheme: <\/p>\n<div id=\"a0000000008\" 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>Assume the cost of each set is at most <script type=\"math\/tex;\">1<\/script>. With non-zero probability, the cost of the random set cover <script type=\"math\/tex;\">C<\/script> is less than <script type=\"math\/tex;\">1+[1+\\ln (n\/c\\cdot x)]c\\cdot x<\/script>. <\/p>\n<\/div><\/div>\n<div id=\"a0000000009\" class=\"latex-paragraph latex-proof\">\n<div class=\"latex-paragraph-heading\"> <b>Proof of lemma.<\/b>  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Define (with foresight) <script type=\"math\/tex;\">\\alpha = \\ln (n\/c\\cdot x) \\, c\\cdot x<\/script>. Let <script type=\"math\/tex;\">n_t<\/script> denote the number of elements remaining after <script type=\"math\/tex;\">t<\/script> samples. Let stopping time <script type=\"math\/tex;\">T<\/script> be the number of samples until the cumulative cost of sampled sets is in the range <script type=\"math\/tex;\">[\\alpha ,\\alpha +1)<\/script>, so that the total cost of the <script type=\"math\/tex;\">T<\/script> sets chosen in this first stage is less than <script type=\"math\/tex;\">\\alpha +1<\/script>. In the second stage, <script type=\"math\/tex;\">n_T<\/script> elements are initially not-yet-covered, and then each set chosen covers at least 1 new element and costs at most 1. So the total cost of the second stage is at most <script type=\"math\/tex;\">n_T<\/script>. Thus, the total cost of all sets chosen is less than <script type=\"math\/tex;\">\\alpha +1+n_T<\/script>. To finish the proof, we show that <em>with positive probability <script type=\"math\/tex;\">n_T<\/script> is at most <script type=\"math\/tex;\">c\\cdot x<\/script><\/em>, in which case the upper bound <script type=\"math\/tex;\">\\alpha +1+n_T<\/script> on the total cost is at most <script type=\"math\/tex;\">\\ln (n\/c\\cdot x) \\,  c\\cdot x + 1 + c\\cdot x<\/script>, as desired. <\/p>\n<div class=\"expandable\" id=\"a0000000010\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for remaining details \u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for remaining details \u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p> With each of the first <script type=\"math\/tex;\">T<\/script> samples, the number of not-yet-covered elements <script type=\"math\/tex;\">n_t<\/script> decreases by at least a <script type=\"math\/tex;\">1\/|x|<\/script> factor in expectation. By <a href=\"http:\/\/algnotes.info\/on\/walds-dependent\">Wald\u2019s for dependent decrements<\/a>, this implies that <\/p>\n<div id=\"a0000000011\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\textrm{E}[T] \\, \\le \\,  \\textrm{E}\\Big[{\\textstyle \\int _{n_T}^{n_0}} \\frac{|x|}{z} \\, dz\\Big] \\, =\\,  |x|\\big(\\ln (n) - \\textrm{E}[\\ln n_T]\\big). <\/script><\/div>\n<p>Since the cumulative cost increases by at most <script type=\"math\/tex;\">c\\cdot x\/|x|<\/script> in expectation with each sample, and increases from 0 to at least <script type=\"math\/tex;\">\\alpha <\/script> in the first <script type=\"math\/tex;\">T<\/script> samples, by <a href=\"http:\/\/algnotes.info\/on\/walds\">Wald\u2019s equation<\/a>, the expected number of samples in the first stage is <script type=\"math\/tex;\">\\textrm{E}[T] \\ge \\alpha \\,  |x|\\,  \/ c\\cdot x<\/script>. <\/p>\n<p>Transitively, these two bounds on <script type=\"math\/tex;\">\\textrm{E}[T]<\/script> imply <script type=\"math\/tex;\">|x|\\big(\\ln (n) - \\textrm{E}[\\ln n_T]\\big) \\ge \\alpha |x|\/c\\cdot x<\/script>. <\/p>\n<p>That is, <script type=\"math\/tex;\">\\textrm{E}[\\ln n_T] \\le \\ln (n) - \\alpha \/c\\cdot x = \\ln c\\cdot x<\/script>. <\/p>\n<\/div>\n<\/details>\n<\/div>\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><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000012\">Method of conditional probabilities<\/h1>\n<p> To prove the theorem, we show that applying the method of conditional probabilities to the lemma yields the algorithm. <\/p>\n<div id=\"a0000000013\" class=\"latex-paragraph latex-proof\">\n<div class=\"latex-paragraph-heading\"> <b>Proof of theorem.<\/b>  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Define <script type=\"math\/tex;\">T<\/script>, <script type=\"math\/tex;\">n_t<\/script>, and <script type=\"math\/tex;\">\\alpha <\/script> as in the proof of the lemma. Following the proof of the lemma, in any outcome where <script type=\"math\/tex;\">n_T<\/script> is less than <script type=\"math\/tex;\">c\\cdot x<\/script>, the performance guarantee holds. We show that the algorithm chooses each of the first <script type=\"math\/tex;\">T<\/script> sets to keep the conditional expectation of <script type=\"math\/tex;\">\\ln n_T<\/script> below <script type=\"math\/tex;\">\\ln c\\cdot x<\/script>. It does so by keeping the following pessimistic estimator from decreasing: <\/p>\n<div id=\"a0000000014\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\phi _t ~ =~  \\ln (n_t) \\,  - \\,  \\frac{\\alpha -C_t}{c\\cdot x}, <\/script><\/div>\n<p> where (abusing notation) <script type=\"math\/tex;\">C_t<\/script> denotes the cost of the first <script type=\"math\/tex;\">t<\/script> sampled sets. <\/p>\n<div class=\"expandable\" id=\"a0000000015\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for verification of pessimistic estimator\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for verification of pessimistic estimator\u2026<\/summary>\n<div class=\"collapseomatic_content\"> Fix any <script type=\"math\/tex;\">t \\in \\{ 0,1,\\ldots ,T\\} <\/script>. If the algorithm chooses some set <script type=\"math\/tex;\">s<\/script> for sample <script type=\"math\/tex;\">t<\/script>, the increase in the pessimistic estimator <script type=\"math\/tex;\">\\phi _{t}-\\phi _{t-1}<\/script> is <\/p>\n<div id=\"a0000000016\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\ln \\Big( \\frac{n_{t}}{n_{t-1}}\\Big) + \\frac{c_s}{c\\cdot x} ~ \\le ~  \\frac{c_s}{c\\cdot x} - \\frac{n_{t-1}-n_{t}}{n_{t-1}}.  <\/script><\/div>\n<p> In expectation (for random <script type=\"math\/tex;\">s<\/script> from <script type=\"math\/tex;\">x\/|x|<\/script>) the right-hand side (RHS) above is non-positive. RHS will be non-positive iff (bringing terms that depend on <script type=\"math\/tex;\">s<\/script> to the left-hand side (LHS)) <\/p>\n<div id=\"a0000000017\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\frac{n_{t-1}-n_{t}}{c_s} ~ \\ge ~  \\frac{n_{t-1}}{c\\cdot x}.  <\/script><\/div>\n<p> The algorithm chooses <script type=\"math\/tex;\">s<\/script> to maximize the LHS above, satisfying the inequality, and keeping the pessimistic estimator from increasing. Thus, at time <script type=\"math\/tex;\">T<\/script> we have <\/p>\n<div id=\"a0000000018\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\ln (n_T)\\,  -\\,  \\frac{\\alpha -C_T}{c\\cdot x} \\, =\\,  \\phi _T \\, \\le \\,  \\phi _0 \\, =\\,  \\ln (n)\\,  -\\,  \\frac{\\alpha }{c\\cdot x} \\, =\\,  \\ln c\\cdot x, <\/script><\/div>\n<p> which with <script type=\"math\/tex;\">C_T \\ge \\alpha <\/script> implies <script type=\"math\/tex;\">\\ln n_T \\le \\ln (c\\cdot x)<\/script> as desired. <\/div>\n<\/details>\n<\/div>\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 class=\"expandable\" id=\"a0000000019\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for derivation of pessimistic estimator\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for derivation of pessimistic estimator\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p> Condition on the first <script type=\"math\/tex;\">t<\/script> samples. For each subsequent sample <script type=\"math\/tex;\">s=t+1,t+2,\\ldots , T<\/script>, we have <script type=\"math\/tex;\">\\textrm{E}[n_s\\, |\\, n_{s-1}] \\le n_{s-1}\/|x|<\/script>, so by <a href=\"http:\/\/algnotes.info\/on\/walds-dependent\">Wald\u2019s for dependent decrements<\/a> <\/p>\n<div id=\"a0000000020\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\textrm{E}[ T-t \\, |\\, n_t] \\, \\le \\,  \\textrm{E}\\big[{\\textstyle \\int _{n_T}^{n_t}} \\frac{|x|}{z} \\, dz\\big] \\, =\\,  |x|\\big(\\ln (n_t) - \\textrm{E}[\\ln n_T\\, |\\, n_t]\\big), <\/script><\/div>\n<p> so that <script type=\"math\/tex;\">\\textrm{E}[\\ln n_T \\, |\\, n_t]\\, \\le \\, \\ln (n_t)\\,  - \\,  \\textrm{E}[T-t\\, |\\, n_t]\/|x|<\/script>. <\/p>\n<p>Each sample costs <script type=\"math\/tex;\">c\\cdot x\/|x|<\/script> in expectation, so, by Wald\u2019s, given <script type=\"math\/tex;\">n_t<\/script> and <script type=\"math\/tex;\">C_t<\/script> (the cost so far) the expected number of additional samples required to bring the cost to <script type=\"math\/tex;\">\\alpha <\/script> or more is <script type=\"math\/tex;\">\\textrm{E}[T-t\\, |\\, n_t] \\ge (\\alpha -C_t)|x|\/c\\cdot x<\/script>. <\/p>\n<p>Combining the two bounds above, <script type=\"math\/tex;\">\\textrm{E}[\\ln n_T\\, |\\, n_t]<\/script> is at most <script type=\"math\/tex;\">\\ln (n_t) \\,  - \\,  (\\alpha -C_t)\/ c\\cdot x = \\phi _t<\/script>. <\/p>\n<\/div>\n<\/details>\n<\/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-subsection\">\n<h2 id=\"a0000000021\">Related<\/h2>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/set-cover-local\"><script type=\"math\/tex;\">{\\rm H}(d)<\/script>-approximation ratio for Set Cover (localized)<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<\/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=\"slavik1997tight\">1<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;P+Slavik&quot;+intitle:&quot;+A+tight+analysis+of+the+greedy+algorithm+for+set+cover&quot;\">P.\u00a0Slav\u00edk. A tight analysis of the greedy algorithm for set cover. <em>Journal of Algorithms<\/em>, 25(2):237\u2013254, 1997. Preliminary version in STOC\u201996. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Srinivasan99Improved\">2<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;A+Srinivasan&quot;+intitle:&quot;+Improved+approximation+guarantees+for+packing+and+covering+integer+programs&quot;\">A.\u00a0Srinivasan. Improved approximation guarantees for packing and covering integer programs. <em>SIAM J. Comput.<\/em>, 29:648\u2013670, 1999. Preliminary version in STOC\u201995. <\/a><\/td>\n<\/tr>\n<\/table><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Yet another approximation ratio for Chv\u00e1tal\u2019s greedy set-cover algorithm. We show that the rounding scheme and algorithm give -approximate solutions, matching bounds of Srinivasan\u00a0[2, Thm.5.2(b)] and Slavik\u00a0[1]. For unweighted set cover, this bound compares favorably to the -approximation ratio, because is always at most (the maximum set size). For the weighted case the bounds are [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8640,"menu_order":4,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8565","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8565","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=8565"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8565\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8640"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=8565"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}