Tutorial 8, Design and Analysis of Algorithms, 2025
1. Study Kwek-Mehlhorn's polynomial-time algorithm for optimal search for ratio-
nals. Show how you will search 22
7 using this algorithm.
2. Assuming that is an NP Optimization problem having the objective function
rational valued, and given a polynomial-time algorithm DCN (I; B ) for solving
the decision version of , prove that you can use DCN (I; B ) to construct a
polynomial-time algorithm OP T (I ) for nding the optimal solution of I 2 D.
3. Consider the following greedy algorithm for the knapsack problem. We initially
sort all the items in order of non-increasing ratio of value to size so that v1=s1
v2 =s2 : : : vn =sn . Let i be the index of an item of maximum value so that
vi = maxi2[1::n] vi . The greedy algorithm puts items in the knapsack in index
order until the next item no longer ts; that is, it nds k such that ki=1si B
but ki=1 +1 s > B . The algorithm returns either f 1; 2; : : : ; k g or f i g, whichever
i
has greater value. Prove that this algorithm is a 2 approximation algorithm for
the knapsack problem. You are required to give complete proof without making
any assumptions. You can assume that si B for each i 2 [1 : : : n]. Here B is
the knapsack capacity, vi is the pro t of item i, and si is the size of item i for
i 2 [1 : : : n].
4. Suppose you are given a set of positive integers A = f a1; a2; : : : ; an g and a positive
integer B . A subset S A is called feasible if the sum of the numbers in S does
not exceed B : X
ai B:
ai 2 S
The sum of the numbers in S will be called the total sum of S . You would like
to select a feasible subset S of A whose total sum is as large as possible. For
example, if A = f 8; 2; 4 g and B = 11, then the optimal solution is the subset
S = f 8; 2 g. Give a polynomial-time approximation algorithm for this problem
with the following guarantee: it returns a feasible set S A whose total sum is
at least half as large as the maximum total sum of any feasible set S A. Your
algorithm should have a running time of at most O(n log n).
5. Suppose you are given an n n grid graph G, as in Figure 1.
Associated with each node v is a weight w(v), which is a non-negative 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 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
The ‘‘heaviest-first’’ greedy algorithm:
Start with S equal to the empty set
While some node remains in G
Pick a node vi of maximum weight
Add vi to S
Delete vi and its neighbors from G
Endwhile
Return S
(a) Let S be the independent set returned by the \heaviest- rst" greedy algo-
rithm, and let T be any other independent set in G. Show that, for each
node v 2 T , either v 2 S , or there is a node v0 2 S so that w(v) w(v0) and
(v; v0) is an edge of G.
(b) Show that the \heaviest- rst" greedy algorithm returns an independent set of
total weight at least 14 times the maximum total weight of any independent
set in the grid graph G.
Figure 1: An example of a 5 5 grid graph.
6. We formulate the Load Balancing Problem as follows. We are given a set of m
machines M1; : : : ; Mm and a set of n jobs; each job j has a processing time tj . We
seek to assign each job to one of the machines so that the loads placed on all ma-
chines are as \balanced" as possible. More concretely, in any assignment of jobs
to machines, we can let A(i) denote the set of jobs assigned to machine P Mi ; under
this assignment, machine Mi needs to work for a total time of Ti = j 2A(i) tj ,
and we declare this to be the load on machine Mi. We seek to minimize a quan-
tity known as the makespan; it is simply the maximum load on any machine,
T = maxi Ti . Prove that the following algorithm is a 2 approximation algorithm
for the Load Balancing Problem :
Greedy-Balance:
Start with no jobs assigned
Set Ti = 0 and A(i) = for all machines Mi
For j = 1; : : : ; n
Let Mi be a machine that achieves the minimum mink Tk
2
Assign job j to machine Mi
Set A(i) A(i) [f j g
Set Ti Ti + tj
EndFor
7. Consider the cycle graph Cn in which each vertex has weight 21 . Show the
working of the dual-approximation algorithm for the minimum weight vertex
cover problem on this instance.
8. Consider the following instance of the Weighted Vertex Cover Problem with ver-
tices f v1; v2; v3; v4; v5; v6 g, having weight of vertices de ned as w(v1) = 2; w(v2) =
8; w(v3) = 5; w(v4) = 1; w(v5) = 4; w(v6) = 3, for an undirected graph having the
following adjacency matrix (edge between vi and vj is lebelled as eij ):
2 3
660 0 0 1 1 17
660 0 0 1 1 1777
6600 0 1 1 177
661
1 1 0 0 0777
66
41
1 1 0 0 075
1 1 1 0 0 0
(a) Formulate the above problem as a Set Cover Problem.
(b) Using the Primal-Dual Approximation Algorithm for the Set Cover Prob-
lem, solve the above instance of the Set Cover Problem.
(c) Now, from the above solution, get back your original solution of the Weighted
Vertex Cover Problem.
9. Design an ecient Fully Polynomial Time Approximation Scheme (FPTAS)
(A)2(0;1) for!the 0 1 Knapsack problem such that the algorithm A(I ) runs in
time O jIj and
2
A (I )
OP T (I )
1 :
10. Prove or disprove:
P = NP =) FPTAS = PTAS = APX = NPO:
