13.1.1 Algorithm Design Paradigm

The Greedy Paradigm: Construct a solution iteratively, via a sequence of myopic decisions, and hope that everything works out in the end.

Features: 1. Easy to come up with one or more greedy algorithms. 2. Easy to analyze the running time. 3. Hard to establish correctness.

Most greedy algorithms are not always correct.

13.2 A Scheduling Problem

Suppose a problem instance that has three jobs with $l_1=1, l_2=2, l_3=3$, then we should schedule them in what order does it have the least completion time in total.

The objective function is

$$\min_\sigma \sum_{j=1}^n w_jC_j(\sigma)$$

Then their weights are allocated as follows: $w_1=3, w_2=2, w_3=1$.

For example, if we order them in current order, then objective function returns

$$3\times 1 + 2\times 3 + 1\times 6 = 15$$

Well, by checking all $3!=6$ possible schedules, then you can verify that this is the schedule that minimizes the sum of weighted completion times.

However, we don’t have to check all possible schedule plans, here we introduce an effective greedy algorithm:

13.3 Developing a Greedy Algorithm

There are 2 proposal for designing the greedy algorithm. We design a score, which indicate how cost-efficient the job is.

Here we have 2 criteria, (i) holding the length fixed, it should be increasing in the job’s weight; (ii) holding the weight fixed, it should be decreasing in jobs length.

Also, higher scores are better.

#1 Proposal  for score of job $j$ : $w_j-l_j$

the score might be negative, but that poses no obstacle to sequencing the jobs from heights to lowest score.

#2 Proposal for score of job $j$ : $\frac{w_j}{l_j}$

These 2 scoring functions we call them GreedyDiff and GreedyRatio.

Using the criteria above, GreedyDiff can be ruled out. Then how can we proof the correctness of GreedyRatio.

Theorem 13.1 (Correctness of GreedyRatio)

For every set of positive job weights $w_i$ and positive job lengths $l_i$, the GreedyRatio Algorithm outputs a schedule with the minimum-possible sum of weighted completion times.

13.4 Proof of Correctness