604 Chapter 11 Approximation Algorithms
Approximate solution Optimal solution:
via greedy algorithm:
The greedy
algorithm was
doing well
until the last
job arrived.
M1 M2 M3 M4 M1 M2 M3 M4
Figure 11.3 A bad example for the greedy balancing algorithm with m = 4.
What does the optimal solution look like in this example? It assigns the
large job to one of the machines, say, M1, and evenly spreads the remaining
jobs over the other m − 1 machines. This results in a makespan of m. Thus
the ratio between the greedy algorithm’s solution and the optimal solution is
(2m − 1)/m = 2 − 1/m, which is close to a factor of 2 when m is large.
See Figure 11.3 for a picture of this with m = 4; one has to admire the
perversity of the construction, which misleads the greedy algorithm into
perfectly balancing everything, only to mess everything up with the final giant
item.
In fact, with a little care, one can improve the analysis in (11.3) to show
that the greedy algorithm with m machines is within exactly this factor of
2 − 1/m on every instance; the example above is really as bad as possible.
Extensions: An Improved Approximation Algorithm
Now let’s think about how we might develop a better approximation
algorithm—in other words, one for which we are always guaranteed to be
within a factor strictly smaller than 2 away from the optimum. To do this, it
helps to think about the worst cases for our current approximation algorithm.
Our earlier bad example had the following flavor: We spread everything out
very evenly across the machines, and then one last, giant, unfortunate job
arrived. Intuitively, it looks like it would help to get the largest jobs arranged
nicely first, with the idea that later, small jobs can only do so much damage.
And in fact, this idea does lead to a measurable improvement.
Thus we now analyze the variant of the greedy algorithm that first sorts
the jobs in decreasing order of processing time and then proceeds as before.
11.1 Greedy Algorithms and Bounds on the Optimum: A Load Balancing Problem 605
We will prove that the resulting assignment has a makespan that is at most 1.5
times the optimum.
Sorted-Balance:
Start with no jobs assigned
Set Ti = 0 and A(i) = ∅ for all machines Mi
Sort jobs in decreasing order of processing times tj
Assume that t1 ≥ t2 ≥ . . . ≥ tn
For j = 1, . . . , n
Let Mi be the machine that achieves the minimum mink Tk
Assign job j to machine Mi
Set A(i) ← A(i) ∪ {j}
Set Ti ← Ti + tj
EndFor
The improvement comes from the following observation. If we have fewer
than m jobs, then the greedy solution will clearly be optimal, since it puts each
job on its own machine. And if we have more than m jobs, then we can use
the following further lower bound on the optimum.
(11.4) If there are more than m jobs, then T ∗ ≥ 2tm+1.
Proof. Consider only the first m + 1 jobs in the sorted order. They each take
at least tm+1 time. There are m + 1 jobs and only m machines, so there must
be a machine that gets assigned two of these jobs. This machine will have
processing time at least 2tm+1.
(11.5) Algorithm Sorted-Balance produces an assignment of jobs to ma-
chines with makespan T ≤ 23 T ∗.
Proof. The proof will be very similar to the analysis of the previous algorithm.
As before, we will consider a machine Mi that has the maximum load. If Mi
only holds a single job, then the schedule is optimal.
So let’s assume that machine Mi has at least two jobs, and let tj be the
last job assigned to the machine. Note that j ≥ m + 1, since the algorithm will
assign the first m jobs to m distinct machines. Thus tj ≤ tm+1 ≤ 21 T ∗, where
the second inequality is (11.4).
We now proceed as in the proof of (11.3), with the following single change.
At the end of that proof, we had inequalities Ti − tj ≤ T ∗ and tj ≤ T ∗, and we
added them up to get the factor of 2. But in our case here, the second of these
606 Chapter 11 Approximation Algorithms
inequalities is, in fact, tj ≤ 21 T ∗; so adding the two inequalities gives us the
bound
3
Ti ≤ T ∗ .
2
11.2 The Center Selection Problem
Like the problem in the previous section, the Center Selection Problem, which
we consider here, also relates to the general task of allocating work across
multiple servers. The issue at the heart of Center Selection is where best to
place the servers; in order to keep the formulation clean and simple, we will not
incorporate the notion of load balancing into the problem. The Center Selection
Problem also provides an example of a case in which the most natural greedy
algorithm can result in an arbitrarily bad solution, but a slightly different
greedy method is guaranteed to always result in a near-optimal solution.
The Problem
Consider the following scenario. We have a set S of n sites—say, n little towns
in upstate New York. We want to select k centers for building large shopping
malls. We expect that people in each of these n towns will shop at one of the
malls, and so we want to select the sites of the k malls to be central.
Let us start by defining the input to our problem more formally. We are
given an integer k, a set S of n sites (corresponding to the towns), and a
distance function. When we consider instances where the sites are points
in the plane, the distance function will be the standard Euclidean distance
between points, and any point in the plane is an option for placing a center.
The algorithm we develop, however, can be applied to more general notions of
distance. In applications, distance sometimes means straight-line distance, but
can also mean the travel time from point s to point z, or the driving distance
(i.e., distance along roads), or even the cost of traveling. We will allow any
distance function that satisfies the following natural properties.
. dist(s, s) = 0 for all s ∈ S
. the distance is symmetric: dist(s, z) = dist(z, s) for all sites s, z ∈ S
. the triangle inequality: dist(s, z) + dist(z, h) ≥ dist(s, h)
The first and third of these properties tend to be satisfied by essentially all
natural notions of distance. Although there are applications with asymmetric
distances, most cases of interest also satisfy the second property. Our greedy al-
gorithm will apply to any distance function that satisfies these three properties,
and it will depend on all three.