RW746 Solution 8

RW746 Solution 8
1. (20 marks) Exercise 17.4 of the notes.
Given n integers
cn , find a partition of {1, 2, . . . , n} into two subsets S1 , S2 that minimizes the
P c1 , . . . , P
quantity max( j∈S1 cj , j∈S2 cj ).
Consider the following heuristic for some fixed integer k:
1. Choose the k largest cj ’s.
2. Find the optimal partition of these k integers (by some exhaustive method).
3. Complete this into a partition of {1, 2, . . . , n} by considering each of the remaining cj ’s
and adding it to the partition which at the time has the smallest sum.
(a) (10 marks) Prove that this O(2k + n) algorithm is
2+k -approximate.
(b) (10 marks) Based on the previous question, devise an approximation scheme for this problem.
What is the complexity of your PTAS, in terms of n and 1/?
This problem was clearly too hard to do. I am not going to give the solution here and it will not
be marked as part of the tutorial. It also won’t be considered for the exam.
2. (20 marks)
Suppose we are given an n×n grid graph G, as in the figure.
Associated with each node v is a weight w(v), which is a
nonnegative integer. You may assume that the weights of
all nodes are distinct. Your goal is to choose an independent
set S of nodes of the grid, so that the sum of the weights
of the nodes in S is as large as possible. (The sum of the
weights of the nodes in S will be called its total weight.)
Consider the following greedy algorithm for this problem.
1. Start with S equal to the empty set.
2. While some node remains in G:
Pick a node vi of maximum weight
Add vi to S
Delete vi and its neighbours from G
3. Return S.
(a) (10 marks) Let S be the independent set returned by the algorithm above, and let T be any other
independent set in G. Show that, for each node v ∈ T , either v ∈ S, or there is a node v 0 ∈ S so
that w(v) ≤ w(v 0 ) and (v, v 0 ) is an edge of G.
Consider any v ∈ T . If v ∈ S, then we are done. So let’s assume that v 6∈ S.
(1) At least one of the up to four neighbours of v must be in S; otherwise, we could increase
the total weight of S by adding v to S.
(2) So, let’s suppose that the neighbours of v are {v1 , . . . , vk }. Either k = 2 (in case v is a
corner node), k = 3 (in case v is an edge node), or k = 4 (in case v is an interior node).
(3) Rewind the algorithm to the point just before any of the neighbours are selected by
the greedy algorithm. In the next step, the algorithm selects vi . Therefore w(v) ≤ w(vi )
(otherwise v would have been selected), and (v, vi ) (because vi is a neighbour of v).
(b) (10 marks) Show that the greedy algorithm returns an independent set of total weight at least
1/4 times the maximum total weight of any independent set in the grid graph G.
Consider any other independent set T (including the optimal set). For each node v ∈ T , we
charge it to a node in S as follows. If v ∈ S, then we charge v to itself. Otherwise, by (a), v
is a neighbour of some node v 0 ∈ S whose weight is at least as large. We charge v to v 0 .
Now, if v is charged to itself, then no other node is charged to v, since S and T are independent
sets. Otherwise, at most four neighbouring nodes of no greater weight are charged to v. Either
way, the total weight of all nodes charged to v is at most 4w(v). Since these charges account
for the total weight ogf T , it follows that the total weight of nodes in T is at most four times
the total weight of nodes in S.
Total: 20 marks