Marek ChrobakUniversity of California, RiversideMinimum Energy SchedulingHow to Keep Sheep Warm in a Snow Storm?• n sheep on a line huddle together to stay warm• Each sheep is chained• Objective: group sheep to minimize # of gapsABCDFGHHow to Keep Sheep Warm in a Snow Storm? ACBDFGHEE• n sheep on a line huddle together to stay warm• Each sheep is chained• Objective: group sheep to minimize # of gapsABCDFGHHow to Keep Sheep Warm in a Snow Storm? ACBDFGHEE• n sheep on a line huddle together to stay warm• Each sheep is chained• Objective: group sheep to minimize # of gapsABCDFGHHow to Keep Sheep Warm in a Snow Storm? ACBDFGHEE• n sheep on a line huddle together to stay warm• Each sheep is chained• Objective: group sheep to minimize # of gapsABCDFGHHow to Keep Sheep Warm in a Snow Storm? ACBDFGHEE• n sheep on a line huddle together to stay warm• Each sheep is chained• Objective: group sheep to minimize # of gapsABCDFGHHow to Keep Sheep Warm in a Snow Storm? ACBDFGHEE• n sheep on a line huddle together to stay warm• Each sheep is chained• Objective: group sheep to minimize # of gapsABCDFGHHow to Keep Sheep Warm in a Snow Storm? ACBDFGHEEpartial grouping 1partial grouping 23Intuition -- why naive algorithms can’t work ...How to Keep Sheep Warm in a Snow Storm?partial grouping 1partial grouping 23Intuition -- why naive algorithms can’t work ...How to Keep Sheep Warm in a Snow Storm? grouping 1 is better, so far ...partial grouping 1partial grouping 23Intuition -- why naive algorithms can’t work ...How to Keep Sheep Warm in a Snow Storm? grouping 1 is better, so far ...partial grouping 1partial grouping 23Intuition -- why naive algorithms can’t work ...How to Keep Sheep Warm in a Snow Storm? grouping 1 is better, so far ...partial grouping 1partial grouping 23Intuition -- why naive algorithms can’t work ...How to Keep Sheep Warm in a Snow Storm? grouping 1 is better, so far ...but only grouping 2 could be extensible to global optimumtradeoff: # gaps vs gap sizes•[aj,bj] = range of sheep j•assume b1 ≤ b2 ≤ ... ≤ bn•a gap with respect to interval [u,v]:-internal gap or-initial gap or-final gap u v3 gaps w.r.t. [u,v]How to Keep Sheep Warm in a Snow Storm?GapsF(u,v) =ABCDEFGuvHow to Keep Sheep Warm in a Snow Storm? Instk(u,v) = all sheep j ∊ {1,2,...,k} for which aj ∈ [u,v]Gapsk(u,v) = min. number of gaps of Instk(u,v) w.r.t [u,v] AC BDE F G?GapsF(u,v) =ABCDEFGuvHow to Keep Sheep Warm in a Snow Storm? Instk(u,v) = all sheep j ∊ {1,2,...,k} for which aj ∈ [u,v]Gapsk(u,v) = min. number of gaps of Instk(u,v) w.r.t [u,v] AC BDE F?GapsF(u,v) =ABCDEFGuvHow to Keep Sheep Warm in a Snow Storm? Instk(u,v) = all sheep j ∊ {1,2,...,k} for which aj ∈ [u,v]Gapsk(u,v) = min. number of gaps of Instk(u,v) w.r.t [u,v] C BDE F?GapsF(u,v) =ABCDEFGuvHow to Keep Sheep Warm in a Snow Storm? Instk(u,v) = all sheep j ∊ {1,2,...,k} for which aj ∈ [u,v]Gapsk(u,v) = min. number of gaps of Instk(u,v) w.r.t [u,v] BDE F?GapsF(u,v) =ABCDEFGuvHow to Keep Sheep Warm in a Snow Storm? Instk(u,v) = all sheep j ∊ {1,2,...,k} for which aj ∈ [u,v]Gapsk(u,v) = min. number of gaps of Instk(u,v) w.r.t [u,v] BDE F?GapsF(u,v) =ABCDEFGuvHow to Keep Sheep Warm in a Snow Storm? Instk(u,v) = all sheep j ∊ {1,2,...,k} for which aj ∈ [u,v]Gapsk(u,v) = min. number of gaps of Instk(u,v) w.r.t [u,v] BDEF1Recurrence for Gapsk(u,v)How to Keep Sheep Warm in a Snow Storm?Recurrence for Gapsk(u,v)Case 1: ak ∉ [u,v]. Then k ∉ Instk(u,v), soGapsk(u,v) = Gapsk-1(u,v)How to Keep Sheep Warm in a Snow Storm?Recurrence for Gapsk(u,v)Case 1: ak ∉ [u,v]. Then k ∉ Instk(u,v), soGapsk(u,v) = Gapsk-1(u,v)Case 2: ak ∈ [u,v], so k ∈ Instk(u,v). If k is scheduled at time t then Instk(u,v) = {k} ∪ Instk-1(u,t) ∪ Instk-1(t+1,v)How to Keep Sheep Warm in a Snow Storm?Recurrence for Gapsk(u,v)Case 1: ak ∉ [u,v]. Then k ∉ Instk(u,v), soGapsk(u,v) = Gapsk-1(u,v)Case 2: ak ∈ [u,v], so k ∈ Instk(u,v). If k is scheduled at time t then Instk(u,v) = {k} ∪ Instk-1(u,t) ∪ Instk-1(t+1,v)How to Keep Sheep Warm in a Snow Storm? Philippe’s Partition Principle: Wlog grouping looks like this:ku vtInstk-1(u,t) = Instk-1(u,t-1)Instk-1(t+1,v) (in particular, no ri at t, i ≠ k)Case 2: ak ∈ [u,v], proof of PPP.Fix an optimal grouping with maximum t (position of k)How to Keep Sheep Warm in a Snow Storm?Case 2: ak ∈ [u,v], proof of PPP.jku vkjtIf j ∈ Instk-1(t+1,v):Fix an optimal grouping with maximum t (position of k)How to Keep Sheep Warm in a Snow Storm?Case 2: ak ∈ [u,v], proof of PPP.jku vkjtIf j ∈ Instk-1(t+1,v):Fix an optimal grouping with maximum t (position of k)jkIf j ∈ Instk-1(u,t): u vkjtHow to Keep Sheep Warm in a Snow Storm?Case 2: ak ∈ [u,v], proof of PPP.jku vkjtIf j ∈ Instk-1(t+1,v):Fix an optimal grouping with maximum t (position of k)jkIf j ∈ Instk-1(u,t): u vkjtHow to Keep Sheep Warm in a Snow Storm?jku vkjtIf j ∈ Instk-1(t+1,v):jkIf j ∈ Instk-1(u,t-1): u vkjtHow to Keep Sheep Warm in a Snow Storm? Fix an optimal grouping with maximum t (position of k)Case 2: ak ∈ [u,v], proof of PPP.jku vkjtIf j ∈ Instk-1(t+1,v):jkIf j ∈ Instk-1(u,t-1): u vkjtHow to Keep Sheep Warm in a Snow Storm? Fix an optimal grouping with maximum t (position of k)Case 2: ak ∈ [u,v], proof of PPP.How to Keep Sheep Warm in a Snow Storm? ku vtInstk-1(u,t) = Instk-1(u,t-1)Instk-1(t+1,v)Philippe’s Partition Principle: Wlog grouping looks like this:Recurrence for Gapsk(u,v)Case 1: ak ∉ [u,v]. Then k ∉ Instk(u,v), soGapsk(u,v) = Gapsk-1(u,v)Case 2: ak ∈ [u,v], so k ∈ Instk(u,v). If k is scheduled at time t then Instk(u,v) = {k} ∪ Instk-1(u,t) ∪ Instk-1(t+1,v)So Gapsk(u,v) = Gapsk-1(u,t-1) + Gapsk-1(t+1,v) How to Keep Sheep Warm in a Snow Storm? ku vtInstk-1(u,t) = Instk-1(u,t-1)Instk-1(t+1,v)Philippe’s Partition Principle: Wlog grouping looks like this:Recurrence for Gapsk(u,v)Case 1: ak ∉ [u,v]. Then k ∉ Instk(u,v), soGapsk(u,v) = Gapsk-1(u,v)Case 2: ak ∈ [u,v], so k ∈ Instk(u,v). If k is scheduled at time t then Instk(u,v) = {k} ∪ Instk-1(u,t) ∪ Instk-1(t+1,v)So Gapsk(u,v) = Gapsk-1(u,t-1) + Gapsk-1(t+1,v) How to Keep Sheep Warm in a Snow Storm? ku vtInstk-1(u,t) = Instk-1(u,t-1)Instk-1(t+1,v)Philippe’s Partition Principle: Wlog grouping looks like this:Recurrence for Gapsk(u,v)Case 1: ak ∉ [u,v]. Then k ∉ Instk(u,v), soGapsk(u,v) = Gapsk-1(u,v)Case 2: ak ∈ [u,v], so k ∈ Instk(u,v). If k is scheduled at