{"id":8573,"date":"2014-12-07T10:43:18","date_gmt":"2014-12-07T18:43:18","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=8573"},"modified":"2026-09-30T09:15:34","modified_gmt":"2026-09-30T17:15:34","slug":"smu-slow","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-multicover-unconstrained\/smu-slow\/","title":{"rendered":"A greedy algorithm for 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><script type=\"math\/tex;\">{\\rm H}(n)<\/script>-approximation for unconstrained Set Multicover by oblivious randomized rounding.<\/em><\/center><\/p><\/blockquote>\n<p>  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.<!--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\/walds-dependent\">Wald\u2019s equation for dependent decrements<\/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 rounding scheme<\/h1>\n<p> Fix an instance of unconstrained Set Multicover. Here is the rounding scheme: <\/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\"> Sample a set <script type=\"math\/tex;\">s<\/script> from the distribution <script type=\"math\/tex;\">x\/|x|<\/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 1. <\/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=\"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 set 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> The proof generalizes <a href=\"http:\/\/algnotes.info\/on\/set-cover-weighted\">the proof of the <script type=\"math\/tex;\">{\\rm H}(n)<\/script>-approximation for weighted Set Cover<\/a>. <\/p>\n<p>Let <script type=\"math\/tex;\">\\tilde x(e) = \\sum _{s\\ni e} \\tilde{x_s}<\/script> denote the extent to which <script type=\"math\/tex;\">\\tilde x<\/script> covers element <script type=\"math\/tex;\">e<\/script>. As the rounding scheme proceeds, after <script type=\"math\/tex;\">t<\/script> samples, define the <em>fractional number uncovered<\/em> to be <\/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> Intuitively, this counts the \u201cnumber\u201d of elements left to cover, where an element <script type=\"math\/tex;\">e<\/script> is counted as fractionally covered when its coverage <script type=\"math\/tex;\">\\tilde x(e)<\/script> is less than its demand <script type=\"math\/tex;\">d_e<\/script>. <\/p>\n<p>For each element <script type=\"math\/tex;\">e<\/script> that is not yet fully covered, the next sample will increase the coverage <script type=\"math\/tex;\">\\tilde x(e)<\/script> of <script type=\"math\/tex;\">e<\/script> by 1 with probability at least <script type=\"math\/tex;\">d_e\/|x|<\/script>. (The probability is <script type=\"math\/tex;\">\\sum _{s\\ni e} x_s\/|x| \\ge d_e\/|x|<\/script>.) Thus, in expectation, <script type=\"math\/tex;\">\\tilde x(e)<\/script> will increase by at least <script type=\"math\/tex;\">d_e\/|x|<\/script>, so, in expectation, <script type=\"math\/tex;\">1-\\tilde x(e)\/d_e<\/script> will decrease by at least <script type=\"math\/tex;\">1\/|x|<\/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, inspecting the definition of <script type=\"math\/tex;\">n_t<\/script>, the next sample will decrease it by at least <script type=\"math\/tex;\">\\lceil n_t \\rceil \/|x|<\/script> in expectation: <\/p>\n<div id=\"a0000000008\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\textrm{E}[n_{t} - n_{t+1} \\, |\\, n_t] ~ \\ge ~  \\lceil n_t \\rceil \/ |x|.  <\/script><\/div>\n<p> By <a href=\"http:\/\/algnotes.info\/on\/Walds-dependent\">Wald\u2019s for dependent decrements<\/a> (being careful to use the ceiling in the inequality above), this implies that the number of samples, <script type=\"math\/tex;\">T<\/script>, before all elements are covered has expectation <\/p>\n<div id=\"a0000000009\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\textstyle \\textrm{E}[T] ~ \\le ~  \\int _0^{n} |x| \/ \\lceil z \\rceil \\, dz ~ =~  |x|\\,  {\\rm H}(n).  <\/script><\/div>\n<p>Each of the <script type=\"math\/tex;\">T<\/script> sampled sets contributes <script type=\"math\/tex;\">\\sum _s (x_s\/|x|) c_s = c\\cdot x\/|x|<\/script> in expectation to the final cost of <script type=\"math\/tex;\">\\tilde x<\/script>. So, by Wald\u2019s equation, the total expected cost is at most <script type=\"math\/tex;\">(c\\cdot x\/|x|) \\textrm{E}[T] \\le c\\cdot x\\,  {\\rm H}(n)<\/script>. <\/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 1. <\/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<p>This greedy algorithm differs from the one following from <a href=\"http:\/\/algnotes.info\/on\/smu-reduction\">the reduction to Set Cover<\/a>, in that, in choosing <script type=\"math\/tex;\">s<\/script>, it gives each element weight <script type=\"math\/tex;\">1\/d_e<\/script> instead of <script type=\"math\/tex;\">1<\/script>. <\/p>\n<div class=\"expandable\" id=\"a0000000013\" 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 random variable <script type=\"math\/tex;\">Q<\/script> be the cost of the final cover <script type=\"math\/tex;\">\\tilde x<\/script>. The algorithm will keep the conditional expectation of <script type=\"math\/tex;\">Q<\/script> below <script type=\"math\/tex;\">{\\rm H}(n)\\, c\\cdot x<\/script>. <\/p>\n<p>Let <script type=\"math\/tex;\">\\tilde x<\/script> denote the rounded solution after <script type=\"math\/tex;\">t<\/script> samples. Define <script type=\"math\/tex;\">n_t<\/script> to be the fractional number uncovered (elements) as in the existence proof. Reasoning as in the existence proof (and from the proof of Wald\u2019s for dependent decrements), <\/p>\n<ol class=\"enumerate\">\n<li value=\"1\">\n<p>The expected number <script type=\"math\/tex;\">T-t<\/script> of samples needed to fully cover the remaining elements is at most <script type=\"math\/tex;\">|x|\\tilde{\\rm H}(n_t)<\/script>, where <\/p>\n<div id=\"a0000000014\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\tilde{\\rm H}(y) = \\int _{0}^y 1\/\\lceil z \\rceil \\, dz <\/script><\/div>\n<p> is the piecewise-linear extension of the function <script type=\"math\/tex;\">{\\rm H}(n)<\/script> to the positive reals. <\/p>\n<\/li>\n<li value=\"2\">\n<p>Each remaining sample costs <script type=\"math\/tex;\">c\\cdot x\/|x|<\/script> in expectation. <\/p>\n<\/li>\n<\/ol>\n<p> Hence, by Wald\u2019s equation, the total expected remaining cost is at most the product <script type=\"math\/tex;\">[|x| \\tilde{\\rm H}(n_t) ] c\\cdot x\/|x| = \\tilde{\\rm H}(n_t)c\\cdot x<\/script>. That is, given <script type=\"math\/tex;\">\\tilde x<\/script>, the conditional expectation of <script type=\"math\/tex;\">Q<\/script> is at most <\/p>\n<div id=\"a0000000015\" 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>The algorithm will keep this pessimistic estimator <script type=\"math\/tex;\">\\phi _t<\/script> from increasing in each iteration. When a set <script type=\"math\/tex;\">s<\/script> is chosen in iteration <script type=\"math\/tex;\">t+1<\/script>, the increase <script type=\"math\/tex;\">\\phi _{t+1} - \\phi _t<\/script> equals <\/p>\n<div id=\"a0000000016\" class=\"equation\"><script type=\"math\/tex; mode=display\">  c_{s} ~ -~  [\\tilde{\\rm H}(n_{t}) - \\tilde{\\rm H}(n_{t+1})] c\\cdot x.  <\/script><\/div>\n<p> Recalling the key inequality <script type=\"math\/tex;\">\\tilde{\\rm H}(n_{t}) - \\tilde{\\rm H}(n_{t+1}) \\ge (n_t - n_{t+1})\/\\lceil n_t\\rceil <\/script> from <a href=\"http:\/\/algnotes.info\/on\/walds-dependent\">Wald\u2019s for dependent decrements<\/a>, this increase is at most <\/p>\n<div id=\"desired\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{desired} c_{s} \\, -\\,  \\frac{n_{t} - n_{t+1}}{\\lceil n_t\\rceil }\\, c\\cdot x. \\end{equation}<\/script><\/div>\n<p> For a set <script type=\"math\/tex;\">s<\/script> chosen randomly from <script type=\"math\/tex;\">x\/|x|<\/script>, the bound\u00a0\\eqref{desired} is non-positive in expectation, because <script type=\"math\/tex;\">\\textrm{E}[c_{s}] = c\\cdot x\/|x|<\/script> while <script type=\"math\/tex;\">\\textrm{E}[n_t - n_{t+1}] \\ge \\lceil n_t\\rceil \/|x|<\/script>. <\/p>\n<p>Therefore, there exists a set <script type=\"math\/tex;\">s<\/script> for which the bound is non-positive. Gathering terms that depend on <script type=\"math\/tex;\">s<\/script> (namely <script type=\"math\/tex;\">c_{s}<\/script> and <script type=\"math\/tex;\">n_t-n_{t+1}<\/script>), the bound is non-positive iff <\/p>\n<div id=\"a0000000017\" class=\"equation\"><script type=\"math\/tex; mode=display\">  (n_t - n_{t+1})\/c_{s} \\, \\ge \\,  \\lceil n_t\\rceil \\,  c\\cdot x. <\/script><\/div>\n<p> Since some set <script type=\"math\/tex;\">s<\/script> satisfies this, the set <script type=\"math\/tex;\">s<\/script> that maximizes the left-hand side satisfies it. This is the set that the greedy algorithm chooses. Thus, the greedy algorithm is guaranteed to reach a successful outcome. <\/p>\n<\/div>\n<\/details>\n<\/div>\n<p>This performance guarantee follows as a corollary: <\/p>\n<div id=\"a0000000018\" 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<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000019\">Localizing gives <script type=\"math\/tex;\">{\\rm H}(\\max _s|s|)<\/script>-approximation<\/h1>\n<p> We note without recording the proof that <a href=\"http:\/\/algnotes.info\/on\/localizing\">localizing<\/a> the above rounding scheme improves the approximation ratio of the rounding scheme and algorithm to <script type=\"math\/tex;\">{\\rm H}(\\max _s |s|)<\/script>. The localized greedy algorithm is not the one directly above. It is the same as the algorithm from the reduction (it chooses the set <script type=\"math\/tex;\">s<\/script> in each iteration to maximize the number of not-yet-satisfied elements in <script type=\"math\/tex;\">s<\/script> divided by <script type=\"math\/tex;\">c_s<\/script>.) <\/p>\n<p>This approach generalizes to unconstrained Multiset Multicover (where each set <script type=\"math\/tex;\">s<\/script> covers element <script type=\"math\/tex;\">e<\/script> with a given integer multiplicity <script type=\"math\/tex;\">A_{se}<\/script>). The localized analysis gives approximation ratio <script type=\"math\/tex;\">{\\rm H}(\\max _{s} \\sum _e A_{se})<\/script>. The same result can be obtained by applying <a href=\"http:\/\/algnotes.info\/on\/set-cover-Wolsey\">Wolsey\u2019s generalization of the Set-Cover algorithm<\/a>\u00a0<span class=\"cite\">[<a href=\"#Nemhauser88Integer\">1<\/a>, <a href=\"#wolsey1982analysis\">3<\/a>]<\/span>, using the following submodular constraint for <script type=\"math\/tex;\">x\\in {\\mathbb N}_+^m<\/script>: that <script type=\"math\/tex;\">\\sum _{e} \\min \\{ d_e, \\sum _{s} A_{es} x_s\\}  \\ge \\sum _e d_e<\/script>. That approach proves approximation ratio <script type=\"math\/tex;\">{\\rm H}(\\max _s \\sum _e A_{se})<\/script> for the localized greedy algorithm (without the <script type=\"math\/tex;\">1\/d_e<\/script> in the element weight). <\/p>\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=\"a0000000020\">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). Aim for <script type=\"math\/tex;\">{\\rm H}(\\max _s |s|)<\/script>-approximation (matching Wolsey). <\/p>\n<\/div>\n<div class=\"latex-section\">\n<h1 id=\"a0000000021\">Related<\/h1>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/smu-reduction\">Rounding scheme and algorithm via reduction to Set Cover<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/smu-fast\">Reducing the iteration count using non-uniform increments<\/a> <\/p>\n<\/li>\n<li>\n<p>\u00a0<span class=\"cite\">[<a href=\"#Vazirani03Approximation\">2<\/a>, Exercise 13.4.1]<\/span> <\/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><\/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=\"Nemhauser88Integer\">1<\/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=\"Vazirani03Approximation\">2<\/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<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","protected":false},"excerpt":{"rendered":"<p>-approximation for unconstrained Set Multicover by oblivious randomized rounding. 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.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8571,"menu_order":5,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8573","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8573","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=8573"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8573\/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=8573"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}