{"id":280,"date":"2013-09-10T08:32:14","date_gmt":"2013-09-10T08:32:14","guid":{"rendered":"http:\/\/www.cs.uleth.ca\/~benkoczi\/wordpress\/?p=280"},"modified":"2013-10-15T18:54:14","modified_gmt":"2013-10-15T18:54:14","slug":"assignment-1","status":"publish","type":"post","link":"https:\/\/www.cs.uleth.ca\/~benkoczi\/wordpress\/?p=280","title":{"rendered":"Assignment 1"},"content":{"rendered":"<p><strong>Due: Thursday Oct 3, 2013, 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 vertex cover problem discussed in class for Graph $K_3$. Write the linear programming (LP) relaxation for the problem and give the optimal fractional solution. Write the dual LP and prove that your answer is indeed optimal (find a feasible dual solution whose cost equals that of the primal). <\/p>\n<p><strong> Problem 2: (grad)<\/strong> Relax the LP from Problem 1 by removing the condition that variables $x_v$ associated with the vertices of $K_3$ must be non-negative. Explain how you obtain the dual of the LP in this case. Write this dual LP.<\/p>\n<p><strong>Problem 3:<\/strong> Solve Problem 1.4 b from the textbook. Briefly argue that your algorithm runs in time polynomial with the problem size.<\/p>\n<p><strong>Problem 4: (grad) <\/strong> Solve Problem 1.4 a in the textbook. Hint: read the textbook.<\/p>\n<p><strong>Problem 5:<\/strong> Describe the local search approximation algorithm for scheduling jobs on identical parallel machines completely, <strong> including any data structures <\/strong> that you are using. Try to describe an algorithm that is as fast as you can. Analyse the running time of your algorithm.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Due: Thursday Oct 3, 2013, 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 &hellip; <a href=\"https:\/\/www.cs.uleth.ca\/~benkoczi\/wordpress\/?p=280\">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-280","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\/280","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=280"}],"version-history":[{"count":17,"href":"https:\/\/www.cs.uleth.ca\/~benkoczi\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/280\/revisions"}],"predecessor-version":[{"id":320,"href":"https:\/\/www.cs.uleth.ca\/~benkoczi\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/280\/revisions\/320"}],"wp:attachment":[{"href":"https:\/\/www.cs.uleth.ca\/~benkoczi\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=280"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.cs.uleth.ca\/~benkoczi\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=280"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.cs.uleth.ca\/~benkoczi\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=280"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}