{"id":820,"date":"2010-03-05T08:49:20","date_gmt":"2010-03-05T16:49:20","guid":{"rendered":"http:\/\/obliviousrounding.com\/blog\/?p=820"},"modified":"2026-09-30T09:14:43","modified_gmt":"2026-09-30T17:14:43","slug":"rounding","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/linear-programming\/rounding\/","title":{"rendered":"rounding an LP relaxation"},"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>A simple example of computing an approximate solution by rounding the solution to a linear-program relaxation.<\/em><\/center><\/p><\/blockquote>\n<p>The basic paradigm: <\/p>\n<ol class=\"enumerate\">\n<li value=\"1\">\n<p>Model your problem as an integer linear program. <\/p>\n<\/li>\n<li value=\"2\">\n<p>Solve its linear program relaxation. <\/p>\n<\/li>\n<li value=\"3\">\n<p>Somehow <em>round<\/em> the solution <script type=\"math\/tex;\">x^*<\/script> of the relaxed problem to get a solution <script type=\"math\/tex;\">\\tilde x<\/script> of the original problem. <\/p>\n<\/li>\n<\/ol>\n<p>The rounding step is typically most easily done with a so-called <em>randomized rounding<\/em> scheme. <\/p>\n<p>Rounding a relaxation is one of two standard ways to use linear-programming relaxations to design approximation algorithms. (The other way is the <em>primal-dual method<\/em>.)<!--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\/modeling\">Modeling problems as linear programs<\/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\">Trivial example: vertex cover<\/h1>\n<p> For a trivial example of rounding, consider minimum-cost Vertex Cover. Given a graph <script type=\"math\/tex;\">G=(V,E)<\/script> with vertex costs, the problem is to find a vertex cover (a subset of the vertices touching all edges) of minimum total cost. A standard integer program for the problem is <\/p>\n<div id=\"a0000000004\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\renewcommand{\\mathspread }{\\, \\, \\, }\\textstyle \\min \\Big\\{  \\sum _{v\\in V} c_v x_v ~ \\Big|~  x\\in {\\mathbb N}_+^{V};~  (\\forall (u,w)\\in E)~  x_u + x_w {\\, \\, \\, {\\ge }\\, \\, \\, }1\\Big\\} .  <\/script><\/div>\n<p>Let <script type=\"math\/tex;\">x^*<\/script> be an optimal fractional solution, that is, an optimal solution to the linear-program relaxation of this integer program. Let <span class=\"scshape\" style=\"font-variant:small-caps;text-transform:lowercase\">opt<\/span> be an optimal vertex cover, that is, an optimal solution to the integer program. <\/p>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b>The relaxation bounds <span class=\"scshape\" style=\"font-variant:small-caps;text-transform:lowercase\">opt<\/span>.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> How does the cost of <script type=\"math\/tex;\">x^*<\/script> relate to the cost of <span class=\"scshape\" style=\"font-variant:small-caps;text-transform:lowercase\">opt<\/span>? Note that <span class=\"scshape\" style=\"font-variant:small-caps;text-transform:lowercase\">opt<\/span> is one feasible solution to the linear-program relaxation. Since <script type=\"math\/tex;\">x^*<\/script> is the minimum-cost feasible solution, it follows that the cost of <span class=\"scshape\" style=\"font-variant:small-caps;text-transform:lowercase\">opt<\/span> is <em>at least<\/em> the cost of <script type=\"math\/tex;\">x^*<\/script>. <\/p>\n<p>How can this lower bound be used in an approximation algorithm? The following \u201crounding\u201d algorithm solves the relaxed problem, then rounds up every variable that is at least 1\/2: <\/p>\n<table id=\"a0000000005\" 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> Vertex-Cover problem 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> a vertex cover<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">1.<\/td>\n<td style=\"padding-left:0em\"> Compute the optimal solution <script type=\"math\/tex;\">x^*<\/script> to the linear-program relaxation. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">2.<\/td>\n<td style=\"padding-left:0em\"> For each <script type=\"math\/tex;\">v\\in V<\/script>, let <script type=\"math\/tex;\">\\tilde x_v = 1<\/script> if <script type=\"math\/tex;\">x^*_v \\ge 1\/2<\/script>, and <script type=\"math\/tex;\">\\tilde x_v = 0<\/script> otherwise. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:0em\"> Return <script type=\"math\/tex;\">\\tilde x<\/script>. <\/td>\n<\/tr>\n<\/table>\n<p>The algorithm indeed produces a feasible vertex cover <script type=\"math\/tex;\">\\tilde x<\/script>. (Because, for each edge <script type=\"math\/tex;\">(u,w)<\/script>, the fractional solution has <script type=\"math\/tex;\">x^*_u+x^*_w\\ge 1<\/script>, so one of <script type=\"math\/tex;\">x^*_u<\/script> or <script type=\"math\/tex;\">x^*_w<\/script> must be at least 1\/2, so one of <script type=\"math\/tex;\">\\tilde x_u<\/script> or <script type=\"math\/tex;\">\\tilde x_w<\/script> must be 1, so one of <script type=\"math\/tex;\">u<\/script> or <script type=\"math\/tex;\">v<\/script> must be in the cover.) <\/p>\n<p>The algorithm is a 2-approximation algorithm. The vertex cover <script type=\"math\/tex;\">\\tilde x<\/script> has cost <script type=\"math\/tex;\">\\sum _v c_v \\tilde x_v<\/script>. This is at most twice the cost <script type=\"math\/tex;\">\\sum _v c_v x^*_v<\/script> of <script type=\"math\/tex;\">x^*<\/script> (because each <script type=\"math\/tex;\">\\tilde x_v \\le 2 x^*_v<\/script>). Since the cost of <span class=\"scshape\" style=\"font-variant:small-caps;text-transform:lowercase\">opt<\/span> is at least the cost of <script type=\"math\/tex;\">x^*<\/script>, the vertex cover <script type=\"math\/tex;\">\\tilde x<\/script> has cost at most twice <span class=\"scshape\" style=\"font-variant:small-caps;text-transform:lowercase\">opt<\/span>. <\/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=\"a0000000006\">Randomized rounding<\/h1>\n<p> In general, the challenge in rounding is to convert the fractional solution <script type=\"math\/tex;\">x^*<\/script> into a feasible integer solution <script type=\"math\/tex;\">\\tilde x<\/script> without increasing the cost by too much. Naively rounding to the nearest integer (as in the example above) doesn\u2019t work well for most problems. Randomized rounding is generally more useful. <\/p>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000007\">Related<\/h2>\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\/obliv\">Randomized rounding without solving the linear program<\/a> <\/p>\n<\/li>\n<\/ul>\n<p>On wikipedia: <\/p>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Linear_programming_relaxation\">Linear programming relaxation<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Relaxation_(approximation)\">Relaxation (approximation)<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Vertex_cover\">Vertex cover<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Randomized_rounding\">Randomized rounding<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div><\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>A simple example of computing an approximate solution by rounding the solution to a linear-program relaxation. The basic paradigm: Model your problem as an integer linear program. Solve its linear program relaxation. Somehow round the solution of the relaxed problem to get a solution of the original problem. The rounding step is typically most easily [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1468,"menu_order":11,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-820","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/820","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=820"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/820\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/1468"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=820"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}