MODULE – V

LIMITATIONS OF ALGORITHMIC POWER: Decision Trees, P, NP, and NP-Complete

Problems. COPING WITH LIMITATIONS OF ALGORITHMIC POWER: Backtracking (n-
Queens problem, Subset-sum problem), Branch-and-Bound (Knapsack problem), Approximation
algorithms for NP-Hard problems (Knapsack problem).

LECTURE 39

Decision Tree Algorithms

Many important algorithms, especially those for sorting and searching, work by comparing items of
their inputs. We can study the performance of such algorithms with a device called a decision tree.
As an example, Figure presents a decision tree of an algorithm for finding a minimum of three
numbers. Each internal node of a binary decision tree represents a key comparison indicated in the
node, e.g., kk . (For the sake of simplicity, we assume throughout this section that all input items are
distinct.) Each leaf represents a possible outcome of the algorithm’s run on some input of size n.
Note that the number of leaves can be greater than the number of outcomes because, for some
algorithms, the same outcome can be arrived at through a different chain of comparisons. (This
happens to be the case for the decision tree in Figure - An important point is that the number of
leaves must be at least as large as the number of possible outcomes. The algorithm’s work on a
particular input of size n can be traced by a path from the root to a leaf in its decision tree, and the
number of comparisons made by the algorithm on such

a run is equal to the length of this path. Hence, the number of comparisons in the worst case is equal
to the height of the algorithm’s decision tree. The central idea behind this model lies in the
observation that a tree with a given number of leaves, which is dictated by the number of possible
Analysis & Design of Algorithms (BCS401) AIML-CEC Page 1
outcomes, has to be tall enough to have that many leaves. Specifically, it is not difficult to prove that
for any binary tree with l leaves and height h,

h ≥log2].

Indeed, a binary tree of height h with the largest number of leaves has all its leaves on the last level
(why?). Hence, the largest number of leaves in such a tree is 2h. In other words, 2h ≥ l, which
immediately implies. Inequality puts a lower bound on the heights of binary decision trees and hence
the worst-case number of comparisons made by any comparison-based algorithm for the problem in
question. Such a bound is called the information-theoretic lower bound. We illustrate this technique
below on two important problems: sorting and searching in a sorted array.

Decision Trees for Sorting

Most sorting algorithms are comparison based, i.e., they work by comparing elements in a list to be
sorted. By studying properties of decision trees for such algorithms, we can derive important lower
bounds on their time efficiencies. We can interpret an outcome of a sorting algorithm as finding a
permutation of the element indices of an input list that puts the list’s elements in ascending order.
Consider, as an example, a three-element list a, b, c of orderable items such as real numbers or
strings. For the outcome a < c<b obtained by sorting this list (see Figure 11.2), the permutation in
question is 1, 3, 2. In general, the number of possible outcomes for sorting an arbitrary n-element
list is equal to n!

Analysis & Design of Algorithms (BCS401) AIML-CEC Page 2

Inequality implies that the height of a binary decision tree for any comparison-based sorting
algorithm and hence the worst-case number of comparisons made by such an algorithm cannot be
less than [log2 n!]:

In other words, about n log2 n comparisons are necessary in the worst case to sort an arbitrary n-
element list by any comparison-based sorting algorithm. Note that merge sort makes about this
number of comparisons in its worst case and hence is asymptotically optimal. This also implies that
the asymptotic lower bound n log n is tight and therefore cannot be substantially improved. We
should point out, however, that the lower bound of nlogn can be improved for some values of n.

We can also use decision trees for analyzing the average-case efficiencies of comparison-based
sorting algorithms. We can compute the average number of comparisons for a particular algorithm
as the average depth of its decision tree’s leaves, i.e., as the average path length from the root to the
leaves. For example, for the three-element insertion sort whose decision tree is given in Figure 11.3,
this number is (2 + 3 + 3 + 2 + 3 + 3)/6 = 2(2/3) .

