Four Representative Algorithms Deterministic Algorithms Greedy [soDa 19911 Permutation [sODa 1991] o Randomized algorithms HST-Greedy [sODa 2006 HST-Reassignment [ESA 2007]
Four Representative Algorithms 17 ⚫ Deterministic Algorithms ⚫ Greedy [SODA 1991] ⚫ Permutation [SODA 1991] ⚫ Randomized Algorithms ⚫ HST-Greedy [SODA 2006] ⚫ HST-Reassignment [ESA 2007]
18 Greedy Basic idea Match the nearest neighbor of the new task
Greedy 18 ⚫ Basic idea ⚫ Match the nearest neighbor of the new task
Greedy Basic idea Match the nearest neighbor of the new task W4(5,5) W3(3,4) W2(2,3) 3 2345X
𝑤1 𝑤2 𝑤3 𝑡1 𝑤4 Greedy t1（1，2） w2（2，3） w3（3，4） w1（3，0） w4（5，5） 5 4 3 2 1 1 2 3 4 5 Y X ⚫ Basic idea ⚫ Match the nearest neighbor of the new task