{"id":880,"date":"2010-01-29T00:26:38","date_gmt":"2010-01-29T08:26:38","guid":{"rendered":"http:\/\/obliviousrounding.com\/blog\/?p=880"},"modified":"2026-09-30T09:14:36","modified_gmt":"2026-09-30T17:14:36","slug":"greedy-example","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/greedy-example\/","title":{"rendered":"Set Cover \/ greedy algorithm"},"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 brief review of the greedy algorithm for the Set-Cover problem.<\/em><\/center><\/p><\/blockquote>\n<p> \u00a0<!--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><span style=\"float:right;margin:0.8em;margin-right:-0.5in;\"> <img decoding=\"async\" src=\"http:\/\/algnotes.info\/b\/wp-content\/uploads\/2011\/02\/img-00014.png\" alt=\"\\includegraphics[type=pdf,ext=.pdf,read=.pdf,width=3.75in]{shared\/graphics\/set_cover}\" style=\"width:3.75in\" class=\"zoooom\" \/> <\/span> The Set-Cover problem: Given a collection <script type=\"math\/tex;\">S<\/script> of finite sets from a universe <script type=\"math\/tex;\">U<\/script> and a cost <script type=\"math\/tex;\">c_s<\/script> for each set <script type=\"math\/tex;\">s\\in S<\/script>, the problem is to choose a minimum-cost <em>set cover<\/em> \u2014 a collection <script type=\"math\/tex;\"> C<\/script> of sets in <script type=\"math\/tex;\"> S<\/script> such that each element <script type=\"math\/tex;\">e\\in U<\/script> is contained in at least one set in <script type=\"math\/tex;\"> C<\/script>. The cost of <script type=\"math\/tex;\"> C<\/script> is <script type=\"math\/tex;\">\\sum _{s\\in C} c_s<\/script>. The figure shows a Set Cover instance with universe <script type=\"math\/tex;\">\\{ a,b,c,d,e\\} <\/script> and four sets. The two sets labeled \u201c1\u201d form a set cover of size 2, covering all five elements in the universe. <\/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<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;\"> S<\/script> of sets over universe <script type=\"math\/tex;\">U<\/script>, 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;\"> C \\leftarrow \\emptyset <\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">2.<\/td>\n<td style=\"padding-left:0em\"> Repeat until <script type=\"math\/tex;\">C<\/script> is a set cover: <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:1em\"> Find a set <script type=\"math\/tex;\">s\\in S<\/script> maximizing the number of elements in <script type=\"math\/tex;\">s<\/script> <br \/>not yet covered by any set in <script type=\"math\/tex;\">C<\/script>, divided by the cost <script type=\"math\/tex;\">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\"> Add <script type=\"math\/tex;\">s<\/script> to <script type=\"math\/tex;\"> C<\/script>. <\/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;\"> C<\/script>. <\/td>\n<\/tr>\n<\/table>\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=\"a0000000005\">Performance guarantee<\/h1>\n<p>The following performance guarantee was proved in the 1970\u2019s: <\/p>\n<div id=\"a0000000006\" class=\"my-theorem latex-paragraph latex-thm\">\n<div class=\"latex-paragraph-heading\">   <b>Theorem <\/b> (<span class=\"cite\">[<a href=\"#Johnson74Approximation\">3<\/a>, <a href=\"#Lovasz75Ratio\">4<\/a>, <a href=\"#Chvatal79Greedy\">1<\/a>]<\/span>).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> The greedy set-cover algorithm returns a set cover of cost at most <script type=\"math\/tex;\">{\\rm H}(d)\\, {\\textsc{opt}}<\/script>, where <script type=\"math\/tex;\">{\\textsc{opt}}<\/script> is the minimum cost of any set cover, <script type=\"math\/tex;\">d = \\max _{s\\in S} |s|<\/script> is the maximum set size, and <script type=\"math\/tex;\">{\\rm H}(d)\\approx 0.58+\\ln d<\/script> is the <script type=\"math\/tex;\">d<\/script>th Harmonic number. <\/p>\n<\/div><\/div>\n<p>The guarantee actually holds with respect to the optimum <a href=\"http:\/\/algnotes.info\/on\/modeling\">fractional set cover<\/a>. The proof is typically given as a charging argument, or by a primal-dual argument (constructing a related dual solution to bound <span class=\"scshape\" style=\"font-variant:small-caps;text-transform:lowercase\">opt<\/span>). <\/p>\n<p>The logarithmic approximation guarantee is the best possible in the following sense: if P<script type=\"math\/tex;\">\\ne <\/script>NP, in the worst case, no polynomial-time algorithm guarantees a cover of cost <script type=\"math\/tex;\">o({\\textsc{opt}}\\log n)<\/script>, where <script type=\"math\/tex;\">n=|U|<\/script> is the number of elements to be covered <span class=\"cite\">[<a href=\"#Feige98Threshold\">2<\/a>]<\/span>. <\/p>\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=\"a0000000007\">Related<\/h2>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/obliv\">Using randomized rounding to derive this algorithm<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/set-cover-Wolsey\">Wolsey\u2019s generalization<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Set_cover_problem\">Set cover problem (wikipedia)<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Harmonic_number\">Harmonic numbers (wikipedia)<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/V\u00e1clav_Chv\u00e1tal\">V\u00e1clav Chv\u00e1tal<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/David_S._Johnson\">David Johnson<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/L\u00e1szl\u00f3_Lov\u00e1sz\">L\u00e1szl\u00f3 Lov\u00e1sz<\/a> (wikipedia) <\/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=\"Chvatal79Greedy\">1<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;V+Chvatal&quot;+intitle:&quot;+A+greedy+heuristic+for+the+set-covering+problem&quot;\">V.\u00a0Chv\u00e1tal. A greedy heuristic for the set-covering problem. <em>Math. Operations Research<\/em>, 4(3):233\u2013235, 1979. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Feige98Threshold\">2<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;U+Feige&quot;+intitle:&quot;+A+threshold+of+ln+n+for+approximating+set+cover&quot;\">U.\u00a0Feige. A threshold of ln n for approximating set cover. <em>J. ACM<\/em>, 45(4):634\u2013652, 1998. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Johnson74Approximation\">3<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;D+S++Johnson&quot;+intitle:&quot;+Approximation+algorithms+for+combinatorial+problems&quot;\">D.\u00a0S. Johnson. Approximation algorithms for combinatorial problems. <em>J. Computer System Sciences<\/em>, 9:256\u2013278, 1974. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Lovasz75Ratio\">4<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;L+Lovasz&quot;+intitle:&quot;+On+the+ratio+of+optimal+integral+and+fractional+covers&quot;\">L.\u00a0Lov\u00e1sz. On the ratio of optimal integral and fractional covers. <em>Discrete Mathematics<\/em>, 13:383\u2013390, 1975. <\/a><\/td>\n<\/tr>\n<\/table><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>A brief review of the greedy algorithm for the Set-Cover problem. \u00a0<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8676,"menu_order":5,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-880","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/880","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=880"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/880\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8676"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=880"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}