Under the standard assumption that all n! outcomes of sorting are equally likely, the following lower
bound on the average number of comparisons Cavg made by any comparison-based algorithm in
sorting an n-element list has been proved:

Cavg(n) ≥ log2 n!.

Analysis & Design of Algorithms (BCS401) AIML-CEC Page 3

Review Questions

1. What is a decision tree in the context of algorithms?

2. Why is the height of a decision tree important in analyzing the performance of an algorithm?

3. What is meant by the information-theoretic lower bound in decision trees?

4. List the types of problems that can be analyzed using decision trees.

5. List two sorting algorithms that are considered asymptotically optimal based on decision tree
analysis.

Analysis & Design of Algorithms (BCS401) AIML-CEC Page 4

 LECTURE 40

Decision Trees for Searching a Sorted Array

In this section, we shall see how decision trees can be used for establishing lower bounds on the
number of key comparisons in searching a sorted array of n keys: A[0]<A[1]< . . .<A[n − 1]. The
principal algorithm for this problem is binary search. As we saw in Section 4.4, the number of
comparisons made by binary search in the worst case, Cworst(n), is given by the formula

Cworst(n)=log2 n + 1= log2(n + 1).

We will use decision trees to determine whether this is the smallest possible number of comparisons.
Since we are dealing here with three-way comparisons in which search keyK is compared with some
element A[i] to see whether K <A[i],K = A[i], orK >A[i], it is natural to try using ternary decision
trees. Figure 11.4 presents such a tree for the case of n = 4.The internal nodes of that tree indicate
the array’s elements being compared with the search key. The leaves indicate either a matching
element in the case of a successful search or a found interval that the search key belongs to in the
case of an unsuccessful search. We can represent any algorithm for searching a sorted array by three-
way comparisons with a ternary decision tree similar to that in Figure 11.4. For an array of n
elements, all such decision trees will have 2n + 1 leaves (n for successful searches and n + 1 for
unsuccessful ones). Since the minimum height h of a ternary tree with l leaves is log3, we get
following lower bound on the number of worst-case comparisons:

Cworst(n) ≥ log3(2n + 1).

This lower bound is smaller than log2(n + 1), the number of worst-case comparisons for binary
search, at least for large values of n (and smaller than or equal to log2(n + 1) for every positive

Analysis & Design of Algorithms (BCS401) AIML-CEC Page 5

integer n—see Problem 7 in this section’s exercises). Can we prove a better lower bound, or is binary
search far from being optimal? The answer turns out to be the former. To obtain a better lower bound,
we should consider binary rather than ternary decision trees, such as the one in Figure 11.5. Internal
nodes in such a tree correspond to the same three way comparisons as before, but they also serve as
terminal nodes for successful searches. Leaves therefore represent only unsuccessful searches, and
there are n + 1 of them for searching an n-element array.

Review Questions

1. What is the principal algorithm for searching a sorted array?

2. Why do we use decision trees to analyze searching algorithms?

3. What is a ternary decision tree?

4. Why do ternary decision trees have 2n + 1 leaves for an array of n elements?

5. List the differences between ternary and binary decision trees for searching.

Analysis & Design of Algorithms (BCS401) AIML-CEC Page 6

 LECTURE 41

NP-Complete and NP-Hard problems

Basic concepts

For many of the problems we know and study, the best algorithms for their solution have
computing times can be clustered into two groups;

1. Solutions are bounded by the polynomial- Examples include Binary search O(log n),
Linear search O(n), sorting algorithms like merge sort O(n log n), Bubble sort O(n2)
&matrix multiplication O(n3) or in general O(nk) where k is a constant.

2. Solutions are bounded by a non-polynomial-Examples include travelling salesman

problem O(n22n) & knapsack problem O(2n/2). As the time increases exponentially, even
moderate size problems cannot be solved.

So far, no one has been able to device an algorithm which is bounded by the polynomial for the
problems belonging to the non-polynomial. However impossibility of such an algorithmis not
proved.

