{"id":8577,"date":"2014-12-07T10:43:44","date_gmt":"2014-12-07T18:43:44","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=8577"},"modified":"2026-09-30T09:15:40","modified_gmt":"2026-09-30T17:15:40","slug":"smu-reduction","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-multicover-unconstrained\/smu-reduction\/","title":{"rendered":"Reduction to Set Cover"},"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>Unconstrained Set Multicover reduces to Set Cover.<\/em><\/center><\/p><\/blockquote>\n<p>  Unconstrained Set Multicover has an approximation-preserving reduction to Set Cover that also preserves maximum set size. This reduction (and previous results on Set Cover) imply that a localized rounding scheme and a greedy algorithm both give <script type=\"math\/tex;\">{\\rm H}(\\max _s |s|)<\/script>-approximation.<!--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\">Set Cover <script type=\"math\/tex;\">{\\rm H}(n)<\/script>-approximation<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/set-multicover-unconstrained\">Unconstrained Set Multicover<\/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 reduction<\/h1>\n<p>Here is the reduction. Fix any instance <script type=\"math\/tex;\">{\\cal I}<\/script> of Unconstrained Set Multicover. Replace each element <script type=\"math\/tex;\">e<\/script> with <script type=\"math\/tex;\">d_e<\/script> <em>duplicates<\/em> of <script type=\"math\/tex;\">e<\/script>. Replace each set <script type=\"math\/tex;\">s<\/script> with <script type=\"math\/tex;\">\\prod _{e\\in s} d_e<\/script> <em>copies<\/em> of <script type=\"math\/tex;\">s<\/script>, where each copy contains exactly one of the duplicates of each element of <script type=\"math\/tex;\">e<\/script>. This gives an instance <script type=\"math\/tex;\">{\\cal I}'<\/script> of Set Cover. The size of each copy of <script type=\"math\/tex;\">s<\/script> is equal to the size of <script type=\"math\/tex;\">s<\/script>. <\/p>\n<div id=\"a0000000004\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma <\/b> (reduction to Set Cover).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> For every unconstrained Set Multicover instance <script type=\"math\/tex;\">{\\cal I}<\/script>, the above Set Cover instance <script type=\"math\/tex;\">{\\cal I}'<\/script> has the same maximum set size and is equivalent, in that the solutions to <script type=\"math\/tex;\">{\\cal I}<\/script> correspond to the solutions to <script type=\"math\/tex;\">{\\cal I}'<\/script>, and the correspondence preserves feasibility, cost, and integrality. <\/p>\n<\/div><\/div>\n<div class=\"expandable\" id=\"a0000000005\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for proof\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for proof\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p> Let <script type=\"math\/tex;\">D_e<\/script> denote the duplicates of <script type=\"math\/tex;\">e<\/script>. Let <script type=\"math\/tex;\">C_s<\/script> denote the copies of <script type=\"math\/tex;\">s<\/script>. <\/p>\n<p>Given any fractional set cover <script type=\"math\/tex;\">x'<\/script> of <script type=\"math\/tex;\">{\\cal I}'<\/script>, define fractional multicover <script type=\"math\/tex;\">x=f(x')<\/script> of <script type=\"math\/tex;\">{\\cal I}<\/script> by taking <script type=\"math\/tex;\">x_s = \\sum _{s'\\in C_s} x'_{s'}<\/script> to be the sum of the sizes of the copies of <script type=\"math\/tex;\">s<\/script> in <script type=\"math\/tex;\">x'<\/script>. Then <script type=\"math\/tex;\">x<\/script> is feasible if <script type=\"math\/tex;\">x'<\/script> is, because, for any element <script type=\"math\/tex;\">e<\/script>, for each of the <script type=\"math\/tex;\">d_e<\/script> duplicates <script type=\"math\/tex;\">e'<\/script> of <script type=\"math\/tex;\">e<\/script>, the weight of sets <script type=\"math\/tex;\">s'<\/script> containing <script type=\"math\/tex;\">e'<\/script> must be at least 1, and each of these sets <script type=\"math\/tex;\">s'<\/script> is a copy of <script type=\"math\/tex;\">s<\/script>: <\/p>\n<div id=\"a0000000006\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\sum _{s\\ni e} x_s ~ =~  \\sum _{s\\ni e} \\sum _{s'\\in C_s} x'_{s'} ~ =~  \\sum _{e'\\in D_e} \\sum _{s'\\ni e'} x'_{s'} ~ \\ge ~  \\sum _{e'\\in D_e} 1 ~ =~  d_e.  <\/script><\/div>\n<p> The cost of <script type=\"math\/tex;\">x<\/script> equals the cost of <script type=\"math\/tex;\">x'<\/script>, and, if <script type=\"math\/tex;\">x'<\/script> is an integer solution, then so is <script type=\"math\/tex;\">x<\/script>. <\/p>\n<p>Conversely, given any fractional multicover <script type=\"math\/tex;\">x<\/script> of <script type=\"math\/tex;\">{\\cal I}<\/script>, define fractional set cover <script type=\"math\/tex;\">x'<\/script> of <script type=\"math\/tex;\">{\\cal I}'<\/script> to be an inverse of <script type=\"math\/tex;\">f<\/script> (so that <script type=\"math\/tex;\">f(x') = x<\/script>), computed as follows. <\/p>\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> fractional multicover <script type=\"math\/tex;\">x<\/script> of <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> fractional set cover <script type=\"math\/tex;\">x'<\/script> of <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\"> Initialize <script type=\"math\/tex;\">x'_{s'} = 0<\/script> for all <script type=\"math\/tex;\">s'<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">2.<\/td>\n<td style=\"padding-left:0em\"> For each set <script type=\"math\/tex;\">s<\/script>: <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:1em\"> Repeat until <script type=\"math\/tex;\">x_s = 0<\/script>: <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">4.<\/td>\n<td style=\"padding-left:2em\"> Shift weight from <script type=\"math\/tex;\">x_s<\/script> to <script type=\"math\/tex;\">x'_{s'}<\/script>, where <script type=\"math\/tex;\">s'<\/script> is any copy of <script type=\"math\/tex;\">s<\/script> such that, <br \/>for each <script type=\"math\/tex;\">e\\in s<\/script>, if some copy of <script type=\"math\/tex;\">e'<\/script> has <script type=\"math\/tex;\">x'(e') \\lt 1<\/script>, then one such <script type=\"math\/tex;\">e'<\/script> is in <script type=\"math\/tex;\">s'<\/script>. <br \/>(Shift weight to <script type=\"math\/tex;\">x'_{s'}<\/script> only as long as the condition on <script type=\"math\/tex;\">s'<\/script> continues to hold.) <\/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;\">x'<\/script>. <\/td>\n<\/tr>\n<\/table>\n<p> The cost of <script type=\"math\/tex;\">x'<\/script> is the same as the cost of <script type=\"math\/tex;\">x<\/script>, and, if <script type=\"math\/tex;\">x<\/script> is an integer solution, then <script type=\"math\/tex;\">x'<\/script> will be too (provided the shifts in line 4 are maximal). <\/p>\n<p>If <script type=\"math\/tex;\">x<\/script> is feasible, then so is <script type=\"math\/tex;\">x'<\/script>, because a total of <script type=\"math\/tex;\">d_e<\/script> units of weight must be shifted to sets containing copies of <script type=\"math\/tex;\">e<\/script>, there are only <script type=\"math\/tex;\">d_e<\/script> such copies, and no copy <script type=\"math\/tex;\">e'<\/script> has <script type=\"math\/tex;\">x'(e')<\/script> greater than 1 unless all copies are covered. <\/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=\"a0000000008\">Rounding scheme and greedy algorithm via reduction<\/h1>\n<p>The corollaries below follow from the reduction: <\/p>\n<div id=\"a0000000009\" class=\"my-theorem latex-paragraph latex-corollary\">\n<div class=\"latex-paragraph-heading\">   <b \"=\"&quot;\">Corollary.<\/b>   <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>The localized rounding scheme for unconstrained Set Multicover returns a cover of expected cost at most <script type=\"math\/tex;\">\\sum _s {\\rm H}(|s|) c_s x_s<\/script>, which is at most <script type=\"math\/tex;\">{\\rm H}(\\max _s |s|) ~ c\\cdot x<\/script>. <\/p>\n<\/div><\/div>\n<div class=\"expandable\" id=\"a0000000010\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for proof\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for proof\u2026<\/summary>\n<div class=\"collapseomatic_content\"> Running the localized rounding scheme on a fractional solution <script type=\"math\/tex;\">x<\/script> of <script type=\"math\/tex;\">{\\cal I}<\/script> and returning <script type=\"math\/tex;\">\\tilde x<\/script> corresponds to running the localized rounding scheme for Set Cover on the fractional solution <script type=\"math\/tex;\">x'=f^{-1}(x)<\/script> on <script type=\"math\/tex;\">{\\cal I}'<\/script>, where <script type=\"math\/tex;\">f<\/script> is as described in the reduction above, then returning <script type=\"math\/tex;\">\\tilde x = f(\\tilde x')<\/script>, where <script type=\"math\/tex;\">\\tilde x'<\/script> is the rounded solution for <script type=\"math\/tex;\">{\\cal I}'<\/script>. The cost of <script type=\"math\/tex;\">\\tilde x<\/script> equals the cost of <script type=\"math\/tex;\">\\tilde x'<\/script>. We know that the expected cost of <script type=\"math\/tex;\">\\tilde x'<\/script> is at most <script type=\"math\/tex;\">\\sum _{s'\\in {\\cal I}'} {\\rm H}(|s'|) c_s x'_{s'}<\/script> (<a href=\"http:\/\/algnotes.info\/on\/set-cover-local\">proven here<\/a>), which equals <script type=\"math\/tex;\">\\sum _{s\\in {\\cal I}} {\\rm H}(|s|) c_s x_{s}<\/script>. <\/div>\n<\/details>\n<\/div>\n<p>Consider the following greedy algorithm for unconstrained Set Multicover: <em>Start with each <script type=\"math\/tex;\">\\tilde x_s = 0<\/script>. At each iteration, choose <script type=\"math\/tex;\">s<\/script> minimizing the ratio of <script type=\"math\/tex;\">c_s<\/script> to the number of not-yet-satisfied elements in <script type=\"math\/tex;\">s<\/script>, then increment <script type=\"math\/tex;\">\\tilde{x_s}<\/script>.<\/em> <\/p>\n<div id=\"a0000000011\" class=\"my-theorem latex-paragraph latex-corollary\">\n<div class=\"latex-paragraph-heading\">   <b \"=\"&quot;\">Corollary.<\/b>   <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>That greedy algorithm returns a cover of cost at most <script type=\"math\/tex;\">\\sum _s{\\rm H}(|s|) c_s x_s<\/script>, which is at most <script type=\"math\/tex;\">{\\rm H}(\\max _s |s|) ~ c\\cdot x<\/script>. <\/p>\n<\/div><\/div>\n<div class=\"expandable\" id=\"a0000000012\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for proof\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for proof\u2026<\/summary>\n<div class=\"collapseomatic_content\"> Running that greedy algorithm on a fractional solution <script type=\"math\/tex;\">x<\/script> of <script type=\"math\/tex;\">{\\cal I}<\/script> and returning <script type=\"math\/tex;\">\\tilde x<\/script> corresponds to running the greedy algorithm for Set Cover on the fractional solution <script type=\"math\/tex;\">x'=f^{-1}(x)<\/script> on <script type=\"math\/tex;\">{\\cal I}'<\/script>, where <script type=\"math\/tex;\">f<\/script> is as described in the reduction above, then returning <script type=\"math\/tex;\">\\tilde x = f(\\tilde x')<\/script>, where <script type=\"math\/tex;\">\\tilde x'<\/script> is the rounded solution for <script type=\"math\/tex;\">{\\cal I}'<\/script>. The cost of <script type=\"math\/tex;\">\\tilde x<\/script> equals the cost of <script type=\"math\/tex;\">\\tilde x'<\/script>. We know that the cost of <script type=\"math\/tex;\">\\tilde x'<\/script> is at most <script type=\"math\/tex;\">\\sum _{s'\\in {\\cal I}'} {\\rm H}(|s'|) c_s x'_{s'}<\/script> (<a href=\"http:\/\/algnotes.info\/on\/set-cover-local\">proven here<\/a>), which equals <script type=\"math\/tex;\">\\sum _{s\\in {\\cal I}} {\\rm H}(|s|) c_s x_{s}<\/script>. <\/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=\"a0000000013\">Related<\/h1>\n<ul class=\"itemize\">\n<li>\n<p>\u00a0<span class=\"cite\">[<a href=\"#Vazirani03Approximation\">1<\/a>, Exercise 13.4.1]<\/span> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/set-multicover-unconstrained\">Other entries on unconstrained Set Multicover<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/set-cover-Wolsey\">Wolsey\u2019s generalization of greedy set cover<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<div class=\"latex-section\">\n<h1 id=\"a0000000014\">Questions for later<\/h1>\n<p>Generalize to <em>constrained<\/em> Set Multicover (where the solution must take each set <script type=\"math\/tex;\">s<\/script> at most once). (The Knapsack-cover inequalities give a reduction, but it increases <script type=\"math\/tex;\">\\max _s |s|<\/script>.) Aim for <script type=\"math\/tex;\">{\\rm H}(\\max _s |s|)<\/script>-approximation (matching Wolsey). <\/p>\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=\"Vazirani03Approximation\">1<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;V+Vazirani&quot;+intitle:&quot;+Approximation+Algorithms&quot;\">V.\u00a0Vazirani. <em>Approximation Algorithms<\/em>. Springer Verlag, 2003. <\/a><\/td>\n<\/tr>\n<\/table><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Unconstrained Set Multicover reduces to Set Cover. Unconstrained Set Multicover has an approximation-preserving reduction to Set Cover that also preserves maximum set size. This reduction (and previous results on Set Cover) imply that a localized rounding scheme and a greedy algorithm both give -approximation.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8571,"menu_order":1,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8577","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8577","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=8577"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8577\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8571"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=8577"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}