St. Francis Xavier UniversityDepartment of Computer ScienceCSCI 550: Approximation AlgorithmsAssignment 1Due October 7, 2021 at 11:59pm (Atlantic time)Assignment Regulations.• This assignment must be...

St. Francis Xavier UniversityDepartment of Computer ScienceCSCI 550: Approximation AlgorithmsAssignment 1Due October 7, 2021 at 11:59pm (Atlantic time)Assignment Regulations.• This assignment must be completed individually. It is acceptable to discuss the assignment questionswith other students, but you must write your answers individually and without assistance.• Please include your full name and email address on your submission.• You may either handwrite or typeset your submission. If your submission is handwritten, please ensurethat the handwriting is neat and legible, and that the scanned paper is clear.[10 marks] 1. Recall the weighted set cover problem from the lecture notes. Consider the partial weighted set coverproblem:Partial-Weighted-Set-CoverGiven: a ground set of elements E = fe1; : : : ; eng, subsets S1; : : : ; Sm  E, and a nonnegative weightwj  0 for each subset SjDetermine: the set I  f1; : : : ;mg that minimizesPi2I wi such that, for some constant 0 [i2ISi  pjEjGive a polynomial-time algorithm to nd a solution to the partial weighted set cover problem whosevalue is no greater than c(p)  OPT, where c(p) is some constant depending on p and OPT is the valueof the optimal solution to the weighted set cover problem (not the partial weighted set cover problem).Hint. Adapt one of the algorithms we have for the weighted set cover problem, but modify the stoppingcondition appropriately. You may nd the analysis in Section 1.6 of the course textbook to be useful.[10 marks] 2. Given a graph G = (V;E), we say that G contains an independent set if there exists a subset S  V ofvertices in the graph where, for any two vertices u; v 2 S, the edge fu; vg is not included in the edge set.Given G as well as an integer k, we can de ne the independent set problem as follows:Independent-SetGiven: an undirected graph G = (V;E) and an integer kDetermine: whether G contains an independent set S  V where jSj  kGive a polynomial-time reduction from Independent-Set to Vertex-Cover.Hint. Consider the relationship between an independent set and a vertex cover. If a graph G has one,then what can we conclude about G having the other?CSCI 550: Approximation AlgorithmsAssignment 1 Page 2[10 marks] 3. A Steiner tree is a tree that spans certain vertices in a graph G = (V;E). In the node-weighted Steinertree problem, we assume that each vertex in G has an associated weight and each edge in G has anassociated cost, and we nd a Steiner tree of least weight for G. The weight of a Steiner tree is the sumof the weights of each vertex and the costs of each edge in the tree.Formally, we de ne the problem as follows:Node-Weighted-Steiner-TreeGiven: an undirected graph G = (V;E), a weight wv  0 for each v 2 V , a cost ce  0 for each e 2 E,and a set of terminal vertices T  VDetermine: a minimum-weight tree in G that spans all terminal vertices in TShow that there exists no c ln(jTj)-approximation algorithm for Node-Weighted-Steiner-Tree withc Hint. Use a reduction from another problem we discussed in the lecture notes.[10 marks] 4. Consider the problem of scheduling on identical machines where each job to be scheduled is now subjectto a precedence constraint. We say that i  j if, in any feasible schedule, job i must be processedcompletely before job j can begin to be processed.We also say that a job j is available if all jobs i such that i  j have been processed completely. The listscheduling algorithm used by the machine is one in which, whenever a machine goes idle, any remainingjob that is available is assigned to that machine to start processing.Prove that this list scheduling algorithm is a 2-approximation algorithm for the identical-machinescheduling problem with predecence constraints.Hint. Observe that Equation (2.4) in the course textbook gives us one lower bound for this variant of theidentical-machine scheduling problem. If we have a set of jobs, all of which have precedence constraints,how might that give us another lower bound?
Sep 16, 2021
SOLUTION.PDF

Get Answer To This Question

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here