P, NP, NP-Complete and NP-Hard classes

Definition: P is a set of all decision problems solvable by a deterministic algorithm in

polynomial time.

Definition: NP is the set of all decision problems solvable by a nondeterministic algorithm in

polynomial time. This also implies P ⊆ NP

Problems known to be in P are trivially in NP — the nondeterministic machine just never

troubles itself to fork another process, and acts just like a deterministic one. One example of a
problem not in P but in NP is Integer Factorization.

But there are some problems which are known to be in NP but don’t know if they’re in P. The
traditional example is the decision-problem version of the Travelling Salesman Problem
(decision-TSP). It’s not known whether decision-TSP is in P: there’s no known poly-time
solution, but there’s no proof such a solution doesn’t exist.

There are problems that are known to be neither in P nor NP; a simple example is to enumerate
all the bit vectors of length n. No matter what, that takes 2n steps.
Analysis & Design of Algorithms (BCS401) AIML-CEC Page 7
 Now, one more concept: given decision problems P and Q, if an algorithm can transform a
solution for P into a solution for Q in polynomial time, it’s said that Q is poly-time reducible
(or just reducible) to P.

The most famous unsolved problem in computer science is “whether P=NP or P≠NP? ”

Figure: Commonly believed

relationship between P and NP

Figure: Commonly believed relationship between P, NP, NP-

Complete and NP-hard problems

Definition: A decision problem D is said to be NP-complete if:

3. it belongs to class NP
4. every problem in NP is polynomially reducible to D

The fact that closely related decision problems are polynomially reducible to each other is not
very surprising. For example, Hamiltonian circuit problem is polynomially reducible to the
decision version of the traveling salesman problem.

NP-Complete problems have the property that it can be solved in polynomial time if all other
NP-Complete problems can be solved in polynomial time. i.e if anyone ever finds a poly-time
solution to one NP-complete problem, they’ve automatically got one for all the NP-complete
problems; that will also mean that P=NP.

Example for NP-complete is the CNF-satisfiability problem. The CNF-satisfiability problem

deals with boolean expressions. This is given by Cook in 1971. The CNF-satisfiabilityproblem

Analysis & Design of Algorithms (BCS401) AIML-CEC Page 8

 asks whether one can assign true and false values to variables of a given boolean expression in
its CNF form to make the entire expression true.

Over the years many problems in NP have been proved to be in P (like Primality Testing). Still,
there are many problems in NP not proved to be in P. i.e. the question still remains whether
P=NP? NP Complete Problems helps in solving this question. They are a subsetof NP
problems with the property that all other NP problems can be reduced to any of them in
polynomial time. So, they are the hardest problems in NP, in terms of running time. If it can be
showed that any NP-Complete problem is in P, then all problems in NP will be in P (because
of NP-Complete definition), and hence P=NP=NPC.

NP Hard Problems - These problems need not have any bound on their running time. If
any NP-Complete Problem is polynomial time reducible to a problem X, that problem X
belongs to NP-Hard class. Hence, all NP-Complete problems are also NP-Hard. In other words
if a NP-Hard problem is non-deterministic polynomial time solvable, it is a NP- Complete
problem. Example of a NP problem that is not NPC is Halting Problem.

If a NP-Hard problem can be solved in polynomial time then all NP-Complete can be solved
in polynomial time.

“All NP-Complete problems are NP-Hard but not all NP-Hard problems are not NP-
Complete.”NP-Complete problems are subclass of NP-Hard

Review Questions

1. Why are non-polynomial bounded problems significant in computing?

2. What is the class P?

3. Why is P considered a subset of NP?

4. What are the two conditions for a problem to be NP-complete?

5. Why are all NP-complete problems also NP-hard?

Analysis & Design of Algorithms (BCS401) AIML-CEC Page 9

 LECTURE 42

Backtracking

