{"id":310,"date":"2013-10-01T04:14:40","date_gmt":"2013-10-01T04:14:40","guid":{"rendered":"http:\/\/www.cs.uleth.ca\/~benkoczi\/wordpress\/?p=310"},"modified":"2014-10-13T03:22:33","modified_gmt":"2014-10-13T03:22:33","slug":"assignment-2-more-problems-will-be-added","status":"publish","type":"post","link":"https:\/\/www.cs.uleth.ca\/~benkoczi\/wordpress\/?p=310","title":{"rendered":"Assignment 2"},"content":{"rendered":"<p><strong>Due: TBD, in class<\/strong><\/p>\n<blockquote><p>Undergraduate students can work in teams of two students and can submit a single paper per team. Problems marked (grad) are optional for undergraduate students.<br \/>\nAny notation that is not explained is standard notation. Search google for the definition.\n<\/p><\/blockquote>\n<p><strong>Problem 1:<\/strong> Consider the k-suppliers problem defined in Exercise 2.1 in the textbook. In class, we argued that choosing an arbitrary vertex as center for the 1-center problem is a 2-approximation algorithm. Show that the same strategy has an unbounded approximation factor for the 1-supplier problem (show that $\\forall \\alpha > 0$, there exists an instance with $Z_{arb} > \\alpha Z_{OPT}$, where $Z_{arb}$ is the cost of an arbitrary center in the 1-supplier problem).<\/p>\n<p><strong> Problem 2 (grad):<\/strong> Consider the following strategy for the 1-supplier problem:<\/p>\n<ul>\n<li> Choose an arbitrary customer $i \\in D$.\n<li> Let $j \\in F$ be the closest facility from $i$.\n<li> Place the facility at $j$.\n<\/ul>\n<p>Show that this strategy is a 3-approximation for the 1-supplier problem (ignore the fact that the 1-supplier problem can be solved optimally in polynomial time by a brute force algorithm). Give a 3-approximation greedy algorithm for the $k$-suppliers problem. Prove its approximation factor.<\/p>\n<p><strong>Problem 3:<\/strong> Consider the following greedy algorithm for the knapsack problem, where $i \\in I$ represents an object with value $v_i$ and size $s_i$, and $B$ is the knapsack capacity. Let $v(S)$ and $s(S)$ be the total value and size respectively of items in $S$, $v(S) = \\sum_{i \\in S} v_i$, $s(S) = \\sum_{i \\in S} s_i$.<\/p>\n<ul>\n<li> Initialize the solution set  $S \\leftarrow \\emptyset$.<\/li>\n<li> while the total size of the solution $S$ does not exceed the knapsack capacity, $s(S) \\le B$ do:\n<ul>\n<li> Let $j$ be the object with largest value per unit size, $j = \\mathop{\\rm argmax}_{i \\in I-S} \\frac{v_i}{s_i}$.\n<li> Add $j$ to the solution, $S \\leftarrow S \\cup \\{j\\}$\n  <\/ul>\n<\/li>\n<li> Return $v(S)$ <\/li>\n<\/ul>\n<p>Give a simple example to show that this greedy algorithm has an arbitrarily small approximation factor.<\/p>\n<p><strong> Problem 4 (grad):<\/strong> Show that replacing the last step of the greedy algorithm from Problem 3 with<br \/>\n\\[<br \/>\n\\text{Return } \\max\\{v(S), \\max_{i \\in I} v_i\\},<br \/>\n\\]<br \/>\ngives a $\\frac{1}{2}$-approximation for the knapsack problem. Provide an example where the greedy algorithm returns a solution with cost equal to half of the optimal solution. Justify your answer even if you cite published work.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Due: TBD, in class Undergraduate students can work in teams of two students and can submit a single paper per team. Problems marked (grad) are optional for undergraduate students. Any notation that is not explained is standard notation. Search google &hellip; <a href=\"https:\/\/www.cs.uleth.ca\/~benkoczi\/wordpress\/?p=310\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[18],"tags":[],"class_list":["post-310","post","type-post","status-publish","format-standard","hentry","category-approx-oldass"],"_links":{"self":[{"href":"https:\/\/www.cs.uleth.ca\/~benkoczi\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/310","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.cs.uleth.ca\/~benkoczi\/wordpress\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.cs.uleth.ca\/~benkoczi\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.cs.uleth.ca\/~benkoczi\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.cs.uleth.ca\/~benkoczi\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=310"}],"version-history":[{"count":17,"href":"https:\/\/www.cs.uleth.ca\/~benkoczi\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/310\/revisions"}],"predecessor-version":[{"id":440,"href":"https:\/\/www.cs.uleth.ca\/~benkoczi\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/310\/revisions\/440"}],"wp:attachment":[{"href":"https:\/\/www.cs.uleth.ca\/~benkoczi\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=310"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.cs.uleth.ca\/~benkoczi\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=310"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.cs.uleth.ca\/~benkoczi\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=310"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}