8. The first-fit decreasing (FFD) approximation algorithm for the bin
packing problem starts by sorting the items in nonincreasing order of their
sizes and then acts as the first-fit algorithm.
a. Apply FFD to the instance
9. a.BDesign a simple 2-approximation algorithm for finding the minimum
vertex cover (the vertex cover with the smallest number of vertices) in
a given graph.
10. a. Design a polynomial-time greedy algorithm for the graph-coloring prob-
lem.
Hints to Exercises 12.3
1. a. Start by marking the first column of the matrix and finding the smallest
element in the first row and an unmarked column.
2. a. The simplest approach is to mark matrix columns that correspond to
visited cities. Alternatively, you can maintain a linked list of unvisited
cities.
3. Do the walk in the clockwise direction.
5. First, determine the time efficiency of each of the three steps of the algo-
rithm.
6. You will have to prove two facts:
i. (∗)≤2()for any instance of the knapsack problem, where ()
is the value of the approximate solution obtained by the enhanced greedy
7. a. Trace the algorithm on the instance given and then answer the question
whether you can put the same items in fewer bins.
b. What is the basic operation of this algorithm? What inputs make
the algorithm run the longest?
8. a. Trace the algorithm on the instance given and then answer the question
whether you can put the same items in fewer bins.
b. You can answer the question either with a theoretical argument or
by providing a counterexample.
9. a. One such algorithm is based on the idea similar to that of the source
removal algorithm for the transitive closureexceptthatitstartswithan
arbitrary edge of the graph.
10. a. Color the vertices without introducing new colors unnecessarily.
b. Find a sequence of graphs for which the ratio
κ()
κ∗()
22
Solutions to Exercises 12.3
1. a. The nearest-neighbor algorithm yields the tour 1−3−2−5−4−1of
length 58.
b. To compute the accuracy ratio, we’ll have to find the length of the
optimaltourfortheinstancegivenbythedistancematrix
2. a. This is a pseudocode of a straightforward implementation.
Algorithm NearestNeighbor ([1 1],)
//Implements the nearest-neighbor heuristic for the TSP
//Input: A matrix [1 1]of intercity distances and
// an index of the starting city
3. The tour in question is a, b, d, e, c, a of length 38, which is not the same
4. The assertion in question follows immediately from the following general-
ization of the triangle inequality. If distances satisfy the triangle inequal-
ity, then they also satisfy its extension to an arbitrary positive number
of intermediate cities:
5. Computing value-to-weight ratios is in Θ()The time efficiency of sort-
ing depends on the sorting algorithm used: it’s in (2)for elementary
6. i. Let us prove that
(∗)≤2()
for any instance of the knapsack problem, where ()is the value of
the approximate solution obtained by the enhanced greedy algorithm and
(∗)is the optimal value of the exact solution for the same instance. In
ii. Consider, for example, the family of instances defined as follows:
item weight value
1(+1)2(+2)21
2221
3221
7. a. The first-fit algorithm places items 1, 3, and 4 into the first bin, item
2 into the second bin, and item 5 into the third bin. This solution is not
optimal because it’s inferior to the solution that places items 1 and 5 into
one bin and items 2, 3, and 4 into the other. The latter solution is optimal
b. The basis operation is to check whether the current item fits into a
particular bin. (It can be done in constant time if the amount of remain-
ing space is maintained for each started bin.) The worst-case input will
force the algorithm to check all −1started bins when placing the th
item for =2 For example, this will happen for any input with
c. Obviously, FF is a polynomial time algorithm. We’ll prove first that
for any instance of the problem that requires more than one bin (i.e.,
P
=1 1),
2
X
=1
where is the number of bins in the approximate solution obtained by
the first-fit(FF ) algorithm. In any solution obtained by this algorithm,
which proves the inequality 2P
=1 . Combining this with the
obvious observation that P
=1 ≤∗we obtain
26
8. a. The first-fit decreasing algorithm (FFD) places items of sizes 0.7, 0.2,
and 0.1 in the first bin and items of sizes 0.5 and 0.4 in the second one.
Since ∗≥dP5
=1 e=2at least two bins are necessary, making the
solution obtained by FFD optimal.
b. The answer is no: if it did, FFD would be a polynomial time algo-
rithm that solves this NP-hard problem. Here is one counterexample:
c. Obviously, FFD is a polynomial time algorithm. If FFD yields
bins while the optimal number of bins is ∗we know from the properties
quoted in the hint that the number of items in the extra bins is at most
∗−1with each of the items be of size at most 1/3. Therefore the total
number of extra bins is at most d(∗−1)3e, and we have the following
upper bound on the approximation’s accuracy ratio:
d. Note the two versions of this task. The easy one would simply com-
pare which of the two greedy algorithms yields a more accurate solution
more often. It is easy because, in this form, one doesn’t need to know the
27
9. a. Initialize the vertex cover to the empty set. Repeat the following until
no edges are left: select an arbitrary edge, add both its endpoints to the
vertex cover, and remove from the graph all the edges incident with either
of these two endpoint vertices.
b. No. Consider, for example, the complete bipartite graph with
vertices 1
1…,
:
1
a2
a3
an
a
10. a. The simplest greedy heuristic, called sequential coloring, is to color a
vertex in the first available color, i.e., the first color not used for coloring
any vertex adjacent to it. (Vertices are colored in the order given by the
graph’s data structure.)
Algorithm SC ()
28
b. Consider the following sequence of graphs with 2vertices specified
in the order 1
1…,
:
1
a2
a3
an
a
29
Exercises 12.4
1. a. Find on the Internet or in your library a procedure for finding a real
root of the general cubic equation 3+2+ +=0with real coeffi–
cients.
3. a. Prove that if ()is a polynomial of an odd degree, then it must have
at least one real root.
where ()is the quotient of the division of ()by −0
4. Prove inequality (12.7).
5. Apply the bisection method to find the root of the equation
with an absolute error smaller than 10−2
8. Derive formula (12.11) underlying Newton’s method.
9. Apply Newton’s method to find the root of the equation
10. Give an example that shows that the approximation sequence of Newton’s
method may diverge.
Hints to Exercises 12.4
1. It might help your search to know that the solution was first published by
Italian Renaissance mathematician Girolamo Cardano.
2. You can answer these questions without using calculus or a sophisticated
3. a. Use the property underlying the bisection method.
b. Use the definition of division of polynomial ()by −0, i.e., the
4. Use the fact that |−∗|is the distance between the middle of
interval [
]and root ∗
5. Sketch the graph to determine a general location of the root and choose
an initial interval bracketing it. Use an appropriate inequality given
6. Write an equation of the line through the points (()) and (())
and find its -intercept.
7. See the example given in the section. As a stopping criterion, you may
use either the length of interval [
]or inequality (12.12).
32
Solutions to Exercises 12.4
1. a. Here is a solution as described at http://www.sosmath.com/algebra/factor/fac11/fac11.html:
First, substitute =−3to reduce the general cubic equation
3+2+ +=0
to the “depressed”cubic equation
2. a. Equation −1=0is equivalent to =1 The graphs of
1()=and 2()=1 clearly have a single common point between
0and1.
3. a. For a polynomial ()=+−1−1+ +0of an odd degree,
where 0
33
b. By definition of division of ()by −0where 0is a root of
()
()=()(−0)+
c. Differentiating both hand sides of equality
()=()(−0)
4. Since is the middle point of interval [
]its distance to any point
within that interval, including root ∗cannot exceed the interval’s half
length, which is (−)2That is
5. The graph of ()=3+−1makes it obvious that this polynomial
has a single real root that lies in the interval 01(It also follows
from the fact that this polynomial has an odd degree and its derivative
10−2
yields ≥7The following table contains the results of the first seven
iterations of the bisection method:
()
1 0.0- 1.0+ 0.5 -0.375
6. Substituting (()) and (())the two given points, into the
standard straight-line equation
35
Setting to0tofind the line’s -intercept, we obtain the following equa-
tion for
7. For ()=3+−1
0()=32+1≥1for every
()
1 0.0- 1.0+ 0.5 -0.375
8. Using the standard equation for the tangent line to the graph of the func-
tion ()at (()),weobtain
36
9. For ()=3+−1
The following table contains the results of the first two iterations of New-
ton’s method, with 0=1:
+1 ()
10. Equation 3
√=0has =0as its only root. Using the geometric in-
terpretation of Newton’s method, it is easy to see that the approximation
sequence (the -intercepts of the tangent lines) diverges for any initial
37