{"id":8571,"date":"2014-12-07T10:43:04","date_gmt":"2014-12-07T18:43:04","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=8571"},"modified":"2026-09-30T09:15:37","modified_gmt":"2026-09-30T17:15:37","slug":"set-multicover-unconstrained","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-multicover-unconstrained\/","title":{"rendered":"Unconstrained Set Multicover"},"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>Several entries on unconstrained Set Multicover.<\/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>Problem definition: <em>Unconstrained Set Multicover<\/em>. The problem is a generalization of Set Cover. An instance is specified by a weighted Set Cover instance, along with an integer demand <script type=\"math\/tex;\">d_e\\gt 0<\/script> for every element <script type=\"math\/tex;\">e<\/script>. A <em>fractional multicover<\/em> <script type=\"math\/tex;\">x<\/script> assigns a weight (multiplicity) <script type=\"math\/tex;\">x_s<\/script> to each set <script type=\"math\/tex;\">s<\/script> such that, for every element <script type=\"math\/tex;\">e<\/script>, the total weight assigned to sets containing <script type=\"math\/tex;\">e<\/script> is at least <script type=\"math\/tex;\">d_e<\/script>. If each multiplicity <script type=\"math\/tex;\">x_s<\/script> is an integer, then <script type=\"math\/tex;\">x<\/script> is called just a <em>multicover<\/em>. The goal is to find a multicover of minimum cost, <script type=\"math\/tex;\">c\\cdot x = \\sum _s c_s x_s<\/script>. <\/p>\n<p>The name \u201cSet Multicover\u201d conventionally refers to the variant of the above problem with the added constraint that each set can be taken at most once (<script type=\"math\/tex;\">\\forall s. x_s\\le 1<\/script>). Sometimes, this variant is called \u201cconstrained\u201d Set Multicover \u00a0<span class=\"cite\">[<a href=\"#Vazirani03Approximation\">1<\/a>, Ch.13]<\/span>. <\/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\">Entries on unconstrained Set Multicover<\/h1>\n<div class=\"ccchildpages\"><article class=\"hentry ccchildpage\">\r\n<header class=\"entry-header\">\r\n<h1 class=\"entry-title\">\r\n<a href=\"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-multicover-unconstrained\/smu-reduction\/\" class=\"\">Reduction to Set Cover<\/a>\r\n<\/h1>\r\n<\/header>\r\n<div class=\"entry-summary\">\r\n<div class=\"latex-file\"><div class=\"latex-document\"> <div class=\"latex-outer-sheet\"><div class=\"latex-inner-sheet\"> <p><blockquote class=\"quote\"><center><em>Unconstrained Set Multicover reduces to Set Cover.<\/em><\/center><\/blockquote>  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.\r\n<!--- a href=\"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-multicover-unconstrained\/smu-reduction\/\" class=\"\">More...<\/a --->\r\n<\/div>\r\n<footer class=\"entry-meta\">\r\n<\/footer>\r\n<\/article><article class=\"hentry ccchildpage\">\r\n<header class=\"entry-header\">\r\n<h1 class=\"entry-title\">\r\n<a href=\"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-multicover-unconstrained\/smu-slow\/\" class=\"\">A greedy algorithm for unconstrained Set Multicover<\/a>\r\n<\/h1>\r\n<\/header>\r\n<div class=\"entry-summary\">\r\n<div class=\"latex-file\"><div class=\"latex-document\"> <div class=\"latex-outer-sheet\"><div class=\"latex-inner-sheet\"> <p><blockquote class=\"quote\"><center><em><script type=\"math\/tex;\">{\\rm H}(n)<\/script>-approximation for unconstrained Set Multicover by oblivious randomized rounding.<\/em><\/center><\/blockquote>  This example illustrates the use of \u201cWald\u2019s equation for dependent decrements\u201d. The rounding scheme and algorithm can be exponentially slow. In a later example, we speed it up using non-uniform increments.\r\n<!--- a href=\"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-multicover-unconstrained\/smu-slow\/\" class=\"\">More...<\/a --->\r\n<\/div>\r\n<footer class=\"entry-meta\">\r\n<\/footer>\r\n<\/article><article class=\"hentry ccchildpage\">\r\n<header class=\"entry-header\">\r\n<h1 class=\"entry-title\">\r\n<a href=\"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-multicover-unconstrained\/smu-fast\/\" class=\"\">Non-uniform increments<\/a>\r\n<\/h1>\r\n<\/header>\r\n<div class=\"entry-summary\">\r\n<div class=\"latex-file\"><div class=\"latex-document\"> <div class=\"latex-outer-sheet\"><div class=\"latex-inner-sheet\"> <p><blockquote class=\"quote\"><center><em>Applying non-uniform increments to unconstrained Set Multicover.<\/em><\/center><\/blockquote>  The algorithm in the previous note can be exponentially slow. Here we use non-uniform increments to give a faster rounding scheme and algorithm.\r\n<!--- a href=\"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-multicover-unconstrained\/smu-fast\/\" class=\"\">More...<\/a --->\r\n<\/div>\r\n<footer class=\"entry-meta\">\r\n<\/footer>\r\n<\/article><\/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=\"a0000000004\">Questions for later<\/h1>\n<p>Generalize results here to <em>constrained<\/em> Set Multicover (where the solution must take each set <script type=\"math\/tex;\">s<\/script> at most once). Aim for <script type=\"math\/tex;\">{\\rm H}(\\max _s |s|)<\/script>-approximation (matching Wolsey). <\/p>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000005\">Related<\/h2>\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<\/ul>\n<\/div>\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>Several entries on unconstrained Set Multicover. \u00a0<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8640,"menu_order":9,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8571","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8571","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=8571"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8571\/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=8571"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}