Some problems can be solved, by exhaustive search. The exhaustive search technique suggests
generating all candidate solutions and then identifying the one (or the ones) with a desired
property.

Backtracking is a more intelligent variation of this approach. The principal idea is to construct
solutions one component at a time and evaluate such partially constructed candidates as
follows. If a partially constructed solution can be developed further without violating the
problem’s constraints, it is done by taking the first remaining legitimate option for the next
component. If there is no legitimate option for the next component, no alternatives for any
remaining component need to be considered. In this case, the algorithm backtracks to replace
the last component of the partially constructed solution with its next option.

It is convenient to implement this kind of processing by constructing a tree of choices being

made, called the state-space tree. Its root represents an initial state before the search for a
solution begins. The nodes of the first level in the tree represent the choices made for the first
component of a solution; the nodes of the second level represent the choices for the second
component, and soon. A node in a state-space tree is said to be promising if it corresponds to
a partially constructed solution that may still lead to a complete solution; otherwise, it is
called non-promising. Leaves represent either non-promising dead ends or complete solutions
found by the algorithm.

In the majority of cases, a statespace tree for a backtracking algorithm is constructed in the
manner of depth-first search. If the current node is promising, its child is generated by adding
the first remaining legitimate option for the next component of a solution, and the processing
moves to this child. If the current node turns out to be non-promising, the algorithm backtracks
to the node’s parent to consider the next possible option for its last component; if there is no
such option, it backtracks one more level up the tree, and so on. Finally, if the algorithm reaches
a complete solution to the problem, it either stops (if just one solution is required) or continues
searching for other possible solutions.

N-Queens problem

The problem is to place n queens on an n × n chessboard so that no two queens attack each
Analysis & Design of Algorithms (BCS401) AIML-CEC Page 10
 other by being in the same row or in the same column or on the same diagonal.

So let us consider the four-queens problem and solve it by the backtracking technique.Since
each of the four queens has to be placed in its own row, all we need to do is to assign a column
for each queen on the board presented in figure.

start with the empty board and then place queen 1 in the first possible position of its row, which
is in column 1 of row 1. Then we place queen 2, after trying unsuccessfully columns 1 and 2, in
the first acceptable position for it, which is square (2, 3), the square in row 2 and column 3. This
proves to be a dead end because there is no acceptable position for queen 3. So, the algorithm
backtracks and puts queen 2 in the next possible position at (2, 4). Then queen 3 is placed at (3,
2), which proves to be another dead end. The algorithm thenbacktracks all the way to queen 1 and
moves it to (1, 2). Queen 2 then goes to (2, 4), queen 3 to(3, 1), and queen 4 to (4, 3), which is a

solution to the problem. The state-space tree of this search is shown in figure.
Figure: State-space tree of solving the four-queens problem by backtracking. × denotes

Analysis & Design of Algorithms (BCS401) AIML-CEC Page 11

 an unsuccessful attempt to place a queen in the indicated column. Thenumbers above
the nodes indicate the order in which the nodes are generated.

If other solutions need to be found, the algorithm can simply resume its operations at the leaf
at which it stopped. Alternatively, we can use the board’s symmetry for this purpose.

Finally, it should be pointed out that a single solution to the n-queens problem for any n ≥ 4
can be found in linear time.

Review Questions

1. Why is backtracking considered a more intelligent variation of exhaustive search?

2. What is a state-space tree in the context of backtracking?

3. What is the objective of the N-Queens problem?

4. How does the backtracking algorithm place queens in the N-Queens problem?

5. What does the state-space tree represent in the context of the N-Queens problem?

Analysis & Design of Algorithms (BCS401) AIML-CEC Page 12

 LECTURE 43
Sum of subsets problem

Problem definition: Find a subset of a given set A = {a1, . . . , an} of n positive integers whose
sum is equal to a given positive integer d.

For example, for A = {1, 2, 5, 6, 8} and d = 9, there are two solutions: {1, 2, 6} and {1, 8}.
Of course, some instances of this problem may have no solutions.

