{"id":8567,"date":"2014-12-07T10:42:19","date_gmt":"2014-12-07T18:42:19","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=8567"},"modified":"2026-09-30T09:15:23","modified_gmt":"2026-09-30T17:15:23","slug":"set-cover-grasp","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-cover-grasp\/","title":{"rendered":"Set Cover \/ GRASP (greedy randomized search procedure; 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<blockquote class=\"quote\"><p><center><em>A derivation of a GRASP (greedy randomized adaptive search procedure) for <script type=\"math\/tex;\">O(\\log n)<\/script>-approximating unweighted Set Cover.<\/em><\/center><\/p><\/blockquote>\n<p>In this example we only <em>partially<\/em> derandomize the rounding scheme. The final algorithm still makes some choices randomly.<!--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\/obliv\">Deriving greedy algorithms via randomized rounding.<\/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\">Greedy randomized search procedure (GRASP)<\/h1>\n<p> To start we summarize the algorithm that we will, in the end, derive. Let <script type=\"math\/tex;\">n=|\\cal U|<\/script> be the number of elements to cover. Let <script type=\"math\/tex;\">{\\textsc{opt}}= |x^*|<\/script> be an upper bound on the size of an optimal set cover. (If <script type=\"math\/tex;\">{\\textsc{opt}}<\/script> is unknown, do binary search for it in <script type=\"math\/tex;\">\\{ 1,2,\\ldots ,n\\} <\/script>.) <\/p>\n<table id=\"a0000000004\" 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;\">{\\cal S}<\/script> of sets over universe <script type=\"math\/tex;\">{\\cal U}<\/script>, upper bound <script type=\"math\/tex;\">{\\textsc{opt}}<\/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> w\/probability <script type=\"math\/tex;\">\\ge 1\/2<\/script>, a set cover <script type=\"math\/tex;\">{\\cal C}<\/script> of size <script type=\"math\/tex;\">O({\\textsc{opt}}\\ln n)<\/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;\">K=\\lceil \\ln (2n){\\textsc{opt}}\/0.99\\rceil <\/script>. Let <script type=\"math\/tex;\">T=\\ln (100)<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">2.<\/td>\n<td style=\"padding-left:0em\"> Create <script type=\"math\/tex;\">K<\/script> tokens, each with an associated unit-rate Poisson process. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:0em\"> As time <script type=\"math\/tex;\">t<\/script> increases continuously from <script type=\"math\/tex;\">0<\/script> to <script type=\"math\/tex;\">T<\/script>: <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">4.<\/td>\n<td style=\"padding-left:1em\"> When a Poisson process fires at time <script type=\"math\/tex;\">t<\/script>, remove its token from its current set (if any), then place it on a set <script type=\"math\/tex;\">s<\/script> chosen to maximize <\/p>\n<div id=\"a0000000005\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\sum _{e\\in s} \\Big( \\frac{1-1\/{\\textsc{opt}}}{1\/f(t) - 1\/{\\textsc{opt}}} \\Big)^{C^{(t)}_e},  <\/script><\/div>\n<p> where <script type=\"math\/tex;\">C^{(t)}_e<\/script> denotes the number of tokens (other than the firing token) currently covering element <script type=\"math\/tex;\">e<\/script>, and <script type=\"math\/tex;\">f(t) \\doteq 1-\\exp (-(T-t))<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">5.<\/td>\n<td style=\"padding-left:0em\"> Return the sets that have tokens on them. <\/td>\n<\/tr>\n<\/table>\n<p>When a token fires, it moves to a set whose elements have largest total \u201cweight\u201d. Initially, when <script type=\"math\/tex;\">t\\approx 0<\/script>, the weight of element <script type=\"math\/tex;\">e<\/script> is about <script type=\"math\/tex;\">.99^{C_e} \\approx 1<\/script>, so the algorithm essentially moves tokens onto the largest sets. When <script type=\"math\/tex;\">t\\approx T-\\ln 2<\/script>, the weight of an element <script type=\"math\/tex;\">e<\/script> is about <script type=\"math\/tex;\">.5^{C_e}<\/script>. Thus, each token on a set covering <script type=\"math\/tex;\">e<\/script> cuts <script type=\"math\/tex;\">e<\/script>\u2019s weight by a factor of <script type=\"math\/tex;\">1\/2<\/script>. Finally, when <script type=\"math\/tex;\">t\\approx T-\\varepsilon <\/script>, an element <script type=\"math\/tex;\">e<\/script> has weight about <script type=\"math\/tex;\">\\varepsilon ^{C_e}<\/script>, so only uncovered (or minimally covered) elements contribute significant weight. <\/p>\n<p>If <script type=\"math\/tex;\">{\\textsc{opt}}<\/script> is unknown, then binary search can be used to find the smallest integer <script type=\"math\/tex;\">{\\textsc{opt}}<\/script> between <script type=\"math\/tex;\">1<\/script> and <script type=\"math\/tex;\">n<\/script> for which the algorithm works. <\/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=\"a0000000006\">Analysis<\/h1>\n<p>Next we prove the following performance guarantee. <\/p>\n<div id=\"a0000000007\" 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> If there exists a fractional set cover <script type=\"math\/tex;\">x^*<\/script> of size <script type=\"math\/tex;\">{\\textsc{opt}}<\/script>, then, with probability at least 1\/2, the algorithm returns a set cover of size at most <script type=\"math\/tex;\">\\lceil \\ln (2n){\\textsc{opt}}\/0.99\\rceil <\/script>. <\/p>\n<\/div><\/div>\n<p>We prove the theorem by deriving the algorithm from the following randomized-rounding scheme. <\/p>\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> Given any fractional solution <script type=\"math\/tex;\">x^*<\/script> over <script type=\"math\/tex;\">n<\/script> elements, randomly round it to an integer solution (a collection of sets) as follows. <em>Use <script type=\"math\/tex;\">K<\/script> tokens. For each token in parallel, run a Poisson process of unit intensity for <script type=\"math\/tex;\">T<\/script> time units. When the Poisson process for a token fires, choose a set from probability distribution <script type=\"math\/tex;\">x^*\/{\\textsc{opt}}<\/script> and move the token onto the set. After <script type=\"math\/tex;\">T<\/script> time units, return the sets that have tokens.<\/em> <\/p>\n<\/div><\/div>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b>Analysis.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> The rounding scheme clearly produces at most <script type=\"math\/tex;\">K<\/script> sets. These sets are likely to form a cover for reasonably small <script type=\"math\/tex;\">K<\/script> and <script type=\"math\/tex;\">T<\/script>: <\/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> For <script type=\"math\/tex;\">K\\ge \\ln (2n){\\textsc{opt}}\/0.99<\/script> and <script type=\"math\/tex;\">T=\\ln 100<\/script>, with probability at least 1\/2, the rounding scheme returns a set cover of size at most <script type=\"math\/tex;\">K<\/script>. <\/p>\n<\/div><\/div>\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>Fix a set <script type=\"math\/tex;\">s<\/script>. The probability that a given token doesn\u2019t fire in <script type=\"math\/tex;\">T<\/script> time units is <script type=\"math\/tex;\">\\exp (-T) = 0.01<\/script>. If it does fire, the probability that it ends up on <script type=\"math\/tex;\">s<\/script> is <script type=\"math\/tex;\">x^*_s\/{\\textsc{opt}}<\/script>. Thus, the probability that a given token ends up on <script type=\"math\/tex;\">s<\/script> is <script type=\"math\/tex;\">0.99 x^*_s\/{\\textsc{opt}}<\/script>. <\/p>\n<p>Therefore, for any fixed element <script type=\"math\/tex;\">e<\/script>, the probability that a given token ends up covering <script type=\"math\/tex;\">e<\/script> (that is, ends up on a set containing <script type=\"math\/tex;\">e<\/script>) is <script type=\"math\/tex;\">\\sum _{s\\ni e}0.99\\,  x^*_s\/{\\textsc{opt}}\\ge 0.99\/{\\textsc{opt}}<\/script>. <\/p>\n<p>Since the tokens are independent, the probability that <script type=\"math\/tex;\">e<\/script> is not covered at the end (i.e., the probability that no token ends up covering <script type=\"math\/tex;\">e<\/script>) is at most <\/p>\n<div id=\"a0000000010\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\renewcommand{\\mathspread }{\\, \\, \\, }(1 - 0.99\/{\\textsc{opt}})^K {\\, \\, \\, {<}\\, \\, \\, }\\exp (- 0.99 K\/{\\textsc{opt}}) {\\, \\, \\, {\\le }\\, \\, \\, }1\/(2n).  <\/script><\/div>\n<p>By the naive union bound, the probability that there exists an uncovered element is less than 1\/2. <\/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><\/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=\"a0000000011\">Pessimistic estimator<\/h1>\n<p> Next we apply the method of conditional probabilities to derive the algorithm. <\/p>\n<p>At time <script type=\"math\/tex;\">t<\/script>, let <script type=\"math\/tex;\">f(t) \\doteq 1-\\exp (-(T-t))<\/script> be the probability that a given token will fire in the remaining <script type=\"math\/tex;\">T-t<\/script> time units. If a token is currently covering <script type=\"math\/tex;\">e<\/script>, the conditional probability that it will not cover <script type=\"math\/tex;\">e<\/script> at the end is at most <script type=\"math\/tex;\">\\renewcommand{\\mathspread }{\\, \\, \\, }f(t)( 1- 1 \/ {\\textsc{opt}}), <\/script> (the probability that the token will fire times an upper bound on the probability it will end up elsewhere if it does). Likewise, if a token is not covering <script type=\"math\/tex;\">e<\/script> now, the conditional probability that it will end up not covering <script type=\"math\/tex;\">e<\/script> is at most <script type=\"math\/tex;\">1 - f(t)\/{\\textsc{opt}}<\/script>. <\/p>\n<p>Let <script type=\"math\/tex;\">{C}^{\\scriptscriptstyle (t)}_e<\/script> denote the number of tokens currently covering <script type=\"math\/tex;\">e<\/script>. Since the tokens are independent, the conditional probability that no token will end up covering <script type=\"math\/tex;\">e<\/script> is at most <\/p>\n<div id=\"a0000000012\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\renewcommand{\\mathspread }{\\, \\, \\, }\\psi _{et} {\\, \\, \\, {\\doteq }\\, \\, \\, }\\big(f(t) - f(t) \/ {\\textsc{opt}}\\big)^{\\textstyle {C}^{\\scriptscriptstyle (t)}_e} \\times \\big(1 - f(t) \/ {\\textsc{opt}}\\big)^{\\textstyle K - {C}^{\\scriptscriptstyle (t)}_e} . <\/script><\/div>\n<p> By the naive union bound, the conditional probability that there will be a not-covered element is at most <script type=\"math\/tex;\">\\Phi _t \\doteq \\sum _e \\psi _{et}<\/script>. This is our pessimistic estimator. <\/p>\n<p>The reader can verify that <script type=\"math\/tex;\">\\Phi _t<\/script> does not increase in expectation as <script type=\"math\/tex;\">t<\/script> increases. (It is enough to show that, for <script type=\"math\/tex;\">\\varepsilon <\/script> small, <script type=\"math\/tex;\">\\renewcommand{\\mathspread }{\\, \\, \\, }\\textrm{E}[\\Phi _{t+\\varepsilon } - \\Phi _t \\, |\\, \\Phi _t] {\\, \\, \\, {\\le }\\, \\, \\, }o(\\varepsilon )<\/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=\"a0000000013\">Algorithm<\/h1>\n<p> To obtain the algorithm, derandomize only the random choices of sets. Namely, let the tokens fire randomly, but when a token fires, move the token to a set <script type=\"math\/tex;\">s<\/script> chosen to minimize the resulting value of <script type=\"math\/tex;\">\\Phi _t<\/script>. With this modification, <script type=\"math\/tex;\">\\Phi _t<\/script> is still non-increasing with <script type=\"math\/tex;\">t<\/script> in expectation, so a set cover of size <script type=\"math\/tex;\">K<\/script> will still be found with probability at least 1\/2. This gives the algorithm. <\/p>\n<p>Here is the proof of the approximation guarantee: <\/p>\n<div id=\"a0000000014\" 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>As time proceeds from <script type=\"math\/tex;\">t=0<\/script> to <script type=\"math\/tex;\">t=T<\/script>, the pessimistic estimator <script type=\"math\/tex;\">\\Phi _t<\/script> defined previously is non-increasing in expectation. Thus, <script type=\"math\/tex;\">\\textrm{E}[\\Phi _T] \\le \\Phi _0 \\le 1\/2<\/script>. Thus, <script type=\"math\/tex;\">\\Pr [\\Phi _T \\ge 1] \\, \\le \\,  1\/2<\/script>. Finally, if <script type=\"math\/tex;\">\\Phi _T \\lt 1<\/script>, then each element is covered. <\/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 class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b>open problem:<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Simplify the algorithm, removing the awkward dependence on <script type=\"math\/tex;\">{\\textsc{opt}}<\/script>. <\/p>\n<\/div><\/div>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000015\">Related<\/h2>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/obliv\">Deriving greedy algorithms via randomized rounding<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/set-cover-unweighted\">Deriving the greedy-set cover algorithm via randomized rounding<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Greedy_randomized_adaptive_search_procedure\">Greedy randomized adaptive search procedure<\/a> (wikipedia) <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/cstheory.stackexchange.com\/questions\/14189\/is-there-a-randomized-algorithm-for-set-cover\">Is there a randomized algorithm for set cover<\/a> (Stack Exchange) <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div><\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>A derivation of a GRASP (greedy randomized adaptive search procedure) for -approximating unweighted Set Cover. In this example we only partially derandomize the rounding scheme. The final algorithm still makes some choices randomly.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8640,"menu_order":6,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8567","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8567","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=8567"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8567\/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=8567"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}