CSC373, Winter/Spring 2020 Assignment 3 Due: Thursday, April 2, 2020 4:59PM on MarkUs Note: You will receive 20% of the points for any (sub)problem for which you write “I do not know how to answer this question.” You will receive 10% if you leave a question blank. If instead you submit irrelevant or erroneous answers you will receive 0 points. You will receive partial credit for the work that is clearly “on the right track.” You may choose to spend your time looking for solutions on the internet and may likely succeed in doing so but you probably won’t understand the concepts that way and will then not do well on the quizzes, midterm and final. So at the very least try to do the assignment initially without searching the internet. If you obtain a solution directly from the internet, you must cite the link and explain the solution in your own words to avoid plagarizing. Note: As we have to change the grading scheme, it is especially important that you work individually (or in your established teams for this assignment) and not take solutions from others. This is always important but if we are going to increase the weight of assignments, we clearly have to have confidence that your work is your work. There was an error in the way we were weighting question 3, so we are going to reweight all the questions to better reflect the time needed and importance of the questions. 1. (10 points) We want to consider the following decision problem called DENSESUBGRAPH: Given a graph G = (V,E) and two integers a, b, does there exist V ′ ⊆ V such that |V ′| = a and |(V ′ × V ′) ∩E| ≥ b. That is, the problem is to determine if there is a subset of vertices of size at least a such that the subgraph induced by V ′ has at least b edges. Prove that DENSESUBGRAPH is NP complete. 2. (10 pts) Suppose P = NP . Show how to solve the graph coloring problem in polynomial time. That is, given a graph G = (V,E), find a valid coloring χ(G) : V → {1, 2, . . . , k} for some k satisfying the property that (u, v) ∈ E implies χ(u) 6= χ(v) so as to minimize the fewest number k of “colors”. 1 of 3 CSC373, Winter/Spring 2020 Assignment 3 3. (25 points) The standard form for an integer program is Maximize cTx Subject to Ax ≤ b x ∈ Nn Using the matrix notation, you can define the dual of an IP in standard form in the same way as for an LP in standard form. • (5 points) Show that the statement of weak duality holds for an IP. • Consider the following primal problem expressed as an IP and also as an LP . maiximize y subject to y − 3 2 x ≤ 0 y + 3 2 x ≤ 3 y, x ∈ N for the IP and y, x ≥ 0 for the LP (a) (5 points) Draw the feasible region and determine the optimum integral solution and the optimum fractional solution. (b) (5 points) Provide the dual of this primal and verify that the optimum fractional value for the dual matches the optimum fractional value for the primal. (c) (5 points) Determine an integral value for the dual that is greater than the integral optimum for the primal thereby showing that strong duality does not generally hold for IP. 4. (20 points) Consider the weighted set cover problem as defined in the KT text chapter on approximation algorithms. Namely, the input is a collection of C = {S1, S2, . . . , Sn} where Si ⊂ U , ∑ i Si = U and wi is the weight of set Si. The objective is to select a subcollection C ′ covering the elements in U so as to minimize ∑Si∈C′ wi. Now suppose that we restrict attention to those inputs (which we will call frequency f instances) where each universe element occurs in at most f sets. (a) (10 points) Show that the vertex cover problem can be viewed as a a set cover problem where every input is a frequency 2 instance. (b) (10 points) Show how to represent the set cover problem as an integer programming problem. Then show how to use linear programming and rounding to derive a factor f approximation algorithm for every frequency f instance of the set cover problem. 5. (20 points) Consider the knapsack problem with inputs {(s1, v1), . . . , (sn, vn)};W}. We know that there is an algorithm (using dynamic programming and rounding) that uses time O(n3/) time and computes a solution within a factor (1 + ) of the optimal solution for the (general) knapsack problem. Now consider the simple knapsack problem where vi = si for all i. We want a faster approximation algorithm for this problem. 2 of 3 CSC373, Winter/Spring 2020 Assignment 3 (a) (10 points) Describe a O(n log n) greedy time algorithm Greedy for the simple knapsack problem that always produce a solution within a factor of 2 of the optimal solution; that is, Greedy(I) ≥ (1/2)OPT (I) for every input I = (s1, s2, . . . , sn;W ). Here we assume si ≤ W for all i. Give a brief argument as to why your solution obtains the stated approximation guar- antee. (b) (10 points) Describe anO(n log n) time algorithmALG such thatALG(I) ≥ (2/3)OPT (I) for every input I. Hint: Partition the inputs into three sets, those with weight wi ≤ W/3, those with weight W/3 < wi ≤ (2/3)W and those with weight wi > (2/3)W . Your algorithm should be “greedy-like” in the sense that in each iteration it will consider a couple of items and then decide what items to place in the knapsack. Give a brief argument as to why your solution obtains the stated approximation guar- antee. 6. (20 points) Comsider the following weighted set packing problem. The input is collection C = {S1, S2, . . . , Sm} of sets where |Si| ≤ k for some fixed integer k and wi is the weight of Si. The objective is to select a subcollection C ′ of disjoint sets so as to maximize ∑ Si∈C′ wi. Design a greedy algorithm Greedy that achieves a k approximation ratio. That is, for every input C, Greedy(C) ≥ 1 k OPT (C). Use a charging argument to show that your algorithm obtains the stated approximation. 3 of 3