It is convenient to sort the set’s elements in increasing order. So, we will assume that

a1< a2< . . . < an.

The state-space tree can be constructed as a binary tree like that in Figure shown below forthe
instance A = {3, 5, 6, 7} and d = 15.

The number inside a node is the sum of the elements already included in the subsets
represented by the node. The inequality below a leaf indicates the reason for its termination.

The root of the tree represents the starting point, with no decisions about the given elements
made as yet. Its left and right children represent, respectively, inclusion and exclusion of a1 in
a set being sought.

Similarly, going to the left from a node of the first level corresponds to inclusion of a 2 while
going to the right corresponds to its exclusion, and so on. Thus, a path from the root to a node
on the ith level of the tree indicates which of the first in numbers have been included in the
subsets represented by that node.

We record the value of s, the sum of these numbers, in the node. If s is equal to d, we have a
solution to the problem. We can either report this result and stop or, if all the solutions need
to be found, continue by backtracking to the node’s parent. If s is not equal to d, we can
terminate the node as non-promising if either of the following two inequalities holds:
Analysis & Design of Algorithms (BCS401) AIML-CEC Page 13
 Review Questions

1. Why is it convenient to sort the elements of the set in increasing order for the sum of
subsets problem?

2. What does the root of the state-space tree represent in the sum of subsets problem?

3. How do we determine if a node in the state-space tree is promising or non-promising in the

sum of subsets problem?

Analysis & Design of Algorithms (BCS401) AIML-CEC Page 14

 LECTURE 44

Branch and Bound

Recall that the central idea of backtracking, discussed in the previous section, is to cut off a
branch of the problem’s state-space tree as soon as we can deduce that it cannot lead to a
solution. This idea can be strengthened further if we deal with an optimization problem.

An optimization problem seeks to minimize or maximize some objective function (a tour

length, the value of items selected, the cost of an assignment, and the like), usually subject to
some constraints. An optimal solution is a feasible solution with the best value of theobjective
function (e.g., the shortest Hamiltonian circuit or the most valuable subset of items that fit the
knapsack).

Compared to backtracking, branch-and-bound requires two additional items:

1. a way to provide, for every node of a state-space tree, a bound on the best value of the
objective function on any solution that can be obtained by adding further components
to the partially constructed solution represented by the node
2. the value of the best solution seen so far

In general, we terminate a search path at the current node in a state-space tree of a branch- and-
bound algorithm for any one of the following three reasons:
1. The value of the node’s bound is not better than the value of the best solution seen so
far.
2. The node represents no feasible solutions because the constraints of the problem are
already violated.
3. The subset of feasible solutions represented by the node consists of a single point (and
hence no further choices can be made)—in this case, we compare the value of the
objective function for this feasible solution with that of the best solution seen so far and
update the latter with the former if the new solution is better.

Analysis & Design of Algorithms (BCS401) AIML-CEC Page 15

Knapsack problem:

Let us now discuss how we can apply the branch-and-bound technique to solving the knapsack
problem. Given n items of known weights wi and values vi, i = 1, 2, . . . , n, and a knapsack of
capacity W, find the most valuable subset of the items that fit in the knapsack.
It is convenient to order the items of a given instance in descending order by their value-to-
weight ratios.

Each node on the ith level of state space tree, 0 ≤ i ≤ n, represents all the subsets of n items that
include a particular selection made from the first i ordered items. This particular selection is
uniquely determined by the path from the root to the node: a branch going to the left indicates
the inclusion of the next item, and a branch going to the right indicates its exclusion.

We record the total weight w and the total value v of this selection in the node, along with some
upper bound ub on the value of any subset that can be obtained by adding zero or more items
to this selection. A simple way to compute the upper bound ub is to add to v, the total value of
the items already selected, the product of the remaining capacity of the knapsack W
– w and the best per unit payoff among the remaining items, which is vi+1/wi+1:

ub = v + (W − w)(vi+1/wi+1).

