{"id":8575,"date":"2014-12-07T10:43:30","date_gmt":"2014-12-07T18:43:30","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=8575"},"modified":"2026-09-30T09:15:31","modified_gmt":"2026-09-30T17:15:31","slug":"smu-fast","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-multicover-unconstrained\/smu-fast\/","title":{"rendered":"Non-uniform increments"},"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>Applying non-uniform increments to unconstrained Set Multicover.<\/em><\/center><\/p><\/blockquote>\n<p>  The algorithm in the previous note can be exponentially slow. Here we use non-uniform increments to give a faster rounding scheme and algorithm.<!--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\/smu-slow\"><script type=\"math\/tex;\">{\\rm H}(n)<\/script>-approximation for unconstrained Set Multicover<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/increments\">The general idea of non-uniform increments<\/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 rounding scheme<\/h1>\n<p>For any multicover vector <script type=\"math\/tex;\">\\tilde x<\/script>, let <script type=\"math\/tex;\">\\tilde x(e)<\/script> denote the coverage of <script type=\"math\/tex;\">e<\/script>, that is, <script type=\"math\/tex;\">\\sum _{s\\ni e} \\tilde{x_s}<\/script>. <\/p>\n<p>Here is a rounding scheme with non-uniform increments: <\/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> fractional multicover <script type=\"math\/tex;\">x<\/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> multicover <script type=\"math\/tex;\">\\tilde x<\/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;\">\\tilde x_s = 0<\/script> for every set <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\"> Repeat until every element is covered: <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:1em\"> For each element <script type=\"math\/tex;\">e<\/script>, let <script type=\"math\/tex;\">\\tilde d_e = \\max \\{ 0, d_e - \\tilde x(e)\\} <\/script> denote its residual demand. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">4.<\/td>\n<td style=\"padding-left:1em\"> For each set <script type=\"math\/tex;\">s<\/script>, fix an arbitrary integer increment <script type=\"math\/tex;\">\\delta _s\\in [1, \\min _{e\\in s} d_e]<\/script>, <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">5.<\/td>\n<td style=\"padding-left:1em\"> and define probability <script type=\"math\/tex;\">p_j \\, =\\,  \\alpha \\,  x_j\/\\delta _j<\/script> (choosing <script type=\"math\/tex;\">\\alpha <\/script> so <script type=\"math\/tex;\">|p| = 1<\/script>). <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">6.<\/td>\n<td style=\"padding-left:1em\"> Sample a set <script type=\"math\/tex;\">s<\/script> from the distribution <script type=\"math\/tex;\">p<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">7.<\/td>\n<td style=\"padding-left:1em\"> Increase <script type=\"math\/tex;\">\\tilde x_s<\/script> by <script type=\"math\/tex;\">\\delta _s<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">8.<\/td>\n<td style=\"padding-left:0em\"> Return <script type=\"math\/tex;\">\\tilde x<\/script>. <\/td>\n<\/tr>\n<\/table>\n<div id=\"a0000000005\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma <\/b> (existence proof).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Fix a problem instance. Let <script type=\"math\/tex;\">n<\/script> be the number of elements. The multiset cover <script type=\"math\/tex;\">\\tilde x<\/script> returned by the rounding scheme has expected cost at most <script type=\"math\/tex;\">{\\rm H}(n)\\, c\\cdot x<\/script>. <\/p>\n<\/div><\/div>\n<div class=\"expandable\" id=\"a0000000006\" 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> For the special case with unit increments (where <script type=\"math\/tex;\">\\delta _s = 1<\/script> for all sets in every iteration) we showed <script type=\"math\/tex;\">{\\rm H}(n)<\/script>-approximation in <a href=\"http:\/\/algnotes.info\/on\/set-multicover-unconstrained\">this example<\/a>. The proof is a trivial generalization of that proof. <\/p>\n<p>Let stopping time <script type=\"math\/tex;\">T<\/script> be the number of samples. As the rounding scheme proceeds, after <script type=\"math\/tex;\">t<\/script> samples, recall that the <em>fractional number uncovered<\/em> is <\/p>\n<div id=\"a0000000007\" class=\"equation\"><script type=\"math\/tex; mode=display\">  n_t = \\sum _e \\max \\{ 0, \\,  1-\\tilde x(e)\/d_e\\} .  <\/script><\/div>\n<p> Recall, from the method of conditional probabilities in the previous proof, that the pessimistic estimator was <\/p>\n<div id=\"a0000000008\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\phi _t ~ =~  c\\cdot \\tilde x \\, +\\,  \\tilde{\\rm H}(n_t) \\, c\\cdot x,  <\/script><\/div>\n<p> where <script type=\"math\/tex;\">\\tilde{\\rm H}(y) = \\int _{0}^y 1\/\\lceil z \\rceil \\,  dz<\/script>. <\/p>\n<p>We re-use the same pessimistic estimator here. (But to analyze the rounding scheme!) <\/p>\n<p>Following the inequalities from the previous proof, when a set <script type=\"math\/tex;\">s<\/script> is chosen in iteration <script type=\"math\/tex;\">t+1<\/script> and <script type=\"math\/tex;\">\\tilde x_s<\/script> is increased by <script type=\"math\/tex;\">\\delta _s<\/script>, (letting <script type=\"math\/tex;\">\\delta <\/script> and <script type=\"math\/tex;\">\\alpha <\/script> denote their values at the start of iteration <script type=\"math\/tex;\">t+1<\/script>) the increase in the pessimistic estimator satisfies <\/p>\n<div id=\"a0000000009\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{align}  \\phi _{t+1} - \\phi _{t} ~ \\le ~ &  \\delta _s c_{s} \\, -\\,  \\frac{n_{t} - n_{t+1}}{\\lceil n_t\\rceil }\\, c\\cdot x \\notag \\\\ ~ =~ &  \\delta _s c_{s} \\, -\\,  \\frac{c\\cdot x}{\\lceil n_t\\rceil }\\sum _{\\tilde x(e)\\lt d_e}\\frac{[e\\in s]\\delta _s}{d_e}. \\label{bound} \\end{align}<\/script><\/div>\n<p>We claim that in expectation,\u00a0\\eqref{bound} is non-positive. Before we prove the claim, note that it implies the lemma, because it implies that by Wald\u2019s the expectation of the final value <script type=\"math\/tex;\">\\phi _T<\/script> is at most the initial value <script type=\"math\/tex;\">\\phi _0<\/script>; and the final value <script type=\"math\/tex;\">\\phi _T<\/script> equals the cost of <script type=\"math\/tex;\">\\tilde x<\/script> (because <script type=\"math\/tex;\">\\tilde h(n_T) = 0<\/script>), while the initial value <script type=\"math\/tex;\">\\phi _0<\/script> is <script type=\"math\/tex;\">{\\rm H}(n)\\, c\\cdot x<\/script>. <\/p>\n<p>To finish we observe that\u00a0\\eqref{bound} is non-positive in expectation. <\/p>\n<p>The expectation of the first term <script type=\"math\/tex;\">\\delta _s c_s<\/script>, by calculation, is <script type=\"math\/tex;\">\\sum _s p_s\\,  \\delta _s\\,  c_s = \\sum _s \\alpha \\,  x_s\\,  c_s = \\alpha \\,  c \\cdot x<\/script>. <\/p>\n<p>For each element <script type=\"math\/tex;\">e<\/script>, for random <script type=\"math\/tex;\">s<\/script>, the expectation of <script type=\"math\/tex;\">[e\\in s]\\delta _s\/d_e<\/script> is <script type=\"math\/tex;\">\\sum _{s\\ni e} p_s \\delta _s\/d_e = \\sum _{s\\ni e} \\alpha x_s\/d_e \\ge \\alpha <\/script>. <\/p>\n<p>Given <script type=\"math\/tex;\">n_t<\/script>, there are a minimum of <script type=\"math\/tex;\">\\lceil n_t \\rceil <\/script> such not-fully-covered elements. Hence the expectation of the sum in\u00a0\\eqref{bound} is at least <script type=\"math\/tex;\">\\alpha \\lceil n_t\\rceil <\/script>. The claim follows. <\/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=\"a0000000010\">Applying the method of conditional probabilities<\/h1>\n<div id=\"a0000000011\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma <\/b> (algorithm).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Applying the method of conditional probabilities to the existence proof yields the algorithm below: <\/p>\n<\/div><\/div>\n<table id=\"a0000000012\" 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> Set Multicover instance<\/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> multicover <script type=\"math\/tex;\">\\tilde x<\/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;\">\\tilde x_s = 0<\/script> for every set <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\"> Repeat until every element is covered: <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:1em\"> Choose a set <script type=\"math\/tex;\">s<\/script> to maximize <script type=\"math\/tex;\">\\displaystyle \\sum _{e\\in s : \\tilde x(e) \\lt d_e} \\frac{1}{c_s d_e}<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">4.<\/td>\n<td style=\"padding-left:1em\"> Increase <script type=\"math\/tex;\">\\tilde x_s<\/script> by any integer <script type=\"math\/tex;\">\\delta _s \\le \\min _{e\\in s} d_e - \\tilde x(e)<\/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;\">\\tilde x<\/script>. <\/td>\n<\/tr>\n<\/table>\n<div id=\"a0000000013\" class=\"latex-paragraph latex-proof\">\n<div class=\"latex-paragraph-heading\"> <b>Proof sketch.<\/b>  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> We claim the algorithm keeps the pessimistic estimator <script type=\"math\/tex;\">\\phi _t<\/script> (defined in the existence proof) from increasing. Indeed, the algorithm\u2019s choice of <script type=\"math\/tex;\">s<\/script> is the same as in the algorithm with unit increments, and, which, as shown in <a href=\"http:\/\/algnotes.info\/on\/set-multicover-unconstrained\">that derivation<\/a>, ensures that <\/p>\n<div id=\"a0000000014\" class=\"equation\"><script type=\"math\/tex; mode=display\">  c_{s} ~ \\le ~  \\frac{c\\cdot x}{\\lceil n_t\\rceil }\\sum _{\\tilde x(e)\\lt d_e}\\frac{[e\\in s]}{d_e}.  <\/script><\/div>\n<p> By inspection, this inequality is equivalent to the upper bound\u00a0\\eqref{bound} on the increase in the pessimistic estimator (from the existence proof) being non-positive. <\/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<p>This performance guarantee follows as a corollary: <\/p>\n<div id=\"a0000000015\" 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>The algorithm above returns a multicover of cost at most <script type=\"math\/tex;\">{\\rm H}(n)\\, {\\textsc{opt}}<\/script>, where <script type=\"math\/tex;\">{\\textsc{opt}}<\/script> is the minimum cost of any fractional multicover. <\/p>\n<\/div><\/div>\n<p>In hindsight, this theorem has a more direct proof: by inspection, the algorithm above is a direct simulation of the algorithm for unit increments (choosing <script type=\"math\/tex;\">\\delta _s \\gt 1<\/script> corresponds to simulating <script type=\"math\/tex;\">\\delta _s<\/script> iterations of unit increments \u2014 once the unit-increment algorithm chooses a particular set <script type=\"math\/tex;\">s<\/script>, it will remain a valid choice for at least <script type=\"math\/tex;\">\\delta _s<\/script> more iterations). <\/p>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b>Choosing the increments to guarantee iteration count.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Finally, if the algorithm chooses each increment <script type=\"math\/tex;\">\\delta _s<\/script> maximally, then each sample (or iteration) will satisfy the demand of at least one element, so the number of samples (or iterations) will be at most the number of elements <script type=\"math\/tex;\">n<\/script>. <\/p>\n<\/div><\/div>\n<\/div><\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Applying non-uniform increments to unconstrained Set Multicover. The algorithm in the previous note can be exponentially slow. Here we use non-uniform increments to give a faster rounding scheme and algorithm.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8571,"menu_order":6,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8575","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8575","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=8575"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8575\/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=8575"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}