闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP 360 Winter 2022

Assignment 5

Questions

1. A k-star is the graph on k + 1 vertices u, v1 , v2 , . . . , vk with edges uvi for each i ∈ [k]. A graph [10] G = (V, E) is k-star free if it does not contain a k-star: so, if we look at any subset of k + 1 vertices U C V in G, the subgraph of G on the vertices in U is not a k-star.

(a) For each positive integer k ≥ 3, give an example of a graph Gk = (Vk, Ek) that is k-star free but has a vertex with degree greater than k.

(b) Consider the following weighted version of the Independent Set problem. The input is a graph G = (V, E) with a non-negative integer vertex weight w(u) ≥ 0 for each u ∈ V. The goal is to ﬁnd an independent set U C V in G such that w(U) := u∈U w(u) is maximized. For any k ≥ 3, give a polynomial-time k-approximation algorithm for the Weighted Inde- pendent Set problem on k-star free graphs. (Hint: Use the obvious greedy algorithm!)

2. Consider the Max SAT problem. As input, you receive a CNF formula F = C1 ^ C2 ^ . . . ^ Cm [10] on n variables. The goal is to ﬁnd a boolean assignment x ∈ {0, 1}n which satisﬁes as many clauses as possible.

Prove that the following is a 2-approximation algorithm for the Max SAT problem. Given F, output the all-1s assignment or the all-0s assignment, whichever satisﬁes more clauses.

3. Updated on April 1st. Consider the following variation of the Weighted Vertex Cover problem. [10] As input you receive a graph G = (V, E) with vertex weights w(u) ≥ 0 for all u ∈ V. The goal is to ﬁnd a subset of vertices U C V such that

w(u) + | {uv ∈ E : u, v /∈ U} |

u∈U

is minimized. In other words, the set U does not have to be a vertex cover: it can leave some edges uncovered, but must pay for each uncovered edge.

(a) Create an integer program that solves the above variant of the Weighted Vertex Cover problem exactly. Your integer program should have a variable xu ∈ {0, 1} for every vertex u ∈ U and a variable ye ∈ {0, 1} for every edge e ∈ E.

(b) Now, ﬁnd a polynomial-time 3-approximation algorithm for this problem by rounding a solution of the linear programming relaxation of your integer program from part (a).

4. Let k > 0 be any positive integer, and consider the following restricted version of the Set Cover [10] problem. As input you receive a positive integer n and sets S1, S2 , . . . , Sm C [n] such that for all i ∈ [n], i appears in at most k of the given sets. The goal is to choose I C [m] such that

i∈I Si = [n] and |I| is minimized.

Give a polynomial-time k-approximation algorithm for this restriction of the Set Cover problem.

5. Consider the following modiﬁcation of the Center Selection problem. As input, you receive a list [15] of points p1 , p2 , . . . , pn ∈ [0, 1]2 with rational coordinates1in the plane. Note that each point is contained within the unit square [0, 1]2 , and the distance between any two pairs of points is the

usual Euclidean distance

d((x1 , x2 ), (y1 , y2 )) = ′(x1 - y1 )2 - (x2 - y2 )2 .

The goal is to ﬁnd the minimum r ≥ 0 such that we can cover all the given points with 3 circles of radius r.

In this question we develop a PTAS for this problem. So, we give an algorithm which, for any

ε > 0, runs in time polynomial in n that outputs a solution with approximation factor (1 + ε).

(a) Suppose the optimal radius is r* , and let c1 , c2 , c3 be the centers of circles covering all points in the input, each with radius r* . Divide the unit square [0, 1]2 into a grid of square cells each of which has side-length r* ε/2. Argue that there exists a set of three points c1(′), c2(′), c3(′) on this grid such that circles of radius (1 + ε)r* centered at c1(′), c2(′), c3(′) cover all points in the input.

(b) We can get an approximation of r* even if we cannot compute it exactly. Use the Center Selection algorithm to get a 2-approximation to this problem.