Example: Consider the following problem. The items are already ordered in descending order
of their value-to-weight ratios.

Let us apply the branch-and-bound algorithm. At the root of the state-space tree (see Figure
12.8), no items have been selected as yet. Hence, both the total weight of the items already
selected w and their total value v are equal to 0. The value of the upper bound is 100.

Node 1, the left child of the root, represents the subsets that include item 1. The total weight
and value of the items already included are 4 and 40, respectively; the value of the upper bound
is 40 + (10 − 4) * 6 = 76.

Analysis & Design of Algorithms (BCS401) AIML-CEC Page 16

Node 2 represents the subsets that do not include item 1. Accordingly, w = 0, v = 0, and ub =0 +
(10 − 0) * 6 = 60. Since node 1 has a larger upper bound than the upper bound of node 2, it is
more promising for this maximization problem, and we branch from node 1 first. Its children—
nodes 3 and 4—represent subsets with item 1 and with and without item 2, respectively. Since
the total weight w of every subset represented by node 3 exceeds the knapsack’s capacity, node 3
can be terminated immediately.

Node 4 has the same values of w and v as its parent; the upper bound ub is equal to 40 + (10
− 4) * 5 = 70. Selecting node 4 over node 2 for the next branching (Due to better ub), we get nodes
5 and 6 by respectively including and excluding item 3. The total weights and values aswell as
the upper bounds for these nodes are computed in the same way as for the preceding nodes.

Branching from node 5 yields node 7, which represents no feasible solutions, and node 8, which
represents just a single subset {1, 3} of value 65. The remaining live nodes 2 and 6 have smaller
upper-bound values than the value of the solution represented by node 8. Hence, both can be
terminated making the subset {1, 3} of node 8 the optimal solution to the problem.

Solving the knapsack problem by a branch-and-bound algorithm has a rather unusual

characteristic. Typically, internal nodes of a state-space tree do not define a point of the problem’s
search space, because some of the solution’s components remain undefined. (See, for example,
the branch-and-bound tree for the assignment problem discussed in the preceding subsection.)
For the knapsack problem, however, every node of the tree representsa subset of the items given.
We can use this fact to update the information about the best subset seen so far after generating
each new node in the tree. If we had done this for the instance investigated above, we could have
terminated nodes 2 and 6 before node 8 was generated because they both are inferior to the subset
of value 65 of node 5.

Review Questions

1. Why is branch-and-bound considered an optimization problem technique?

2. What are the two additional items required in branch-and-bound compared to

backtracking?

3. What is the objective of the knapsack problem in the context of branch-and-bound?

4. Why is it convenient to order the items by their value-to-weight ratios in the knapsack
problem?
 LECTURE 45 and 46

Approximation Algorithms for the Knapsack Problem

The knapsack problem, another well-known NP-hard problem, was also introduced in Section
3.4: given n items of known weights w1, . . . , wn and values v1, . . . , vn and a knapsack of weight
capacity W, find the most valuable subset of the items that fits into the knapsack. We saw how
this problem can be solved by exhaustive search, dynamic programming and branch-and-bound.
Now we will solve this problem by approximation algorithms.

Greedy Algorithms for the Knapsack Problem We can think of several greedy approaches to
this problem. One is to select the items in decreasing order of their weights; however, heavier
items may not be the most valuable in the set. Alternatively, if we pick up the items in decreasing
order of their value, there is no guarantee that the knapsack’s capacity will be used efficiently.
Can we find a greedy strategy that takes into account both the weights and values? Yes, we can,
by computing the value-to-weight ratios vi/wi, i = 1, 2, . . . , n, and selecting the items in decreasing
order of these ratios. Here is the algorithm based on this greedy heuristic.

Greedy algorithm for the discrete knapsack problem

Step 1 Compute the value-to-weight ratios ri= vi/wi, i = 1, . . . , n, for the items given.

Step 2 Sort the items in nonincreasing order of the ratios computed in Step 1.

