{"id":8640,"date":"2014-12-07T12:05:07","date_gmt":"2014-12-07T20:05:07","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=8640"},"modified":"2026-09-30T09:15:46","modified_gmt":"2026-09-30T17:15:46","slug":"greedy","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/obliv\/greedy\/","title":{"rendered":"Greedy examples"},"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>Deriving greedy algorithms via randomized rounding.<\/em><\/center><\/p><\/blockquote>\n<p>  Greedy algorithms are often natural, but coming up with exactly the right algorithm or analysis can still be a challenge. Here, the idea is to view these algorithms as derandomized versions of a sample-and-increment rounding scheme. The proof of the performance guarantee starts with the rounding scheme, using standard probabilistic tools. Applying the method of conditional probabilities then yields the algorithm in a systematic way.<!--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\/obliv\">Introduction<\/a> \u2014 About the basic idea of using randomized rounding to derive greedy and Lagrangian-relaxation algorithms. <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/modeling\">linear programming<\/a> \u2014 Notes on integer linear programming, including linear programs for Set Cover. <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/greedy-example\">example algorithm<\/a> \u2014 A review of the greedy Set-Cover algorithm. <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/randomized-rounding\">randomized rounding<\/a> \u2014 Notes on conventional randomized rounding. (See also <a href=\"http:\/\/algnotes.info\/on\/method-of-conditional-probabilities\">the method of conditional probabilities<\/a> and <a href=\"http:\/\/algnotes.info\/on\/pessimistic-estimators\">pessimistic estimators<\/a>.) <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/walds\">Wald\u2019s equation<\/a> \u2014 A review of Wald\u2019s equation, for analyzing random sampling schemes with random stopping times. <\/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\">Three introductory examples<\/h1>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b><a href=\"http:\/\/algnotes.info\/on\/set-cover-unweighted\">1. Unweighted Set Cover.<\/a><\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> This introductory example illustrates the basic idea. The rounding scheme randomly samples a fixed number <script type=\"math\/tex;\">N = \\lceil |x|\\ln n\\rceil <\/script> of sets from the distribution defined by the fractional solution <script type=\"math\/tex;\">x<\/script>. By direct calculation, the expected number of elements left uncovered is less than 1. Applying the method of conditional probabilities yields Johnson and Lov\u00e1sz\u2019s greedy set-cover algorithm, and a proof that it returns a cover of size at most <script type=\"math\/tex;\">\\lceil |x^*|\\ln n\\rceil <\/script>, where <script type=\"math\/tex;\">x^*<\/script> is an optimal fractional cover. <a href=\"http:\/\/algnotes.info\/on\/set-cover-unweighted\">More on deriving the greedy set-cover algorithm\u2026<\/a> <\/p>\n<\/div><\/div>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b><a href=\"http:\/\/algnotes.info\/on\/set-cover-weighted\">2. Weighted Set Cover.<\/a><\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> For problems whose cost functions have weights, the increase in cost with each sample depends on the sample. Also, instead of sampling for a pre-determined number of samples, the most natural rounding scheme stops when some condition is met (such as when all elements are covered). The analysis of the rounding scheme becomes a little more subtle. The analysis for the unweighted case can be adapted by using <a href=\"http:\/\/algnotes.info\/on\/walds\">Wald\u2019s equation<\/a>. <\/p>\n<p>In this example, the rounding scheme samples from the distribution defined by the fractional solution until all elements are covered. We use Wald\u2019s equation to show that the expected number of samples before all elements are covered is at most <script type=\"math\/tex;\">|x|{\\rm H}(n)<\/script>, so the expected cost of all the samples is at most <script type=\"math\/tex;\">c\\cdot x\\,  {\\rm H}(n)<\/script> (the fractional cost times <script type=\"math\/tex;\">{\\rm H}(n)=1+1\/2+\\cdots +1\/n<\/script>). Applying the method of conditional probabilities yields Chv\u00e1tal\u2019s algorithm (which generalizes the greedy set-cover algorithm to the weighted case), and a proof that it returns a <script type=\"math\/tex;\">{\\rm H}(n)<\/script>-approximation. <a href=\"http:\/\/algnotes.info\/on\/set-cover-weighted\">More on using Wald\u2019s to handle weighted set cover\u2026<\/a> <\/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<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b><a href=\"http:\/\/algnotes.info\/on\/set-cover-local\">3. Improving the ratio to <script type=\"math\/tex;\">{\\rm H}(d)<\/script> by \u201clocalizing.\u201d<\/a><\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Here <script type=\"math\/tex;\">d = \\max _s |s|<\/script> is the maximum set size. The analyses in the examples above analyze the number of samples necessary to meet all <script type=\"math\/tex;\">n<\/script> constraints, then multiply that by the cost per sample. With this \u201cglobal\u201d approach, the approximation ratio inevitably grows as <script type=\"math\/tex;\">n<\/script> increases, because the number of samples required to meet all constraints grows with <script type=\"math\/tex;\">n<\/script> (it\u2019s about <script type=\"math\/tex;\">|x|{\\rm H}(n)<\/script>). We can avoid this by recasting the analysis to make it \u201clocal\u201d. <\/p>\n<p>In this example, we modify the random sampling scheme so that, when a set <script type=\"math\/tex;\">s<\/script> is sampled, the set is added to the cover only if <script type=\"math\/tex;\">s<\/script> contains an element that is not yet covered. For the analysis we focus on each set <script type=\"math\/tex;\">s<\/script> in isolation. Following the same reasoning as in the global analysis, the expected number of samples before all elements in <script type=\"math\/tex;\">s<\/script> are covered is at most <script type=\"math\/tex;\">|x|{\\rm H}(|s|)<\/script>. (And <script type=\"math\/tex;\">s<\/script> won\u2019t be added to the cover after that.) Thus, the probability that <script type=\"math\/tex;\">s<\/script> is added is at most <script type=\"math\/tex;\">x_s{\\rm H}(|s|)<\/script>. By linearity of expectation the expected cost of the final cover is at most <script type=\"math\/tex;\">\\sum _s c_s x_s {\\rm H}(|s|)<\/script>. <\/p>\n<p>Applying the method of conditional probabilities yields Chv\u00e1tal\u2019s algorithm again (although the pessimistic estimator is more subtle) and a proof that the algorithm returns a cover of cost at most <script type=\"math\/tex;\">\\min _{x^*} \\sum _s c_s x^*_s {\\rm H}(|s|)<\/script>, which is at most <script type=\"math\/tex;\">{\\rm H}(d)\\min _{x^*} c\\cdot x^*<\/script>, where <script type=\"math\/tex;\">x^*<\/script> ranges over the feasible fractional set covers. <\/p>\n<p><a href=\"http:\/\/algnotes.info\/on\/set-cover-local\">More on improving the bound by localizing it\u2026<\/a> <\/p>\n<\/div><\/div>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000004\">Other related examples<\/h1>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/set-cover-alterations\">Yet another set-cover bound (<script type=\"math\/tex;\">\\ln (n\/{\\textsc{opt}})<\/script>-approximation, using \u201calterations\u201d)<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/set-cover-local\">Using a Markov bound instead of Wald\u2019s equation to bound weighted cost<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/set-cover-grasp\">A greedy randomized adaptive search procedure (GRASP) for Set Cover<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/maximum-matching\">Localizing to get 2-approximation for max-weight <script type=\"math\/tex;\">c<\/script>-matching<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/lagrangian\">Lagrangian-relaxation algorithm examples<\/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 class=\"latex-section\">\n<h1 id=\"a0000000005\">Notes not yet added<\/h1>\n<ul class=\"itemize\">\n<li>\n<p>more general covering problems, including k-medians and facility locations <\/p>\n<\/li>\n<li>\n<p>open problems (e.g.\u00a0greedy algorithm for integer covering with box constraints) <\/p>\n<\/li>\n<li>\n<p>Implicit dual solutions <\/p>\n<\/li>\n<\/ul>\n<\/div><\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Deriving greedy algorithms via randomized rounding. Greedy algorithms are often natural, but coming up with exactly the right algorithm or analysis can still be a challenge. Here, the idea is to view these algorithms as derandomized versions of a sample-and-increment rounding scheme. The proof of the performance guarantee starts with the rounding scheme, using standard [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8643,"menu_order":8,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8640","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8640","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=8640"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8640\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8643"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=8640"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}