{"id":1234,"date":"2010-01-30T18:56:19","date_gmt":"2010-01-31T02:56:19","guid":{"rendered":"http:\/\/obliviousrounding.com\/blog\/?p=1234"},"modified":"2026-09-30T09:14:29","modified_gmt":"2026-09-30T17:14:29","slug":"set-cover-wolsey","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/set-cover-wolsey\/","title":{"rendered":"Set Cover \/ Wolsey\u2019s generalization"},"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>Wolsey\u2019s generalization of the greedy Set-Cover algorithm to a large class of problems.<\/em><\/center><\/p><\/blockquote>\n<p>  It is natural to ask what general classes of problems the greedy Set-Cover algorithm generalizes to. Here we describe one such class, due to Wolsey (1982), that captures many, but not all, such problems.<!--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\/greedy-example\">The greedy Set-Cover algorithm<\/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\">Minimizing a linear cost subject to a submodular constraint<\/h1>\n<p> The class is called <em>choosing a subset to minimize a linear cost function subject to a submodular constraint<\/em>. It contains all problems of the form <\/p>\n<div id=\"a0000000004\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\min _S \\Big\\{  \\sum _{s \\in S} c_s ~ \\Big|~  S\\subseteq C, f(S) \\ge k\\Big\\}   <\/script><\/div>\n<p> where <script type=\"math\/tex;\">C<\/script> is a universe of elements and <script type=\"math\/tex;\">f:2^C\\rightarrow {\\mathbb R}<\/script> is a monotone submodular function (mapping subsets to reals).<a href=\"#a0000000005\" class=\"footnote\"><sup class=\"footnotemark\">1<\/sup><\/a> <\/p>\n<p>The generalized algorithm starts with <script type=\"math\/tex;\">S=\\emptyset <\/script>, then repeatedly chooses an element <script type=\"math\/tex;\">s\\in C<\/script> to add to <script type=\"math\/tex;\">S<\/script>, where <script type=\"math\/tex;\">s<\/script> maximizes <script type=\"math\/tex;\">[f(S\\cup \\{ s\\} ) - f(S)]\/c_s<\/script>, stopping when <script type=\"math\/tex;\">f(S)<\/script> achieves the maximum possible value <script type=\"math\/tex;\">f(C)<\/script>. <\/p>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b>Performance guarantees.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Wolsey proves a number of performance guarantees for the algorithm\u00a0<span class=\"cite\">[<a href=\"#wolsey1982analysis\">3<\/a>, <a href=\"#Nemhauser88Integer\">2<\/a>]<\/span>. The most satisfactory guarantee holds only when the submodular function is <em>integer-valued<\/em>. In this case, the approximation ratio is <script type=\"math\/tex;\">{\\rm H}(d)<\/script>, where <script type=\"math\/tex;\">d<\/script> is <script type=\"math\/tex;\">\\max \\{ f(\\{ s\\} ) - f(\\emptyset )~ |~ s\\in C\\} <\/script>, the largest possible increase in <script type=\"math\/tex;\">f<\/script> from adding a single element. The proof is primal-dual, based on an abstract linear-program relaxation of the problem. <\/p>\n<p>For more general submodular functions, Wolsey bounds the approximation ratio (somewhat weakly) by <script type=\"math\/tex;\">1+\\ln \\min (\\lambda _1, \\lambda _2, \\lambda _3)<\/script>, where <\/p>\n<ul class=\"itemize\">\n<li>\n<p><script type=\"math\/tex;\">\\lambda _1<\/script> is <script type=\"math\/tex;\">\\displaystyle \\max _{s,t} \\Big\\{ \\frac{f(\\{ s\\} ) - f(\\emptyset )}{f(S_t\\cup \\{ s\\} ) - f(S_t)} ~ \\Big|~  {f(S_t\\cup \\{ s\\} ) - f(S_t) \\gt 0} \\Big\\}  <\/script> <br \/>where <script type=\"math\/tex;\">S_t<\/script> contains the first <script type=\"math\/tex;\">t<\/script> elements chosen by the algorithm and <script type=\"math\/tex;\">s<\/script> ranges over <script type=\"math\/tex;\">s\\in C<\/script>. This generalizes Wolsey\u2019s result for integer-valued <script type=\"math\/tex;\">f<\/script>. <\/p>\n<\/li>\n<li>\n<p><script type=\"math\/tex;\">\\lambda _2 = \\sigma _1 \/ \\sigma _T<\/script>, where <script type=\"math\/tex;\">T<\/script> is the number of iterations and <script type=\"math\/tex;\">\\sigma _t<\/script> is the value of the quantity that is maximized in iteration <script type=\"math\/tex;\">t<\/script> of the algorithm (that is, <script type=\"math\/tex;\">\\sigma _t = \\max _s [f(S_t\\cup \\{ s\\} )-f(S_t)]\/c_s<\/script>). <\/p>\n<\/li>\n<li>\n<p><script type=\"math\/tex;\">\\lambda _3<\/script> is <script type=\"math\/tex;\">\\frac{f(C) - f(\\emptyset )}{f(C) - f(S_{T-1})}<\/script>. <\/p>\n<\/li>\n<\/ul>\n<p>These latter bounds aren\u2019t fully satisfying. <\/p>\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=\"a0000000006\">Examples<\/h1>\n<p> The class of problems is somewhat abstract. Here are some examples: <\/p>\n<ul class=\"itemize\">\n<li>\n<p>Set Partial Cover: <em>Given an integer <script type=\"math\/tex;\">k<\/script> and a collection <script type=\"math\/tex;\">C<\/script> of sets over a universe <script type=\"math\/tex;\">{\\cal U}<\/script>, where each set <script type=\"math\/tex;\">s\\in C<\/script> has a cost <script type=\"math\/tex;\">c_s<\/script>, choose a minimum-cost collection of the sets so that their union contains at least <script type=\"math\/tex;\">k<\/script> elements.<\/em> The approximation ratio is <script type=\"math\/tex;\">{\\rm H}(d)<\/script>, where <script type=\"math\/tex;\">d<\/script> is the maximum size of any single set <script type=\"math\/tex;\">s\\in C<\/script>. <\/p>\n<div class=\"expandable\" id=\"a0000000007\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Explanation\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Explanation\u2026<\/summary>\n<div class=\"collapseomatic_content\"> Here the submodular function is the minimum of <script type=\"math\/tex;\">k<\/script> and the size of the union of the chosen sets. The problem requires choosing a minimum-cost collection of sets that makes this function take value at least <script type=\"math\/tex;\">k<\/script>. The greedy algorithm repeatedly chooses a set <script type=\"math\/tex;\">s\\in C<\/script> that maximizes the increase in this function, divided by the cost <script type=\"math\/tex;\">c_s<\/script>. <\/div>\n<\/details>\n<\/div>\n<\/li>\n<li>\n<p>Set Multicover: <em>Given a collection <script type=\"math\/tex;\">C<\/script> of sets, where each set <script type=\"math\/tex;\">s\\in C<\/script> has a cost <script type=\"math\/tex;\">c_s<\/script>, and an integer requirement <script type=\"math\/tex;\">r_e<\/script> for each element <script type=\"math\/tex;\">e<\/script>, choose a minimum-cost collection of the sets so that each element <script type=\"math\/tex;\">e<\/script> is contained in at least <script type=\"math\/tex;\">r_e<\/script> of the chosen sets. Each set can only be chosen once.<\/em> The approximation ratio is <script type=\"math\/tex;\">{\\rm H}(d)<\/script>, where <script type=\"math\/tex;\">d<\/script> is the maximum size of any single set <script type=\"math\/tex;\">s\\in C<\/script>. <\/p>\n<div class=\"expandable\" id=\"a0000000008\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Explanation\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Explanation\u2026<\/summary>\n<div class=\"collapseomatic_content\"> The underlying submodular function is the sum, over the elements <script type=\"math\/tex;\">e<\/script>, of the number of chosen sets covering <script type=\"math\/tex;\">e<\/script> (or <script type=\"math\/tex;\">r_e<\/script>, whichever is smaller). The greedy algorithm repeatedly chooses a not-yet-chosen set <script type=\"math\/tex;\">s\\in C<\/script> to maximize the increase in this function, divided by the cost <script type=\"math\/tex;\">c_s<\/script>. <\/div>\n<\/details>\n<\/div>\n<\/li>\n<li>\n<p><em>Given a collection <script type=\"math\/tex;\">C<\/script> of sets of vectors of <script type=\"math\/tex;\">{\\mathbb R}^n<\/script>, where each set <script type=\"math\/tex;\">s\\in C<\/script> has a cost <script type=\"math\/tex;\">c_s<\/script>, choose a minimum-cost collection of the sets so that their union spans <script type=\"math\/tex;\">{\\mathbb R}^n<\/script>.<\/em> The approximation ratio is <script type=\"math\/tex;\">{\\rm H}(d)<\/script>, where <script type=\"math\/tex;\">d<\/script> is the maximum rank of any single set <script type=\"math\/tex;\">s\\in C<\/script>. <\/p>\n<div class=\"expandable\" id=\"a0000000009\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Explanation\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Explanation\u2026<\/summary>\n<div class=\"collapseomatic_content\"> The submodular function is the vector rank of the union of the sets chosen so far. The greedy algorithm repeatedly chooses a set <script type=\"math\/tex;\">s\\in C<\/script> that maximizes the increase in this quantity, divided by the cost <script type=\"math\/tex;\">c_s<\/script>. <\/div>\n<\/details>\n<\/div>\n<\/li>\n<li>\n<p><em>Given a collection <script type=\"math\/tex;\">C<\/script> of sets of edges in a graph <script type=\"math\/tex;\">G=(V,E)<\/script>, choose a minimum-cost collection of the sets so that their union connects the graph.<\/em> The approximation ratio is <script type=\"math\/tex;\">{\\rm H}(d)<\/script>, where <script type=\"math\/tex;\">d<\/script> is the maximum size of any set <script type=\"math\/tex;\">s\\in C<\/script>. If <script type=\"math\/tex;\">d=1<\/script> the problem is MST, the algorithm gives 1-approximation (it reduces to Kruskal\u2019s algorithm). <\/p>\n<div class=\"expandable\" id=\"a0000000010\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Explanation\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Explanation\u2026<\/summary>\n<div class=\"collapseomatic_content\"> The submodular function is <script type=\"math\/tex;\">|V|<\/script> minus the number of connected components in the subgraph formed by the edges in chosen sets. The greedy algorithm repeatedly chooses a set <script type=\"math\/tex;\">s<\/script> that maximizes the increase in this quantity, divided by the cost <script type=\"math\/tex;\">c_s<\/script>. <\/div>\n<\/details>\n<\/div>\n<\/li>\n<\/ul>\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\">An open problem<\/h1>\n<p> One of the most natural generalizations of Set Cover is Integer Covering with upper bounds on the variables, that is, <script type=\"math\/tex;\">\\min \\{ c\\cdot x ~ |~  Ax\\ge b, ~ x_j\\in \\{ 0,1\\} \\} <\/script> where each <script type=\"math\/tex;\">A_{ij},b_i\\in {\\mathbb R}_+<\/script>. (To model a more general constraint <script type=\"math\/tex;\">x_j\\in \\{ 0,1,\\ldots ,u_j\\} <\/script> for a variable <script type=\"math\/tex;\">x_j<\/script>, just replace each variable <script type=\"math\/tex;\">x_j<\/script> with <script type=\"math\/tex;\">u_j<\/script> copies.) <\/p>\n<p>A nice open question is whether the <script type=\"math\/tex;\">{\\rm H}(d)<\/script> approximation ratio (or perhaps a <script type=\"math\/tex;\">2{\\rm H}(d)<\/script> ratio) can be shown for any natural greedy algorithm for this problem, where <script type=\"math\/tex;\">d<\/script> is the maximum number of constraints in which any variable appears. An <script type=\"math\/tex;\">O(\\log d)<\/script>-approximation algorithm is known for the problem, but it is not a greedy algorithm\u00a0<span class=\"cite\">[<a href=\"#Kolliopoulos01Tight\">1<\/a>]<\/span>. <\/p>\n<p>For this problem, it is natural to define the underlying submodular function by <script type=\"math\/tex;\">f(x) = \\sum _i \\min (A_i x, b_i)<\/script> or <script type=\"math\/tex;\">g(x) = \\sum _i \\min (A_i x\/b_i, 1)<\/script>. But for these functions, none of Wolsey\u2019s three quantities above <script type=\"math\/tex;\">(\\lambda _1,\\lambda _2,\\lambda _3)<\/script> are bounded independent of <script type=\"math\/tex;\">A<\/script> and <script type=\"math\/tex;\">b<\/script>. <\/p>\n<p>The question is resolved positively for for two slightly easier problems: <\/p>\n<ul class=\"itemize\">\n<li>\n<p><script type=\"math\/tex;\">\\min \\{ \\, c\\cdot x ~ |~  Ax\\ge 1,~  x_j\\in {\\mathbb N}_{\\ge 0}\\} <\/script> (no upper bounds on the variables), and <\/p>\n<\/li>\n<li>\n<p><script type=\"math\/tex;\">\\min \\big\\{ \\, c\\cdot x ~ |~  Ax\\ge b,~  x_j\\in \\{ 0,1\\} \\big\\} <\/script> where <script type=\"math\/tex;\">A_{ij}\\in \\{ 0,1\\} <\/script>. (This one is Set Multicover, mentioned previously, for which the function <script type=\"math\/tex;\">f<\/script> above is integer-valued, so Wolsey\u2019s result applies.) <\/p>\n<\/li>\n<\/ul>\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\">Related<\/h1>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Set_cover_problem\">The set-cover problem<\/a> (wikipedia) <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Supermodular_function\">Submodular functions<\/a> (wikipedia) <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/obliv\">Using randomized rounding to derive greedy algorithms<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<div>\n<h1 id=\"bibliography\">Bibliography<\/h1>\n<table class=\"bibliography\" cellspacing=\"0\" cellpadding=\"2\">\n<tr>\n<td valign=\"top\">[<a name=\"Kolliopoulos01Tight\">1<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;S+G++Kolliopoulos+&quot;+author:&quot;+N+E++Young&quot;+intitle:&quot;+Approximation+algorithms+for+covering\/packing+integer+programs&quot;\">S.\u00a0G. Kolliopoulos and N.\u00a0E. Young. Approximation algorithms for covering\/packing integer programs. <em>Journal of Computer and System Sciences<\/em>, 71(4):495\u2013505, 2005. Preliminary version appeared in FOCS\u201901. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Nemhauser88Integer\">2<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;G+L++Nemhauser+&quot;+author:&quot;+L+A++Wolsey&quot;+intitle:&quot;+Integer+and+Combinatorial+Optimization&quot;\">G.\u00a0L. Nemhauser and L.\u00a0A. Wolsey. <em>Integer and Combinatorial Optimization<\/em>. John Wiley &amp; Sons, New York, 1988. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"wolsey1982analysis\">3<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;L+Wolsey&quot;+intitle:&quot;+An+analysis+of+the+greedy+algorithm+for+the+submodular+set+covering+problem&quot;\">L.\u00a0Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. <em>Combinatorica<\/em>, 2(4):385\u2013393, 1982. <\/a><\/td>\n<\/tr>\n<\/table><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<div id=\"footnotes\">\n<div>\n<h2>Footnotes<\/h2>\n<ol>\n<li id=\"a0000000005\"><script type=\"math\/tex;\">f<\/script> is submodular if <script type=\"math\/tex;\">f(S\\cup \\{ b\\} ) - f(S) \\ge f(S\\cup \\{ a,b\\} ) - f(S\\cup \\{ a\\} )<\/script> for any <script type=\"math\/tex;\">S\\subset C<\/script> and <script type=\"math\/tex;\">a,b\\in C<\/script>. That is, adding <script type=\"math\/tex;\">b<\/script> to the current set <script type=\"math\/tex;\">S<\/script> gives at least as much benefit as would adding <script type=\"math\/tex;\">b<\/script> after adding <script type=\"math\/tex;\">a<\/script>. Intuitively, adding <script type=\"math\/tex;\">a<\/script> cannot make it better to add <script type=\"math\/tex;\">b<\/script>. The key property for the analysis of the greedy algorithm is the following: if adding a set <script type=\"math\/tex;\">A<\/script> of elements would increase <script type=\"math\/tex;\">f<\/script> by at least <script type=\"math\/tex;\">\\delta <\/script>, then there must be at least one element in <script type=\"math\/tex;\">A<\/script> that, if added by itself, would increase <script type=\"math\/tex;\">f<\/script> by at least <script type=\"math\/tex;\">\\delta \/|A|<\/script>.<\/li>\n<\/ol><\/div>\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Wolsey\u2019s generalization of the greedy Set-Cover algorithm to a large class of problems. It is natural to ask what general classes of problems the greedy Set-Cover algorithm generalizes to. Here we describe one such class, due to Wolsey (1982), that captures many, but not all, such problems.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8676,"menu_order":6,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1234","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/1234","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=1234"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/1234\/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=1234"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}