{"id":8569,"date":"2014-12-07T10:42:35","date_gmt":"2014-12-07T18:42:35","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=8569"},"modified":"2026-09-30T09:15:51","modified_gmt":"2026-09-30T17:15:51","slug":"set-cover-markov","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-cover-markov\/","title":{"rendered":"Set Cover \/ using Markov to bound the cost"},"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>Using the Markov bound on the cost yields an ugly greedy algorithm.<\/em><\/center><\/p><\/blockquote>\n<p>  As illustrated <a href=\"http:\/\/algnotes.info\/on\/set-cover-weighted\">in a previous note<\/a>, one can use random stopping times and Wald\u2019s equation to bound the cost, leading to Chvatal\u2019s algorithm. Here we describe another approach: analyzing a <em>fixed<\/em> number of samples, then using the Markov bound to bound the cost. This leads to a more complicated algorithm with a slightly weaker approximation ratio.<!--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-weighted\">Weighted set cover via expected cost<\/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\">Ugly algorithm<\/h1>\n<p>We show the following performance guarantee: <\/p>\n<div id=\"a0000000004\" class=\"my-theorem latex-paragraph latex-thm\">\n<div class=\"latex-paragraph-heading\">   <b \"=\"&quot;\">Theorem.<\/b>   <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>The algorithm below is a <script type=\"math\/tex;\">2(1+\\ln (2n))<\/script>-approximation algorithm. <\/p>\n<\/div><\/div>\n<table id=\"a0000000005\" 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 sets, costs <script type=\"math\/tex;\">c: S\\rightarrow {\\mathbb R}_+<\/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><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">1.<\/td>\n<td style=\"padding-left:0em\"> Let <script type=\"math\/tex;\">T\\doteq \\lceil \\ln (2n) n\\rceil <\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">2.<\/td>\n<td style=\"padding-left:0em\"> For <script type=\"math\/tex;\">t=1,2,\\ldots ,T<\/script> do: <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:1em\"> Let set <script type=\"math\/tex;\">U<\/script> contain the elements not yet covered by chosen sets. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">4.<\/td>\n<td style=\"padding-left:1em\"> Define <script type=\"math\/tex;\">\\mbox{rhs}(s) \\doteq \\frac{1}{2T} + |U|(1-1\/n)^{T-t+1} - |U-s|(1-1\/n)^{T-t}<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">5.<\/td>\n<td style=\"padding-left:1em\"> If <script type=\"math\/tex;\">\\mbox{rhs}(\\emptyset ) \\ge 0<\/script> do nothing (i.e., choose <script type=\"math\/tex;\">s=\\emptyset <\/script>). <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">6.<\/td>\n<td style=\"padding-left:1em\"> Else, choose a set <script type=\"math\/tex;\">s<\/script> to maximize <script type=\"math\/tex;\">\\mbox{rhs}(s)\/c_s<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">7.<\/td>\n<td style=\"padding-left:0em\"> Return the chosen sets. <\/td>\n<\/tr>\n<\/table>\n<p>To prove the theorem we apply the method of conditional probabilities to the usual rounding scheme. We start by analyzing the rounding scheme. <\/p>\n<div class=\"expandable\" id=\"a0000000006\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click to see rounding scheme\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click to see rounding scheme\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<table id=\"a0000000007\" 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\"> Return the chosen sets. <\/td>\n<\/tr>\n<\/table><\/div>\n<\/details>\n<\/div>\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>Fix <script type=\"math\/tex;\">T\\doteq \\lceil \\ln (2n)|x| \\rceil <\/script>. With positive probability, the rounding scheme returns a cover <script type=\"math\/tex;\">C<\/script> of cost at most <script type=\"math\/tex;\">2 T c\\cdot x \/|x|<\/script> (which is at most <script type=\"math\/tex;\">2(1+\\ln (2n))c\\cdot x<\/script>). <\/p>\n<\/div><\/div>\n<div class=\"expandable\" id=\"a0000000009\" 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> Let <script type=\"math\/tex;\">C<\/script> contain the first <script type=\"math\/tex;\">T<\/script> sampled sets. <\/p>\n<p>By calculation (as in <a href=\"http:\/\/algnotes.info\/on\/set-cover-unweighted\">the unweighted case<\/a>), the probability that any given element remains uncovered after <script type=\"math\/tex;\">T<\/script> rounds is less than <script type=\"math\/tex;\">1\/(2n)<\/script>. Thus, the expected number of elements not covered by <script type=\"math\/tex;\">C<\/script> is less than 1\/2. By the Markov bound, the probability that <script type=\"math\/tex;\">C<\/script> is not a cover is less than 1\/2. <\/p>\n<p>By calculation, each sample costs <script type=\"math\/tex;\">c\\cdot x\/|x|<\/script> in expectation. By linearity of expectation, the expected cost of <script type=\"math\/tex;\">C<\/script> is <script type=\"math\/tex;\">T \\, c\\cdot x\/|x|<\/script>. By the Markov bound, the chance that the cost of <script type=\"math\/tex;\">C<\/script> exceeds twice this is at most 1\/2. <\/p>\n<p>By the naive union bound, the probability that <script type=\"math\/tex;\">C<\/script> is not a cover or costs too much is less than 1. <\/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<h1 id=\"a0000000010\">Method of conditional probabilities<\/h1>\n<div id=\"a0000000011\" 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> To prove the theorem, we show that the algorithm keeps the following pessimistic estimator (on the probability of failure) from increasing: <\/p>\n<div id=\"a0000000012\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\phi _t ~ \\doteq ~  \\frac{\\sum _{s\\in S_t} c_t ~ +~  (T-t)c\\cdot x\/|x|}{2\\, T\\, c\\cdot x\/|x|} {\\, {+}\\, }n_t(1-1\/|x|)^{T-t}, <\/script><\/div>\n<p> where <script type=\"math\/tex;\">S_t<\/script> contains the first <script type=\"math\/tex;\">t<\/script> sets chosen and <script type=\"math\/tex;\">n_t<\/script> is the number of elements left uncovered by <script type=\"math\/tex;\">S_t<\/script>. <\/p>\n<div class=\"expandable\" id=\"a0000000013\" 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\">\n<p> If the algorithm chooses a set <script type=\"math\/tex;\">s<\/script> in round <script type=\"math\/tex;\">t<\/script>, the increase in the pessimistic estimator <script type=\"math\/tex;\">\\phi _{t}-\\phi _t<\/script> is <\/p>\n<div id=\"a0000000014\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\frac{c_s}{2T c\\cdot x\/|x|} \\, -\\,  \\frac{1}{2T} \\, +\\,  n_{t}(1-1\/|x|)^{T-t} - n_{t-1}(1-1\/|x|)^{T-t+1}.  <\/script><\/div>\n<p> Given <script type=\"math\/tex;\">n_{t-1}<\/script>, for <script type=\"math\/tex;\">s<\/script> chosen randomly from <script type=\"math\/tex;\">x\/|x|<\/script>, the expected increase is non-positive (because <script type=\"math\/tex;\">\\textrm{E}[c_s] = c\\cdot x\/|x|<\/script> and <script type=\"math\/tex;\">\\textrm{E}[n_{t}] \\le (1-1\/|x|)n_{t-1}<\/script>), so some set <script type=\"math\/tex;\">s<\/script> makes it non-positive. The increase will be non-positive iff <\/p>\n<div id=\"a0000000015\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\frac{c_s}{2T c\\cdot x\/|x|} ~ \\le ~  \\frac{1}{2T} \\, +\\,  n_{t-1}(1-1\/|x|)^{T-t+1} \\, -\\,  n_{t}(1-1\/|x|)^{T-t}.  <\/script><\/div>\n<p> Unfortunately choosing <script type=\"math\/tex;\">s<\/script> to ensure the above inequality requires knowing <script type=\"math\/tex;\">|x|<\/script>. Work around this with the following trick: <em>modify<\/em> the input instance by adding the empty set <script type=\"math\/tex;\">\\emptyset <\/script>, with cost 0, to the cover. Then assume without loss of generality that <script type=\"math\/tex;\">|x|=n<\/script>. (If not, increase <script type=\"math\/tex;\">x_{\\emptyset }<\/script> until <script type=\"math\/tex;\">|x|= n<\/script>, without changing <script type=\"math\/tex;\">c\\cdot x<\/script>). Now <script type=\"math\/tex;\">T =\\lceil \\ln (2n)n\\rceil <\/script> and the desired condition is <\/p>\n<div id=\"a0000000016\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\frac{c_s}{2T c\\cdot x\/n} \\, +\\,  n_{t}(1-1\/n)^{T-t} ~ \\le ~  \\frac{1}{2T} + n_{t-1}(1-1\/n)^{T-t+1}.  <\/script><\/div>\n<p> Since this holds for some <script type=\"math\/tex;\">s<\/script>, one of the following two choices will ensure that it holds: choosing <script type=\"math\/tex;\">s=\\emptyset <\/script>, or choosing <script type=\"math\/tex;\">s<\/script> to maximize the right-hand side divided by the left-hand side. Note that to maximize this ratio, the algorithm does not need to know <script type=\"math\/tex;\">c\\cdot x<\/script>. This gives the algorithm. <\/p>\n<p>The algorithm ensures <script type=\"math\/tex;\">\\phi _T \\le \\phi _0 < 1\/2 + n\\exp (-T\/|x|) \\le 1<\/script> (by the choice of <script type=\"math\/tex;\">T<\/script>), which by inspection of <script type=\"math\/tex;\">\\phi _T<\/script> ensures that at time <script type=\"math\/tex;\">t=T<\/script> all elements are covered cost of the cover is at most <script type=\"math\/tex;\">2T c\\cdot x\/|x|<\/script>, as desired. <\/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 class=\"expandable\" id=\"a0000000017\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for explanation of pessimistic estimator\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for explanation of pessimistic estimator\u2026<\/summary>\n<div class=\"collapseomatic_content\"> Why is the conditional probability of failing to find the desired cover, given <script type=\"math\/tex;\">S_t<\/script>, at most <\/p>\n<div id=\"a0000000018\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\phi _t ~ \\doteq ~  \\frac{\\sum _{s\\in S_t} c_t ~ +~  (T-t)c\\cdot x\/|x|}{2\\, T\\, c\\cdot x\/|x|} {\\, {+}\\, }n_t(1-1\/|x|)^{T-t}? <\/script><\/div>\n<p> The first addend is the conditional expectation of <script type=\"math\/tex;\">c\\cdot {\\tilde x}^{\\scriptscriptstyle (T)}\/(2T c\\cdot x\/|x|)<\/script>, which is an upper bound on the conditional probability that the cost is too high. The second addend is an upper bound on the conditional expectation of the number of elements left uncovered. <\/div>\n<\/details>\n<\/div>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000019\">Related<\/h2>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/greedy\">Deriving greedy algorithms<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/lagrangian\">Deriving 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>Using the Markov bound on the cost yields an ugly greedy algorithm. As illustrated in a previous note, one can use random stopping times and Wald\u2019s equation to bound the cost, leading to Chvatal\u2019s algorithm. Here we describe another approach: analyzing a fixed number of samples, then using the Markov bound to bound the cost. [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8640,"menu_order":5,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8569","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8569","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=8569"}],"version-history":[{"count":3,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8569\/revisions"}],"predecessor-version":[{"id":9023,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8569\/revisions\/9023"}],"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=8569"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}