{"id":8643,"date":"2014-12-07T12:05:18","date_gmt":"2014-12-07T20:05:18","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=8643"},"modified":"2026-09-30T09:14:50","modified_gmt":"2026-09-30T17:14:50","slug":"obliv","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/obliv\/","title":{"rendered":"Oblivious randomized rounding"},"content":{"rendered":"<div class=\"latex-file\">\n<div class=\"latex-document\">\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<p><span style=\"float:right;margin:0.8em;margin-right:-0.5in;\"> <img decoding=\"async\" src=\"http:\/\/algnotes.info\/b\/wp-content\/uploads\/2014\/12\/img-00017.png\" alt=\"\\includegraphics[type=pdf,ext=.pdf,read=.pdf,width=2.5in]{shared\/graphics\/random_walk}\" style=\"width:2.5in\" class=\"zoooom\" \/> <\/span> <\/p>\n<blockquote class=\"quote\"><p><center><em>Oblivious randomized rounding via sample-and-increment rounding schemes.<\/em><\/center><\/p><\/blockquote>\n<p> Randomized rounding schemes based on random sampling can give better approximate solutions than do standard randomized-rounding schemes. Derandomizing them (via the method of conditional probabilities) yields greedy and Lagrangian-relaxation algorithms in a systematic way. We illustrate this by example.<!--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\/randomized-rounding\">randomized rounding<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/method-of-conditional-probabilities\">the method of conditional probabilities<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/pessimistic-estimators\">pessimistic estimators<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/greedy-example\">An example of a greedy approximation algorithm<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/lagrangian-relaxation-example\">An example of a Lagrangian-relaxation algorithm<\/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\">Sample-and-increment randomized-rounding schemes<\/h1>\n<p>A typical sample-and-increment randomized-rounding scheme has the form below: <\/p>\n<table id=\"a0000000004\" class=\"latex-scheme\" 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> Problem instance <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> Approximate solution for <script type=\"math\/tex;\">{\\cal I}<\/script> (w\/ positive probability)<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">1.<\/td>\n<td style=\"padding-left:0em\"> <a href=\"http:\/\/algnotes.info\/on\/modeling\">Solve an LP<\/a> to get fractional solution <script type=\"math\/tex;\">x^*<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">2.<\/td>\n<td style=\"padding-left:0em\"> Initialize each <script type=\"math\/tex;\">\\tilde x_j = 0<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:0em\"> For <script type=\"math\/tex;\">t=1,2,\\ldots <\/script> until some condition is met:  <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">4.<\/td>\n<td style=\"padding-left:1em\"> Increment <script type=\"math\/tex;\">\\tilde x_j<\/script>, where <script type=\"math\/tex;\">j<\/script> is randomly sampled from distribution <script type=\"math\/tex;\">x^*\/|x^*|<\/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<p> (Above <script type=\"math\/tex;\">|x^*| = \\sum _j x^*_j<\/script> is the 1-norm of <script type=\"math\/tex;\">x^*<\/script>.) <\/p>\n<p>We are interested in two properties of sample-and-increment schemes: <\/p>\n<ol class=\"enumerate\">\n<li value=\"1\">\n<p><em>They can give a better quality of approximation than conventional rounding schemes.<\/em> <\/p>\n<p>For example, for weighted set cover, a sample-and-increment scheme yields expected cost <script type=\"math\/tex;\">{\\rm H}(d)<\/script> times the cost of the fractional cover, where <script type=\"math\/tex;\">d<\/script> is the largest set size (matching Chv\u00e1tal\u2019s greedy algorithm). <\/p>\n<\/li>\n<li value=\"2\">\n<p><em>Derandomizing them using the standard method of conditional probabilities yields greedy and Lagrangian-relaxation algorithms.<\/em> <\/p>\n<\/li>\n<\/ol>\n<p>Regarding the second point, to derive an algorithm, one first analyzes the rounding scheme to show a desired performance guarantee. A typical guarantee might have the following form: <\/p>\n<div id=\"a0000000005\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b \"=\"&quot;\">Lemma.<\/b>   <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>For any instance <script type=\"math\/tex;\">{\\cal I}<\/script>, with positive probability, the rounding scheme returns a <a href=\"http:\/\/en.wikipedia.org\/wiki\/Approximation_algorithm\"><script type=\"math\/tex;\">c<\/script>-approximate solution<\/a> <script type=\"math\/tex;\">\\tilde x\\ldots <\/script> <\/p>\n<\/div><\/div>\n<p> The proof will use standard <a href=\"http:\/\/algnotes.info\/on\/probabilistic-method\">probabilistic methods<\/a> (<a href=\"http:\/\/algnotes.info\/on\/basic-bounds\">linearity of expectation, naive union bounds,<\/a> <a href=\"http:\/\/algnotes.info\/on\/chernoff\">Chernoff bounds<\/a>, etc.) <\/p>\n<p>Next, one applies <a href=\"http:\/\/algnotes.info\/on\/method-of-conditional-probabilities\">the standard method of conditional probabilities<\/a> to the existence proof. The resulting deterministic algorithm is guaranteed to reach a successful outcome, that is, to match the performance guarantee of the rounding scheme (but with probability 1): <\/p>\n<div id=\"a0000000006\" class=\"my-theorem latex-paragraph latex-thm\">\n<div class=\"latex-paragraph-heading\">   <b>Theorem <\/b> (algorithm).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> For any instance <script type=\"math\/tex;\">{\\cal I}<\/script>, the algorithm returns a <a href=\"http:\/\/en.wikipedia.org\/wiki\/Approximation_algorithm\"><script type=\"math\/tex;\">c<\/script>-approximate solution<\/a> <script type=\"math\/tex;\">\\tilde x\\ldots <\/script>. <\/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=\"a0000000007\">Deriving a greedy or Lagrangian-relaxation algorithm<\/h1>\n<p>The goal in this setting is to obtain an algorithm of the following form: <\/p>\n<table id=\"a0000000008\" 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> Problem instance <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> Approximate solution (guaranteed)<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">1.<\/td>\n<td style=\"padding-left:0em\"> <s style=\"opacity:0.6\"><a href=\"http:\/\/algnotes.info\/on\/modeling\">Solve an LP<\/a> to get fractional solution <script type=\"math\/tex;\">x<\/script>.<\/s> <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">2.<\/td>\n<td style=\"padding-left:0em\"> Initialize each <script type=\"math\/tex;\">\\tilde x_j = 0<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:0em\"> For <script type=\"math\/tex;\">t=1,2,\\ldots <\/script> until some condition is met:  <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">4.<\/td>\n<td style=\"padding-left:1em\"> Increment <script type=\"math\/tex;\">\\tilde x_j<\/script>, where <script type=\"math\/tex;\">j<\/script> is <em>chosen so that <script type=\"math\/tex;\">\\phi (\\tilde x)<\/script> does not increase<\/em>.  <\/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 form is atypical, in that it skips the first step, solving the linear program. The trick is to find a pessimistic estimator <script type=\"math\/tex;\">\\phi <\/script> such that the choice of <script type=\"math\/tex;\">j<\/script> in line 4 can be made <em>without knowing<\/em> the fractional solution <script type=\"math\/tex;\">x^*<\/script>. Starting with a rounding scheme based on random sampling makes this possible. I call this kind of randomized rounding <em>oblivious<\/em> randomized rounding. <\/p>\n<p>Many existing greedy\/Lagrangian-relaxation algorithms can be derived this way. Prime examples are the greedy set-cover algorithm by Johnson\u00a0<span class=\"cite\">[<a href=\"#Johnson74Approximation\">4<\/a>]<\/span>, Lov\u00e1sz\u00a0<span class=\"cite\">[<a href=\"#Lovasz75Ratio\">5<\/a>]<\/span>, and Chv\u00e1tal\u00a0<span class=\"cite\">[<a href=\"#Chvatal79Greedy\">2<\/a>]<\/span>, and the Lagrangian-relaxation algorithms of Plotkin, Shmoys, and Tardos\u00a0<span class=\"cite\">[<a href=\"#Plotkin95Fast\">6<\/a>]<\/span> (comparable to algorithms by Grigoriadis and Khachiyan\u00a0<span class=\"cite\">[<a href=\"#Grigoriadis94Fast\">3<\/a>]<\/span>). The latter compute <script type=\"math\/tex;\">(1+\\varepsilon )<\/script>-approximate solutions to fractional packing\/covering LPs. <\/p>\n<p>From this viewpoint, each algorithm follows from an existence proof \u201cin a systematic way\u201d\u00a0<span class=\"cite\">[<a href=\"#Raghavan88Probabilistic\">7<\/a>]<\/span> by applying the method of conditional probabilities. Standard probabilistic methods yield, and abstract, the arguments necessary to prove the performance guarantees of the algorithms (approximate primal-dual pairs, invariants, smooth penalty functions, etc.) <\/p>\n<p>In short, the \u201cprobabilistic lens\u201d\u00a0<span class=\"cite\">[<a href=\"#Alon92Probabilistic\">1<\/a>]<\/span> helps to organize and standardize the technical ideas underlying the design and analyses of these algorithms. <\/p>\n<p>This collection of notes illustrates the ideas by example (<a href=\"http:\/\/algnotes.info\/on\/greedy\">notes on greedy<\/a>, <a href=\"http:\/\/algnotes.info\/on\/lagrangian\">notes on Lagrangian relaxation<\/a>). There are also notes on <a href=\"http:\/\/algnotes.info\/on\/stopping-times\">bounds related to random stopping times<\/a> and <a href=\"http:\/\/algnotes.info\/on\/background\">other background material<\/a>. <\/p>\n<p>\u2014 <a href=\"http:\/\/www.cs.ucr.edu\/~neal\">Neal Young<\/a> <\/p>\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-subsection\">\n<h2 id=\"a0000000009\">More\u2026<\/h2>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/greedy\">Example derivations of greedy algorithms<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/lagrangian\">Example derivations of Lagrangian-relaxation algorithms<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/stopping-times\">Background: probabilistic bounds related to random stopping times<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/background\">Other background material<\/a> <\/p>\n<\/li>\n<\/ul>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b>p.s. Blogging in LaTeX<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> I write these notes in LaTeX, then use <a href=\"http:\/\/plastex.sourceforge.net\/\">plasTeX<\/a> to translate them to HTML and <a href=\"http:\/\/en.wikipedia.org\/wiki\/MathJax\">MathJax<\/a>. More on that <a href=\"http:\/\/algnotes.info\/on\/plog\">here<\/a>. <\/p>\n<\/div><\/div>\n<\/div>\n<\/div>\n<\/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=\"Alon92Probabilistic\">1<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;N+Alon+&quot;+author:&quot;+J+H++Spencer&quot;+intitle:&quot;+The+Probabilistic+Method&quot;\">N.\u00a0Alon and J.\u00a0H. Spencer. <em>The Probabilistic Method<\/em>. John Wiley and Sons, New York, 1992. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Chvatal79Greedy\">2<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;V+Chvatal&quot;+intitle:&quot;+A+greedy+heuristic+for+the+set-covering+problem&quot;\">V.\u00a0Chv\u00e1tal. A greedy heuristic for the set-covering problem. <em>Math. Operations Research<\/em>, 4(3):233\u2013235, 1979. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Grigoriadis94Fast\">3<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;M+D++Grigoriadis+&quot;+author:&quot;+L+G++Khachiyan&quot;+intitle:&quot;+Fast+approximation+schemes+for+convex+programs+with+many+blocks+and+coupling+constraints&quot;\">M.\u00a0D. Grigoriadis and L.\u00a0G. Khachiyan. Fast approximation schemes for convex programs with many blocks and coupling constraints. <em>SIAM J. Optimization<\/em>, 4(1):86\u2013107, Feb. 1994. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Johnson74Approximation\">4<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;D+S++Johnson&quot;+intitle:&quot;+Approximation+algorithms+for+combinatorial+problems&quot;\">D.\u00a0S. Johnson. Approximation algorithms for combinatorial problems. <em>J. Computer System Sciences<\/em>, 9:256\u2013278, 1974. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Lovasz75Ratio\">5<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;L+Lovasz&quot;+intitle:&quot;+On+the+ratio+of+optimal+integral+and+fractional+covers&quot;\">L.\u00a0Lov\u00e1sz. On the ratio of optimal integral and fractional covers. <em>Discrete Mathematics<\/em>, 13:383\u2013390, 1975. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Plotkin95Fast\">6<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;S+A++Plotkin&quot;+author:&quot;+D+B++Shmoys&quot;+author:&quot;+&quot;+author:&quot;+E+Tardos&quot;+intitle:&quot;+Fast+approximation+algorithms+for+fractional+packing+and+covering+problems&quot;\">S.\u00a0A. Plotkin, D.\u00a0B. Shmoys, and E.\u00a0Tardos. Fast approximation algorithms for fractional packing and covering problems. <em>Math. Operations Research<\/em>, 20(2):257\u2013301, 1995. Preliminary version in FOCS\u201991. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Raghavan88Probabilistic\">7<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;P+Raghavan&quot;+intitle:&quot;+Probabilistic+construction+of+deterministic+algorithms+approximating+packing+integer+programs&quot;\">P.\u00a0Raghavan. Probabilistic construction of deterministic algorithms approximating packing integer programs. <em>J. Computer System Sciences<\/em>, 37(2):130\u2013143, Oct. 1988. <\/a><\/td>\n<\/tr>\n<\/table><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Oblivious randomized rounding via sample-and-increment rounding schemes. Randomized rounding schemes based on random sampling can give better approximate solutions than do standard randomized-rounding schemes. Derandomizing them (via the method of conditional probabilities) yields greedy and Lagrangian-relaxation algorithms in a systematic way. We illustrate this by example.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":3,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8643","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8643","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=8643"}],"version-history":[{"count":3,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8643\/revisions"}],"predecessor-version":[{"id":9006,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8643\/revisions\/9006"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=8643"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}