Step 3 Repeat the following operation until no item is left in the sorted list: if the current item on
the list fits into the knapsack, place it in the knapsack and proceed to the next item; otherwise,
just proceed to the next item.

Example: Let us consider the instance of the knapsack problem with the knapsack capacity 10
and the item information as follows:
The greedy algorithm will select the first item of weight 4, skip the next item of weight 7, select
the next item of weight 5, and skip the last item of weight 3. The solution obtained happens to be
optimal for this instance

Greedy algorithm for the continuous knapsack problem

Step 1 Compute the value-to-weight ratios vi/wi, i = 1, . . . , n, for the items given.

Step 2 Sort the items in non-increasing order of the ratios computed in Step 1.

Step 3 Repeat the following operation until the knapsack is filled to its full capacity or no item is
left in the sorted list: if the current item on the list fits into the knapsack in its entirety, take it and
proceed to the next item; otherwise, take its largest fraction to fill the knapsack to its full capacity
and stop.

For example, for the four-item instance used in Example 5 to illustrate the greedy algorithm for
the discrete version, the algorithm will take the first item of weight 4 and then 6/7 of the next item
on the sorted list to fill the knapsack to its full capacity.

It should come as no surprise that this algorithm always yields an optimal solution to the
continuous knapsack problem. Indeed, the items are ordered according to their efficiency in using
the knapsack’s capacity. If the first item on the sorted list has weight w1 and value v1, no solution
can use w1 units of capacity with a higher payoff than v1. If we cannot fill the knapsack with the
first item or its fraction, we should continue by taking as much as we can of the second most
efficient item, and so on. A formal rendering of this proof idea is somewhat involved, and we will
leave it for the exercises.

Note also that the optimal value of the solution to an instance of the continuous knapsack problem
can serve as an upper bound on the optimal value of the discrete version of the same instance.
This observation provides a more sophisticated way of computing upper bounds for solving the
discrete knapsack problem by the branch-and-bound method

Approximation Schemes: We now return to the discrete version of the knapsack problem. For
this problem, unlike the traveling salesman problem, there exist polynomial-time approximation
schemes, which are parametric families of algorithms that allow us to get approximations s(k) a
with any predefined accuracy level:

where k is an integer parameter in the range 0 ≤ k < n. The first approximation scheme was
suggested by S. Sahni in 1975 [Sah75]. This algorithm generates all subsets of k items or less,
and for each one that fits into the knapsack, it adds the remaining items as the greedy algorithm
would do (i.e., in nonincreasing order of their value-to-weight ratios). The subset of the highest
value obtained in this fashion is returned as the algorithm’s output.

Example: A small example of an approximation scheme with k = 2 is provided in the following

figure. The algorithm yields {1, 3, 4}, which is the optimal solution for this instance.

You can be excused for not being overly impressed by this example. And, indeed, the importance
of this scheme is mostly theoretical rather than practical. It lies in the fact that, in addition to
approximating the optimal solution with any predefined accuracy level, the time efficiency of this
algorithm is polynomial in n. Indeed, the total number of subsets the algorithm generates before
adding extra elements is
For each of those subsets, it needs O(n) time to determine the subset’s possible extension. Thus,
the algorithm’s efficiency is in O(knk+1). Note that although it is polynomial in n, the time
efficiency of Sahni’s scheme is exponential in k. More sophisticated approximation schemes,
called fully polynomial schemes, do not have this shortcoming.

Review Questions

1. Why does the greedy algorithm for the discrete knapsack problem sometimes yield an
optimal solution?

2. Why does the greedy algorithm always yield an optimal solution for the continuous
knapsack problem?

3. How can the solution to the continuous knapsack problem be used in the branch-and-
bound method for the discrete knapsack problem?

4. What is a polynomial-time approximation scheme (PTAS) for the knapsack problem?

5. Why is the importance of Sahni's approximation scheme considered more theoretical than
practical?