Greedy Algorithm

Digest from Algorithm Design

‣ Interval Scheduling

Given many small intervals and a bigger interval. To fit the most smaller intervals possible into the bigger intervals.

• Consider jobs in ascending order of starting time.

  Not working! Counter example:

  The longger: A = {10, 20}
  The shorter: {a : {10, 20}, b : {11,12}, c : {13,14}}
  
  Expect:  {a : {11,12}, c : {13,14}} 
  Because a and c are not in confict
  
  Algorithm Output:
  
  1. Sort by the processing time:
      {a : {10, 20}, b : {11,12}, c : {13,14}}
  2. Consider these sorted intervals one by one
      {a: {10, 20}} takes the whole duration of A
      so output a
  3. Output != Expect
  
  4. Greedy algorithm by ascending order of starting time not working

• Consider jobs in ascending order of duration.

  Not working! Counter example:

  The longger:  A = {10, 20}
  The shorter:  {a : {10, 14}, b : {13, 15}, c : {14, 20}}
  The duration: {a : 4, b : 2, c : 6}
  
  
  Expect:  {a : {10,14}, c : {14,20}} 
  Because a and c are not in confict
  
  Algorithm Output:
  
  1. Sort by duration:
      {b : {13, 15}, a : {10, 14}, c : {14, 20}}
  2. Consider these sorted intervals one by one
      {b: {13, 15}} will be scheduled and all the other two have conflicts
      so output b
  3. Output != Expect
  
  4. Greedy algorithm by ascending order of duration not working

• Consider jobs in ascending order of ending time.

‣ Interval Partitioning

Given many small intervals and some classrooms. To fit all smaller intervals into the classrooms without conflicts such that the number of classrooms should be the minimum possible.

• Consider jobs in ascending order of starting time.

• Consider jobs in ascending order of duration.

  Not working! Counter example:

  The shorter:  {a : {10, 14}, b : {14, 16}, c : {19, 20}}
  The duration: {a : 4, b : 2, c : 1}
  
  
  Expect: 1, {a : {10, 14}, b : {14, 16}, c : {19, 20}}
  Because they are all compatible 
  
  Algorithm Output:
  
  1. Sort by duration:
      {c : {19, 20}, b : {14, 16},  a : {10, 14}}
  2. Consider these sorted intervals one by one
      1, {c : {19, 20}} 
      2, {b : {14, 16}}
      3, {a : {10, 14}}
      Three classroom will be scheduled 
  3. Output != Expect
  
  4. Greedy algorithm by ascending order of duration not working

• Consider jobs in ascending order of finish time.

  Not working! Counter example:

  
  The shorter:  {a:{10, 12}, b:{10, 14}, c:{13, 20}, d: {15, 19}}
  
  
  
  Expect:  1, {a : {10,12}, c : {13,20}} 
           2, {b : {10,14}, d : {15,19}}
  So 2 classrooms should be scheduled
  
  Algorithm Output:
  
  1. Sort by finish time:
      {a:{10, 12}, b:{10, 14}, d: {15, 19}, c:{13, 20}}
  2. Consider these sorted intervals one by one
      1, {a:{10, 12}, d: {15, 19}}
      2, {b:{10, 14}, }
      3, {c:{13, 20}}
      
      Three classroom will be scheduled 
  3. Output != Expect
  
  4. Greedy algorithm by ascending order of finish time not working

‣ Scheduling to minimize lateness

Given many small intervals and some classrooms. To fit all smaller intervals into the classrooms without conflicts such that the number of classrooms should be the minimum possible.

• Consider jobs in ascending order of processing time.

  Not working! Counter example:

      
    job:  1    2
      t:  1    10
      d:  20   10
      
  Expect:  {job2, job1}
           {0-10, 10-11}  
  lateness:{  0,  0 }
  Max :     0
  
  
  
  Algorithm Output:
  
  1. Sort by the processing time:
      {job1, job2}
  2. Consider these sorted intervals one by one
  
           {0-1, 1-11}  
  lateness:{  0,  1 }
  Max :     1
  Output :  1
  
  3. Output != Expect
  
  4. Greedy algorithm by ascending order of duration not working     
      

• Consider jobs in ascending order of slackness by $d_j - t_j$.

  Not working! Counter example:

    job:  1    2
      t:  1    10
      d:  3    10
      
  Expect:  {job1, job2}
           {0-1, 1-11}  
  lateness:{  0,  1 }
  Max :     1
  
  
  
  Algorithm Output:
  
  1. Sort by the slackness:
  
      {job2(0), job1(2)}
      10 - 10 ,  3 - 1   
  2. Consider these sorted intervals one by one
  
           {0 - 10, 10-11}  
  lateness:{  0,  8 (11 - 3) }
  Max :     8
  Output :  8
  
  3. Output != Expect
  
  4. Greedy algorithm by ascending order of slackness not working 

• Consider jobs in ascending order of finish time.

Inversions

‣Overview

ref: https://ocw.tudelft.nl/wp-content/uploads/Algoritmiek_Greedy_Analysis_Strategies.pdf