Greedy Method: General Principles and Machine Scheduling

The greedy method is a powerful algorithm design paradigm used to solve optimization problems. It makes the best choice available at each step, hoping that these locally optimal choices will lead to a globally optimal solution. This approach is often simple to implement but does not always guarantee optimality.

1. The General Method

The greedy method is a straightforward technique applicable to a wide variety of problems. For problems involving $n$ inputs, where we need to find a subset that satisfies certain conditions, the greedy approach can be highly effective.

A subset that satisfies all problem constraints is called a feasible solution. Among all feasible solutions, we are typically looking for one that either maximizes or minimizes an objective function. This particular feasible solution is known as an optimal solution.

The core idea of the greedy method is to work in stages, considering one input at a time. At each stage, a decision is made to determine if a particular input should be included in the optimal solution. This decision is based on a selection procedure that defines an order for considering inputs and a greedy criterion that dictates the locally optimal choice.

Two key properties usually indicate that a greedy approach might work:

Greedy Choice Property: A globally optimal solution can be arrived at by making a locally optimal choice at each step.
Optimal Substructure: An optimal solution to the problem contains optimal solutions to its subproblems.

2. Machine Scheduling Problem

Consider a scenario where you have $n$ tasks and an infinite number of machines. Each task $i$ has a start time $s_i$ and a finish time $f_i$ , where $s_i < f_i$ . The interval $[s_i, f_i]$ represents the processing interval for task $i$ . Two tasks, $i$ and $j$ , are said to overlap if their processing intervals overlap, excluding just touching at an endpoint (e.g., $[1,4]$ overlaps with $[2,4]$ but not with $[4,7]$ ).

A feasible task-to-machine assignment is one where no machine is assigned to two overlapping tasks; that is, each machine handles at most one task at any given time. The objective is to minimize the total number of machines required to complete all tasks.

Greedy Approach for Machine Scheduling:

The greedy strategy for this problem involves:

Sort Tasks: Arrange all tasks in non-decreasing order of their start times.
Assign Tasks: Process tasks one by one based on this sorted order.
- For each task, check if any old machine (a machine that has already been assigned at least one task) becomes available by the current task's start time. If multiple old machines are available, assign the task to any one of them (e.g., the one that finishes earliest, or simply the first one found).
- If no old machine is available by the task's start time, assign the task to a new machine.

Let's illustrate with an example: Suppose we have $n=7$ tasks labeled A to G, with their start and finish times:

| Task | Start ( $s_i$ ) | Finish ( $f_i$ ) | | :--- | :----------- | :------------- | | A | 0 | 2 | | B | 3 | 7 | | C | 4 | 7 | | D | 9 | 11 | | E | 7 | 10 | | F | 1 | 5 | | G | 6 | 8 |

Step 1: Sort by Start Time

| Task | Start ( $s_i$ ) | Finish ( $f_i$ ) | | :--- | :----------- | :------------- | | A | 0 | 2 | | F | 1 | 5 | | B | 3 | 7 | | C | 4 | 7 | | G | 6 | 8 | | E | 7 | 10 | | D | 9 | 11 |

Step 2: Assign Tasks

Task A (0,2): Machine M1. Available: M1 after 2.
Task F (1,5): M1 is busy until 2. No old machine available at time 1. Assign to M2. Available: M1 after 2, M2 after 5.
Task B (3,7): M1 is available at 2. Assign to M1. Available: M1 after 7, M2 after 5.
Task C (4,7): M2 is available at 5. No machine available at time 4. Assign to M3. Available: M1 after 7, M2 after 5, M3 after 7.
Task G (6,8): M2 is available at 5. Assign to M2. Available: M1 after 7, M2 after 8, M3 after 7.
Task E (7,10): M1 is available at 7. Assign to M1. Available: M1 after 10, M2 after 8, M3 after 7.
Task D (9,11): M2 is available at 8. Assign to M2. Available: M1 after 10, M2 after 11, M3 after 7.

Total machines used: 3. This greedy approach often provides an optimal solution for minimizing machines if tasks are scheduled based on earliest finish time availability.

3. Fractional Knapsack Problem

The Fractional Knapsack Problem involves $n$ objects, each with a weight $w_i$ and a profit $p_i$ . We have a knapsack with a maximum capacity $M$ . The objective is to fill the knapsack such that the total profit is maximized. A key characteristic is that objects can be divided, meaning we can take a fraction (where ) of an object , earning a profit of and consuming weight.

The problem can be formally stated as: Maximize $\sum_{i=1}^{n} P_i X_i$ Subject to $\sum_{i = 1}^{n} W_{i} X_{i}$ And , for .

A feasible solution is any set $(X_1, \dots, X_n)$ where the total weight is at most $M$ . An optimal solution is a feasible solution that yields the maximum possible total profit.

Greedy Approach (Price Per Unit):

The greedy strategy for the Fractional Knapsack Problem is based on the profit-to-weight ratio ( $P_i/W_i$ ) of each item.

Calculate Ratios: For each item $i$ , compute its profit-to-weight ratio $P_i/W_i$ .
Sort Items: Arrange the items in descending order based on their profit-to-weight ratios.
Fill Knapsack: Iterate through the sorted items:
- If the current item's weight $W_i$ is less than or equal to the remaining knapsack capacity, take the entire item (). Update the remaining capacity and total profit.

Example Walkthrough: Let $n=5$ , knapsack capacity $M=60$ kg. Items: | Item | Weight ( $W_i$ ) | Value ( $P_i$ ) | Ratio () | | :--- | :------------- | :------------ | :---------------- | | 1 | 5 | 30 | 6 | | 2 | 10 | 40 | 4 | | 3 | 15 | 45 | 3 | | 4 | 22 | 77 | 3.5 | | 5 | 25 | 90 | 3.6 |

Step 1 & 2: Calculate Ratios and Sort (descending ratio)

| Item | Weight ( $W_i$ ) | Value ( $P_i$ ) | Ratio ( $P_i/W_i$ ) | Sorted Order | | :--- | :------------- | :------------ | :---------------- | :----------- | | 1 | 5 | 30 | 6 | 1 | | 5 | 25 | 90 | 3.6 | 2 | | 4 | 22 | 77 | 3.5 | 3 | | 2 | 10 | 40 | 4 | 4 | | 3 | 15 | 45 | 3 | 5 |

Step 3: Fill Knapsack (M=60, P=0)

Item 1 (Ratio 6): $W_1 = 5 \le M = 60$ . Take whole. $X_1 = 1$ . . .

Optimal solution: $(X_1=1, X_2=0.8, X_3=0, X_4=1, X_5=1)$ for a total profit of .

4. Job Sequencing with Deadline

We are given a set of $n$ jobs. Each job $i$ has an integer deadline $d_i \ge 0$ and a profit $p_i \ge 0$ . The profit is earned only if job is completed by its deadline. Each job requires one unit of time for processing on a single machine. Only one machine is available.

A feasible solution is a subset $J$ of jobs such that all jobs in $J$ can be completed by their deadlines. The value of a feasible solution $J$ is the sum of the profits of all jobs in $J$ . An optimal solution is a feasible solution with the maximum possible total profit.

Greedy Approach:

Sort Jobs: Sort all jobs in non-increasing order of their profits ( $p_i$ ).
Schedule Jobs: Iterate through the sorted jobs. For each job:
- Determine the latest possible time slot $t$ such that $1 \le t \le d_i$ and the time slot is free.

Example: Let $n=4$ jobs. $(p_1, p_2, p_3, p_4) = (100, 10, 15, 27)$

Step 1: Sort by Profit (descending)

| Job | Profit ( $p_i$ ) | Deadline ( $d_i$ ) | | :-- | :------------- | :--------------- | | J1 | 100 | 2 | | J4 | 27 | 1 | | J3 | 15 | 2 | | J2 | 10 | 1 |

Maximum deadline is 2, so time slots are 1, 2. schedule array will represent slots.

Step 2: Schedule Jobs

J1 (p=100, d=2): Latest free slot $\le 2$ is 2. schedule[2] = J1. Profit = 100. schedule = [_, J1]
J4 (p=27, d=1): Latest free slot $\le 1$ is 1. schedule[1] = J4. Profit = $100+27 = 127$ . schedule = [J4, J1]
J3 (p=15, d=2): Latest free slot is none (slots 1 and 2 are occupied). Discard J3.

Optimal schedule: J4 at time 1, J1 at time 2. Total profit = 127.

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
 
// Structure to represent a job
struct Job {
    char id;        // Job ID
    int deadline;   // Deadline for the job
    int profit;     // Profit from the job
};
 
// Comparison function for sorting jobs by profit in descending order
bool compareJobs(const Job& a, const Job& b) {
    return a.profit > b.profit;
}
 
// Function to find the maximum profit and job sequence
std::pair<int, std::vector<char>> jobSequencingWithDeadline(std

5. Optimal Storage on Tapes

Imagine you have $n$ programs to store on a computer tape of length $L$ . Each program $i$ has a length $l_i$ . All programs can be stored if $\sum_{i=1}^{n} l_i \le L$ . When a program is retrieved, the tape is initially positioned at the front. Programs can only be retrieved from the front of the tape. If programs are stored in the order , the time to retrieve program is the sum of lengths of programs . The goal is to find an optimal permutation (ordering) for the programs to minimize the .

The retrieval time for program $i_j$ is $T_{i_j} = \sum_{k=1}^{j} l_{i_k}$ . The total retrieval time for all programs is . The Mean Retrieval Time (MRT) is .

Greedy Approach:

To minimize MRT, the greedy strategy is to simply store the programs in non-decreasing order of their lengths. That is, the shortest program goes first.

Example: Let $n=3$ programs with lengths $(l_1, l_2, l_3) = (5, 10, 3)$ .

Step 1: Sort by Length (ascending)

| Program | Length | | :------ | :----- | | 3 | 3 | | 1 | 5 | | 2 | 10 |

Optimal order: (3, 1, 2)

Step 2: Calculate Total Retrieval Time and MRT

Retrieval time for Program 3: $3$
Retrieval time for Program 1: $3 + 5 = 8$
Retrieval time for Program 2: $3 + 5 + 10 = 18$

Total Retrieval Time = $3 + 8 + 18 = 29$ . MRT = $29 / 3 \approx 9.67$ .

Let's compare this to other orderings from the source material:

| Order (Sr. No.) | Order | Total Retrieval Time | MRT | | :-------------- | :------- | :------------------- | :------- | | 1 | (1, 2, 3)| $5 + (5+10) + (5+10+3) = 38$ | $38/3 \approx 12.67$ | | 2 | (1, 3, 2)| | | | | | | |

The greedy choice (shortest first) indeed yields the minimum MRT.

6. Optimal Merge Pattern

When merging multiple sorted files, say $X_1, X_2, \dots, X_n$ , into a single sorted file, we can do this by repeatedly merging two sorted files at a time. The time required to merge two sorted files of lengths $n$ and records is . Different sequences of pairwise merges will result in different total comparison counts (or record moves). The problem is to find an optimal merge pattern that minimizes the total number of comparisons.

Greedy Approach:

The greedy strategy is to always combine the two smallest files (in terms of current number of records/length) at each stage. This creates a new merged file, which then replaces the two original files in the pool of files to be merged. This process continues until only one file remains.

Example: Files $X_1, X_2, X_3$ with lengths $30, 20, 10$ .

Method 1 (Non-optimal): Merge $X_1$ and $X_2$ first, then merge result with $X_3$ .

Merge $X_1(30)$ and $X_2(20)$ to get $Y_1(50)$ . Cost: .

ASCII Art representation:

text

      Y2 (60)
     /     \
   Y1(50)   X3(10)
  /    \
X1(30)  X2(20)

Method 2 (Greedy - Optimal): Merge the two smallest files first.

Smallest files are $X_2(20)$ and $X_3(10)$ . Merge them to get $Y_1(30)$ . Cost: .

ASCII Art representation:

text

      Y2 (60)
     /     \
   X1(30)   Y1(30)
           /    \
         X2(20)  X3(10)

The greedy method produces a lower total cost. This strategy can be implemented using a min-priority queue to efficiently find the two smallest files.

7. Huffman Codes

In telecommunication, it's desirable to represent messages (or symbols) using sequences of 0s and 1s such that frequently used messages have shorter codes, minimizing overall transmission and decoding costs. Huffman coding is a greedy algorithm that constructs such an optimal prefix code. A prefix code ensures that no code for a character is a prefix of the code for another character, allowing unambiguous decoding.

Greedy Approach:

Huffman's algorithm builds an extended binary tree. At each step, it combines the two smallest frequency symbols/nodes into a new parent node, whose frequency is the sum of its children's frequencies. This new node then replaces its children in the set, and the process repeats until only one node (the root of the Huffman tree) remains.

Steps:

Create Leaf Nodes: For each symbol, create a leaf node with its frequency.
Build Tree:
- Place all leaf nodes into a min-priority queue based on their frequencies.
- While there is more than one node in the priority queue:
  - Extract the two nodes with the smallest frequencies (say, x and y).
  - Create a new internal node z with frequency $freq(z) = freq(x) + freq(y)$ . Make and its left and right children (order doesn't matter for optimality, but conventionally (smaller frequency) is left).

Example: Symbols: A, B, C, D, E, F, G Frequencies: 2, 3, 5, 8, 13, 15, 18

Initial: (A:2), (B:3), (C:5), (D:8), (E:13), (F:15), (G:18)

Combine (A:2) and (B:3) -> New Node (AB:5). Remaining: (C:5), (AB:5), (D:8), (E:13), (F:15), (G:18)
Combine (C:5) and (AB:5) -> New Node (CAB:10). Remaining: (D:8), (CAB:10), (E:13), (F:15), (G:18)
Combine (D:8) and (CAB:10) -> New Node (DCAB:18). Remaining: (E:13), (F:15), (G:18), (DCAB:18)
Combine (E:13) and (F:15) -> New Node (EF:28). Remaining: (G:18), (DCAB:18), (EF:28)
Combine (G:18) and (DCAB:18) -> New Node (GDCAB:36). Remaining: (EF:28), (GDCAB:36)
Combine (EF:28) and (GDCAB:36) -> New Node (EFGDCAB:64). Root reached.

The resulting tree (and codes) can be visualized.

text

          (64)
         /    \
      (28)     (36)
     /   \    /    \
   (13) (15) (18)    (18)
   E     F    G     /   \
                   (8)   (10)
                   D    /    \
                       (5)    (5)
                      C      /   \
                            (2)   (3)
                            A     B

From this tree, assigning 0 for left and 1 for right: A: 10100 B: 10101 C: 1011 D: 100 E: 00 F: 01 G: 11

Summary

The Greedy Method is an algorithmic paradigm that makes a locally optimal choice at each stage with the hope of finding a globally optimal solution.
Problems suitable for greedy algorithms often exhibit the Greedy Choice Property and Optimal Substructure.
In Machine Scheduling, tasks are sorted by start times and assigned to the earliest available machine (old or new) to minimize the number of machines.
The Fractional Knapsack Problem is solved by sorting items by their profit-to-weight ratio and taking items (or fractions) with the highest ratios until the knapsack is full.
Job Sequencing with Deadline maximizes profit by sorting jobs by profit (descending) and scheduling them in the latest possible available time slot before their deadline.
Optimal Storage on Tapes minimizes Mean Retrieval Time (MRT) by storing programs in non-decreasing order of their lengths.
Optimal Merge Pattern minimizes comparisons by repeatedly merging the two smallest available files.
Huffman Codes construct optimal prefix codes by greedily combining the two nodes with the smallest frequencies to build a binary tree.

Assessed progress

Greedy Method: General Principles and Machine Scheduling

Greedy Method: General Principles and Machine Scheduling

1. The General Method

2. Machine Scheduling Problem

3. Fractional Knapsack Problem

4. Job Sequencing with Deadline

5. Optimal Storage on Tapes

6. Optimal Merge Pattern

7. Huffman Codes

Summary

Key Concepts

Greedy Choice Property

Optimal Substructure

Feasible Solution

Optimal Solution

Machine Scheduling (Greedy)

Quick Check

Advanced Data Structures

Advanced Data Structures