Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 270 Combinatorial Algorithms & Data Structures — Spring 2023
Problem Set 6
Due: 11:59pm, Friday, March 24th
Solution maximum page limit: 4 pages
See homework policy at https://cs270.org/spring23/syllabus/#homework-policies
Problem 1: In weighted vertex cover we have an undirected graph with n vertices and m edges. Each vertex v has a cost cv > 0. We must choose a subset S of the vertices such that
• Each one of the m edges is incident to at least one vertex in S.
• P v∈S cv is minimized amongst all subsets S of vertices satisfying the previous bullet.
(a) (3 points) Modify the primal LP formulation from Lecture 18 to handle costs, and write the new dual. (This should be a minor modification of what was done in class.)
(b) (7 points) Give a greedy algorithm for weighted vertex cover achieving a 2-approximation. Hint: Maintain a feasible dual solution and build up a feasible primal solution (i.e. as long as an edge is not satisfied, cover it using one or both of its endpoints). The primal solution you maintain should be fractional, and only take a vertex into S once its variable becomes big enough.
Problem 2: In this and the next problem, we will work toward a PTAS for a scheduling problem. There are n jobs that we would like to schedule on m machines. Job i requires processing time pi , and each job must be assigned to exactly one machine. The completion time of a machine is then the sum of processing times of jobs assigned to it, and the “load” of an assignment is the maximum completion time of any machine in that assignment. We want to minimize load.
(a) (2 points) Let pmax be the maximum processing time of any job. Show that the quantity max{pmax,(1/m) Pn i=1 pi} is a lower bound on OPT.
(b) (3 points) Consider a greedy algorithm which loops over the jobs from 1 to n, and for job i assigns it to the currently least loaded machine (the one whose completion time when considering jobs assigned so far is smallest). Show that the greedy algorithm achieves completion time at most (2 − 1/m)OPT. Hint: Use (a).
Problem 3: Now suppose we want a PTAS for the scheduling problem from Problem 2, i.e. to achieve load at most (1 + ε)OPT with an algorithm whose running is time polynomial in the input size (the exponent of this polynomial can be any function of 1/ε). Define the “big” jobs to be B = {i ∈ [n] : pi ≥ εOPT} and the “small” jobs to be S = {i ∈ [n] : pi < εOPT}.
(a) (2 points) Show that if the jobs in B are assigned to machines to achieve load L, then greedily assigning the remaining jobs in S achieves load at most max{L,(1 + ε)OPT}.
(b) (4 points) Show that if there are at most k distinct job processing times across all jobs, then for any T there is a dynamic programming algorithm which finds a schedule achieving load at most T in time O(n 2k ) (or reports if no such schedule exists).
(c) (5 points) Conclude that, if we know OPT, we can schedule all jobs with load at most (1 + ε)OPT in time n O(log(1/ε)/ε) . Hint: For i ∈ B, round pi to ε(1 + ε) j for integer j.
(d) (4 points) In actuality we don’t know OPT. Show, nonetheless, that there is a PTAS for our scheduling problem.
Problem 4: (1 point) How much time did you spend on this problem set? If you can remember the breakdown, please report this per problem. (sum of time spent solving problem and typing up your solution) 2