♦❢ q✉❡r✐❡s ❝♦♥str❛✐♥❡❞ ❜② ❛ st♦r❛❣❡ s♣❛❝❡ ❝❛♣❛❝✐t② ❛♥❞ ♠❛✐♥t❡♥❛♥❝❡ ❝♦sts t♦ ❦❡❡♣ t❤❡ ♠❛t❡r✐❛•✐③❡❞ ✈✐❡✇s ✐♥ s②♥❝❤r♦♥✐③❛t✐♦♥ ✇✐t❤ t❤❡ ✉♥❞❡r•②✐♥❣ ❜❛s❡ r❡•❛t✐♦♥s✳ ▼♦r❡ ♣r❡❝✐s❡•②✱ t❤❡ ✈✐❡✇ s❡•❡❝t✐♦♥ ♣r♦❜•❡♠ ❝❛♥ ❜❡ ❞❡✜♥❡❞ ❛s ❢♦••♦✇s✿ •✐✈❡♥ ❛ q✉❡r② ✇♦r❦•♦❛❞ Q = {q 1 , q 2 , ..., q q } ❛♥❞ t❤❡✐r q✉❡r② ❢r❡q✉❡♥❝② f Q = {f q1 , f q2 , ..., f qq } ♦✈❡r ❛ ❣✐✈❡♥ ❞❛t❛❜❛s❡ ✭♦r ❞❛t❛ ✇❛r❡❤♦✉s❡✮ s❝❤❡♠❛ R = {r 1 , r 2 , ..., r r }✱ ❛ s❡t ♦❢ ✉♣❞❛t❡s U = {u 1 , u 2 , ..., u u } ♦♥ ❜❛s❡ r❡•❛t✐♦♥s ❛♥❞ t❤❡✐r ✉♣❞❛t❡ ❢r❡q✉❡♥❝② f U = {f u r1 , f u r2 , ..., f u rr } ❛♥❞ ❛ •✐♠✐t❡❞ ❛♠♦✉♥t ♦❢ r❡s♦✉r❝❡✱ ❡✳❣✳✱ st♦r❛❣❡ s♣❛❝❡

Sp max ❛♥❞ ✈✐❡✇ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st •✐♠✐t U max ✱ t❤❡ ♣r♦❜•❡♠ ✐s t♦ ✜♥❞ ❛ s❡t ♦❢ ✈✐❡✇s t♦ ♠❛t❡r✐❛•✐③❡ M V = {v 1 , v 2 , ..., v v } s✉❝❤ ❛s t❤❡ ❝♦st ♦❢ ❡✈❛•✉❛t✐♥❣ t❤❡ q✉❡r② ✇♦r❦•♦❛❞ ✐s ♠✐♥✐♠❛•✳ ❈♦st ▼♦❞❡• ❚❤❡ ❝♦st ♠♦❞❡• ❛ss✐❣♥s ❛♥ ❡st✐♠❛t❡❞ ❝♦st ❡✳❣✳✱ q✉❡r② ❝♦st ♦r ♠❛✐♥t❡♥❛♥❝❡ ❝♦st t♦ ❛♥② ✈✐❡✇ ✭♦r q✉❡r②✮ ✐♥ t❤❡ s❡❛r❝❤ s♣❛❝❡✳ ■♥ ♦✉r ❛♣♣r♦❛❝❤✱ ✇❡ ✉s❡ ❛ ❝♦st ♠♦❞❡• s✐♠✐•❛r t♦ ❬✻✱✷✵(✳ ❍❡♥❝❡✱ t❤❡ q✉❡r② ❛♥❞ ✈✐❡✇ ♠❛✐♥t❡♥❛♥❝❡ ❝♦sts ❛r❡ ❡st✐♠❛t❡❞ ✇✐t❤ r❡s♣❡❝t t♦ ❈P❯ ❛♥❞ ■❖ ❝♦sts✳ ■♥ t❤✐s ♣❛♣❡r ✇❡ ❝♦♥s✐❞❡r s❡•❡❝t✐♦♥✲♣r♦•❡❝t✐♦♥✲•♦✐♥ ✭❙P❏✮ q✉❡r✐❡s t❤❛t ♠❛② ✐♥✈♦•✈❡ ❛❣❣r❡❣❛t✐♦♥ ❛♥❞ ❛ ❣r♦✉♣ ❜② ❝•❛✉s❡ ❛s ✇❡••✳ ❚❤❡ ❢♦r♠✉•❛s ✉s❡❞ ❢♦r ❝♦st ♦♣❡r❛t✐♦♥s ❡st✐♠❛t✐♦♥ ❛r❡ ❣✐✈❡♥ ❜❡•♦✇ ✇✐t❤ t❤❡ ❢♦••♦✇✐♥❣ ❛ss✉♠♣t✐♦♥s✿ ✕ ❋♦r♠✉•❛s t♦ ❡st✐♠❛t❡ t❤❡ ❝♦st ♦❢ ❡①❡❝✉t✐♥❣ ❡✈❡r② r❡•❛t✐♦♥❛• ♦♣❡r❛t✐♦♥ t❛❦❡ ✐♥t♦ ❛❝❝♦✉♥t ✐ts ✐♠♣•❡♠❡♥t❛t✐♦♥✱ ❡✳❣✳✱ ✇❡ ❝♦♥s✐❞❡r s❡q✉❡♥t✐❛• s❝❛♥s ❛♥❞ ♥❡st❡❞ •♦♦♣ •♦✐♥s✳ ✕ ❚❤❡ ❈P❯ ❝♦
•② t❤❡ ♥✉♠❜❡r ♦❢ t✉♣•❡s ♦❢ t❤❡ •❡❢t ❛♥❞ r✐❣❤t ♦♣❡r❛♥❞s ✭t❤❡ s❛♠❡ ❢♦r llength ❛♥❞ rlength✮✳ ❋✐❣✳ ✶✿ ❙❡❛r❝❤ tr❡❡ ✉s✐♥❣ ❝♦♥str❛✐♥t ♣r♦♣❛❣❛t✐♦♥ ✸✳✷ ❈♦♥str❛✐♥t Pr♦❣r❛♠♠✐♥❣ ◆♦t✐♦♥s ❈♦♥str❛✐♥t ♣r♦❣r❛♠♠✐♥❣ ❤❛s ❜❡❡♥ s✉❝❝❡ss❢✉••② ❛♣♣•✐❡❞ ✐♥ ♥✉♠❡r♦✉s ❝♦♠❜✐♥❛✲ t♦r✐❛• s❡❛r❝❤ ♣r♦❜•❡♠s ❬✷✻( s✉❝❤ ❛s s❝❤❡❞✉•✐♥❣ ❛♥❞ t✐♠❡t❛❜•✐♥❣✳ ❈♦♥str❛✐♥t ♣r♦✲ ❣r❛♠♠✐♥❣ ❛••♦✇s t♦ s♦•✈❡ ❝♦♠❜✐♥❛t♦r✐❛• ♣r♦❜•❡♠s ♠♦❞❡•❡❞ ❛s ❛ ❈♦♥str❛✐♥t ❙❛t✐s✲ ❢❛❝t✐♦♥ Pr♦❜•❡♠ ✭❈❙P✮✳ ■♥❞❡❡❞✱ t❤❡ ♣r✐♥❝✐♣•❡ ✐❞❡❛ ♦❢ ❝♦♥str❛✐♥t ♣r♦❣r❛♠♠✐♥❣ ✐s t♦ s♦•✈❡ ♣r♦❜•❡♠s ❜② st❛t✐♥❣ ❝♦♥str❛✐♥ts ✇❤✐❝❤ ♠✉st ❜❡ s❛t✐s✜❡❞ ❜② t❤❡ s♦•✉t✐♦♥✳ ❋♦r♠❛••②✱ ❛ ❈❙P ✐s ❞❡✜♥❡❞ ❜② ❛ tr✐♣•❡t ✭❱❆|❀❉❖▼❀❈❙❚✮✿ ✕ ❱❛r✐❛❜•❡s✳ V AR = {var 1 , var 2 , ..., var n } ✐s t❤❡ s❡t ♦❢ ✈❛r✐❛❜•❡s ♦❢ t❤❡ ♣r♦❜•❡♠✳ ✕ ❉♦♠❛✐♥s✳ DOM = {d var1 , d var2 , ..., d varn } ✐s t❤❡ s❡t ♦❢ ♣♦ss✐❜•❡ ✈❛•✉❡s t❤❛t ❝❛♥ ❜❡ ❛ss✐❣♥❡❞ t♦ ❡❛❝❤ ✈❛r✐❛❜•❡ var i ✳ ✕ ❈♦♥str❛✐♥ts✳ CST = {c 1 , c 2 , ..., c n } ✐s t❤❡ s❡t ♦❢ ❝♦♥str❛✐♥ts t❤❛t ❞❡s❝r✐❜❡s t❤❡ r❡•❛t✐♦♥s❤✐♣ ❜❡t✇❡❡♥ s✉❜s❡ts ♦❢ ✈❛r✐❛❜•❡s✳ ❋♦r♠❛••②✱ ❛ ❝♦♥str❛✐♥t C ijk ❜❡t✇❡❡♥ t❤❡ ✈❛r✐❛❜•❡s var i , var j , var k ✐s ❛♥② s✉❜s❡t ♦❢ t❤❡ ♣♦ss✐❜•❡ ❝♦♠❜✐✲ ♥❛t✐♦♥s ♦❢ ✈❛•✉❡s ♦❢ var i , var j , var k ✱ ✐✳❡✳✱ C ijk ⊂ d vari × d varj × d var k ✳ ❚❤❡ s✉❜s❡t s♣❡❝✐✜❡s t❤❡ ❝♦♠❜✐♥❛t✐♦♥s ♦❢ ✈❛•✉❡s t❤❛t t❤❡ ❝♦♥str❛✐♥t ❛••♦✇s✳ ❆ ❢❡❛s✐❜•❡ s♦•✉t✐♦♥ t♦ ❛ ❈❙P ✐s ❛♥ ❛ss✐❣♥♠❡♥t ♦❢ ❛ ✈❛•✉❡ ❢r♦♠ ✐ts ❞♦♠❛✐♥ t♦ ❡✈❡r② ✈❛r✐❛❜•❡✱ s♦ t❤❛t t❤❡ ❝♦♥str❛✐♥ts ♦♥ t❤❡s❡ ✈❛r✐❛❜•❡s ❛r❡ s❛t✐s✜❡❞✳ ❋♦r ♦♣t✐♠✐③❛t✐♦♥ ♣✉r♣♦s❡ s♦♠❡ ❝♦st ❡①♣r❡ss✐♦♥ ♦♥ t❤❡s❡ ✈❛r✐❛❜•❡s t❛❦❡s ❛ ♠❛①✐♠❛• ♦r ♠✐♥✐♠❛• ✈❛•✉❡✳ ▼♦st ❛•❣♦r✐t❤♠s ❢♦r s♦•✈✐♥❣ ❈❙Ps ✉s✉❛••② ✉s❡ ❝♦♥str❛✐♥t ♣r♦♣❛❣❛t✐♦♥ t♦ r❡✲ ❞✉❝❡ t❤❡ s✐③❡ ♦❢ t❤❡ s❡❛r❝❤ s♣❛❝❡ t♦ ❜❡ ❡①♣•♦r❡❞ ❬✶✺(✳ ❲❤❡♥ ❛ ✈❛•✉❡ ♦❢ ❛ ✈❛r✐❛❜•❡ ✐s ✜①❡❞✱ ❝♦♥str❛✐♥t ♣r♦♣❛❣❛t✐♦♥ ✐s ❛♣♣•✐❡❞ t♦ r❡str✐❝t t❤❡ ❞♦♠❛✐♥s ♦❢ ♦t❤❡r ✈❛r✐❛❜•❡s ✇❤♦s❡ ✈❛•✉❡s ❛r❡ ♥♦t ❝✉rr❡♥t•② ✜①❡❞✳ ❚❤✐s ♠❡❛♥s t❤❛t ✇❤❡♥ ❛ ✈❛•✉❡ ✐s ❛ss✐❣♥❡❞ t♦ t❤❡ ❝✉rr❡♥t ✈❛r✐❛❜•❡✱ ❛♥② ✈❛•✉❡ ✐♥ t❤❡ ❞♦♠❛✐♥ ♦❢ ❛ ❢✉t✉r❡ ✈❛r✐❛❜•❡ ✇❤✐❝❤ ❝♦♥✢✐❝ts ✇✐t❤ t❤✐s ❛ss✐❣♥♠❡♥t ✐s r❡♠♦✈❡❞ ❢r♦♠ t❤❡ ❞♦♠❛✐♥✳ ▲❡t ✉s ♥♦✇ ✐••✉str❛t❡ t❤✐s ✐♥ t❤❡ ❝♦♥t❡①t ♦❢ ✈✐❡✇ s❡•❡❝t✐♦♥ ♣r♦❜•❡♠✳ ❋✐❣✲ ✉r❡ ✶ s❤♦✇s t❤❡ ❞♦♠❛✐♥ r❡❞✉❝t✐♦♥ ♦❢ ❢♦✉r ✈❛r✐❛❜•❡s M at v1 ✱ M at v2 ✱ M at v3 ❛♥❞ M at v4 ✇❤❡r❡ M at vi ❞❡♥♦t❡s ❢♦r ❡❛❝❤ ✈✐❡✇ v i ✐❢ ✐t ❤❛s ❜❡❡♥ ♠❛t❡r✐❛•✐③❡❞ ♦r ❤❛s ♥♦t ❜❡❡♥ ♠❛t❡r✐❛•✐③❡❞✳ ■t ✐s ❛ ❜✐♥❛r② ✈❛r✐❛❜•❡✱ d M atv i ❂④✵✱✶⑥ ✭✵✿ v i ❤❛s ♥♦t ❜❡❡♥ ♠❛t❡r✐❛•✐③❡❞✱ ✶✿ v i ❤❛s ❜❡❡♥ ♠❛t❡r✐❛•✐③❡❞✮✳ ❚❤❡ ♣r♦❜•❡♠ ✐s t♦ s❡•❡❝t ❛ s❡t ♦❢ ✈✐❡✇s t♦ ♠❛t❡r✐❛•✐③❡ s✉❜•❡❝t t♦ ❛ s♣❛❝❡ ❛♥❞ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ❝♦♥str❛✐♥ts✳ ❚❤❡ s♣❛❝❡ ❝♦♥str❛✐♥t ❡♥s✉r❡s t❤❛t t❤❡ t♦t❛• s♣❛❝❡ ♦❝❝✉♣✐❡❞ ❜② t❤❡ ♠❛t❡r✐❛•✲ ✐③❡❞ ✈✐❡✇s ✐s •❡ss t❤❛♥ Sp max ✳ ▲❡t ❛s ❛ss✉♠❡ t❤❛t Sp max ❂✸▼❇✱ size(v 1 )❂✹▼❇✱ size(v 2 )❂✷▼❇✱ size(v 3 )❂✶▼❇ ❛♥❞ size(v 4 )❂✶▼❇❀ ✇❤❡r❡ size(v i ) ✐s t❤❡ s✐③❡ ♦❢ t❤❡ ✈✐❡✇ v i ✳ ❲❤✐•❡✱ t❤❡ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ❝♦♥str❛✐♥t ❣✉❛r❛♥t❡❡s t❤❛t t❤❡ t✐♠❡ t♦ ✉♣❞❛t❡ t❤❡ s❡t ♦❢ ♠❛t❡r✐❛•✐③❡❞ ✈✐❡✇s ✐s •❡ss t❤❛♥ U max ✳ ◆♦t❡ t❤❛t U max = 3sec✱ M c(v 1 )❂✶s❡❝✱ M c(v 2 )❂✷s❡❝✱ M c(v 3 )❂✷s❡❝ ❛♥❞ M c(v 4 )❂✺s❡❝❀ ✇❤❡r❡ M c(v i ) ❞❡✲ ♥♦t❡s t❤❡ ❝♦st ♦❢ ♠❛✐♥t❛✐♥✐♥❣ t❤❡ ✈✐❡✇ v i ✳ ❆t t❤❡ ❜❡❣✐♥♥✐♥❣✱ t❤❡ ✐♥✐t✐❛• ✈❛r✐❛❜•❡ ❞♦♠❛✐♥s✱ d M atv 1 ❂d M atv 2 ❂d M atv 3 ❂d M atv 4 ❂④✵✱✶⑥✱ ❛r❡ r❡♣r❡s❡♥t❡❞ ❜② ❢♦✉r ❝♦•✉♠♥s ♦❢ ✇❤✐t❡ sq✉❛r❡s✳ ❈♦♥s✐❞❡r✐♥❣ t❤❡ s♣❛❝❡ ❛♥❞ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ❝♦♥str❛✐♥ts✱ ✐t ❛♣♣❡❛rs t❤❛t M at v1 ❛♥❞ M at v4 ❝❛♥♥♦t t❛❦❡ t❤❡ ✈❛•✉❡ ✶ ❜❡❝❛✉s❡ ♦t❤❡r✇✐s❡ t❤❡ t♦t❛• s♣❛❝❡ ❛♥❞ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ♦❢ t❤❡ ♠❛✲ t❡r✐❛•✐③❡❞ ✈✐❡✇s ✇✐•• ❜❡ r❡s♣❡❝t✐✈❡•② ❣r❡❛t❡r t❤❛♥ Sp max ❛♥❞ U max ✳ ■♥ t❤❡ st❛❣❡ ✭✶✮✱ red M atv 1 size(v1)>Spmax ❛♥❞ red M atv 4 M c(v4)>Umax ✜•t❡rs r❡s♣❡❝t✐✈❡•② t❤❡ ✐♥❝♦♥s✐st❡♥t ✈❛•✉❡ ✶ ❢r♦♠ d M atv 1 ❛♥❞ d M atv 4 ✳ ❚❤❡ ❞❡•❡t❡❞ ✈❛•✉❡s ❛r❡ ♠❛r❦❡❞ ✇✐t❤ ❛ ❜•❛❝❦ sq✉❛r❡✳ ❆❢t❡r t❤✐s st❛❣❡ s♦♠❡ ✈❛r✐❛❜•❡ ❞♦♠❛✐♥s ❛r❡ ♥♦t r❡❞✉❝❡❞ t♦ s✐♥❣•❡t♦♥s✱ t❤❡ ❝♦♥str❛✐♥t s♦•✈❡r t❛❦❡s ♦♥❡ ♦❢ t❤❡s❡ ✈❛r✐❛❜•❡s ❛♥❞ tr✐❡s t♦ ❛ss✐❣♥ t♦ ✐t ❡❛❝❤ ♦❢ t❤❡ ♣♦ss✐❜•❡ ✈❛•✉❡s ✐♥ t✉r♥✳ ❋♦r ❡①❛♠♣•❡✱ ✐❢ t❤❡ s♦•✈❡r s❡•❡❝ts t❤❡ ✈✐❡✇ v 2 t♦ ❜❡ ♠❛t❡r✐❛•✐③❡❞ ✭Mat v2 = 1✱ s❡❡ st❛❣❡ ✭✷✮✮✱ red M atv 3 M c(v2)+M c(v3)>Umax ❡•✐♠✐♥❛t❡s t❤❡ ✈❛•✉❡ ✶ ❢r♦♠ d M atv 3 ✳ ❖t❤❡r✇✐s❡✱ ✐❢ t❤❡ ✈✐❡✇ v 3 ✐s s❡•❡❝t❡❞ t♦ ❜❡ ♠❛t❡r✐❛•✐③❡❞ ✭Mat v3 = 1✱ s❡❡ st❛❣❡ ✭✸✮✮✱ red M atv 2 M c(v2)+M c(v3)>Umax ✇✐t❤❞r❛✇s t❤❡ ✈❛•✉❡ ✶ ❢r♦♠ d M atv 2 ✳ ❚❤✐s ❡♥✉♠❡r❛t✐♦♥ st❛❣❡ •❡❛❞s ✐♥ ♦✉r ❡①❛♠♣•❡ t♦ t✇♦ s♦•✉t✐♦♥s✳ ❚❤❡s❡ s♦•✉t✐♦♥s ❛r❡ ♦❢ ✈❛r✐♦✉s q✉❛•✐t② ♦r ❝♦st✳ ■♥ ❛❞❞✐t✐♦♥ t♦ ♣r♦✈✐❞✐♥❣ ❛ r✐❝❤ ❝♦♥str❛✐♥t •❛♥❣✉❛❣❡ t♦ ♠♦❞❡• ❛ ♣r♦❜•❡♠ ❛s ❛ ❈❙P ❛♥❞ t❡❝❤♥✐q✉❡s s✉❝❤ ❛s ❝♦♥str❛✐♥t ♣r♦♣❛❣❛t✐♦♥ t♦ r❡❞✉❝❡ t❤❡ s❡❛r❝❤ s♣❛❝❡ ❜② ❡①❝•✉❞✐♥❣ s♦•✉t✐♦♥s ✇❤❡r❡ t❤❡ ❝♦♥str❛✐♥ts ❜❡❝♦♠❡ ✐♥❝♦♥s✐st❡♥t✱ ❝♦♥str❛✐♥t ♣r♦✲ ❣r❛♠♠✐♥❣ ♦✛❡rs ❢❛❝✐•✐t✐❡s t♦ ❝♦♥tr♦• t❤❡ s❡❛r❝❤ ❜❡❤❛✈✐♦r✳ ❚❤✐s ♠❡❛♥s t❤❛t s❡❛r❝❤ str❛t❡❣✐❡s ❝❛♥ ❜❡ ❞❡✜♥❡❞ t♦ ❞❡❝✐❞❡ ✐♥ ✇❤✐❝❤ ♦r❞❡r t♦ ❡①♣•♦r❡ t❤❡ ❝r❡❛t❡❞ ❝❤✐•❞ ♥♦❞❡s ✐♥ ❛♥ ❡♥✉♠❡r❛t✐♦♥ tr❡❡ ✇❤✐❝❤ ❝❛♥ s✐❣♥✐✜❝❛♥t•② r❡❞✉❝❡ t❤❡ ❡①❡❝✉t✐♦♥ t✐♠❡✳ ❋✉rt❤❡r♠♦r❡✱ ❝♦♥str❛✐♥t ♣r♦❣r❛♠♠✐♥❣ ♣r♦✈✐❞❡s ✇❛②s t♦ •✐♠✐t t❤❡ tr❡❡ s❡❛r❝❤ r❡✲ ❣❛r❞✐♥❣ ❞✐✛❡r❡♥t ❝r✐t❡r✐❛✳ ❋♦r ✐♥st❛♥❝❡ ♣❡r❢♦r♠✐♥❣ t❤❡ s❡❛r❝❤ ✉♥t✐• r❡❛❝❤✐♥❣ ❛ ❢❡❛s✐❜•❡ s♦•✉t✐♦♥ ✐♥ ✇❤✐❝❤ ❛•• ❝♦♥str❛✐♥ts ❛r❡ s❛t✐s✜❡❞✱ ♦r ✉♥t✐• r❡❛❝❤✐♥❣ ❛ s❡❛r❝❤ t✐♠❡ •✐♠✐t ♦r ✉♥t✐• r❡❛❝❤✐♥❣ t❤❡ ♦♣t✐♠❛• s♦•✉t✐♦♥✳ ✹ ❋r❛♠❡✇♦r❦ ❢♦r ❞❡t❡❝t✐♥❣ ❝♦♠♠♦♥ ✈✐❡✇s ■♥ ♦✉r ❛♣♣r♦❛❝❤✱ t❤❡ t❛s❦ ♦❢ ❛ ✈✐❡✇ s❡•❡❝t✐♦♥ ♠♦❞✉•❡ ✐s t♦ r❡❝♦❣♥✐③❡ ♣♦ss✐❜✐•✐t✐❡s ♦❢ s❤❛r❡❞ ✈✐❡✇s ❛♥❞ t❤❡♥ t♦ ❛♣♣•② ❛ str❛t❡❣② t❤❛t ✉s❡ ❝♦♥str❛✐♥t ♣r♦❣r❛♠♠✐♥❣ ✭❛✮ ❆◆❉ ✈✐❡✇ ❣r❛♣❤ ✭❜✮ ❆◆❉✲❖| ✈✐❡✇ ❣r❛♣❤ ❋✐❣✳ ✷✿ ❉❆• r❡♣r❡s❡♥t❛t✐♦♥ ♦❢ t✇♦ q✉❡r✐❡s q 1 ❛♥❞ q 2 t❡❝❤♥✐q✉❡s ❢♦r ❞❡❝✐❞✐♥❣ ✇❤✐❝❤ ✈✐❡✇s t♦ ♠❛t❡r✐❛•✐③❡✳ ❚❤❡ ✜rst t❛s❦ ✐♥✈♦•✈❡s s❡tt✐♥❣ ✉♣ t❤❡ s❡❛r❝❤ s♣❛❝❡ ❜② ✐❞❡♥t✐❢②✐♥❣ ❝♦♠♠♦♥ s✉❜✲❡①♣r❡ss✐♦♥s ❜❡t✇❡❡♥ t❤❡ ❞✐✛❡r✲ ❡♥t q✉❡r✐❡s ♦❢ ✇♦r❦•♦❛❞✳ ❚❤✐s ❢❡❛t✉r❡ ❝❛♥ ❜❡ ❡①♣•♦✐t❡❞ ❢♦r s❤❛r✐♥❣ ❝♦♠♣✉t❛t✐♦♥✱ ✉♣❞❛t❡s ❛♥❞ st♦r❛❣❡ s♣❛❝❡✳ ❚❤❡ ♠♦st ❝♦♠♠♦♥•② ✉s❡❞ ❢r❛♠❡✇♦r❦s ✐♥ t❤❡ ❝♦♥t❡①t ♦❢ r❡♣r❡s❡♥t✐♥❣ ❙◗▲ q✉❡r✐❡s ✐♥ ♦r❞❡r t♦ ❡①❤✐❜✐t ❝♦♠♠♦♥ s✉❜✲❡①♣r❡ss✐♦♥s ❛r❡ t❤❡ ❆◆❉ ✈✐❡✇ ❣r❛♣❤ ❛♥❞ t❤❡ ❆◆❉✲❖| ✈✐❡✇ ❣r❛♣❤✳ ■♥ ✇❤❛t ❢♦••♦✇s✱ ✇❡ st❛rt ❜② ❣✐✈✐♥❣ ❛ ❢♦r♠❛• ❞❡✜♥✐t✐♦♥ ♦❢ t❤❡s❡ r❡♣r❡s❡♥t❛t✐♦♥s✳ ❉❡✜♥✐t✐♦♥ ✹✳✶ ✭❆◆❉ ❱✐❡✇ •r❛♣❤✮ ❆♥ ❆◆❉ ✈✐❡✇ ❣r❛♣❤ ✐s ❢♦r♠❡❞ ❢r♦♠ t❤❡ ✉♥✐♦♥ ♦❢ ✐♥❞✐✈✐❞✉❛• ❆◆❉✲❉❆• r❡♣r❡s❡♥t❛t✐♦♥s ♦❢ ❡❛❝❤ q✉❡r②✳ ❆♥ ❆◆❉✲❉❆• r❡♣r❡s❡♥t❛t✐♦♥ ❢♦r ❛ q✉❡r② ♦r ❛ ✈✐❡✇ v ✐s ❛ ❞✐r❡❝t❡❞ ❛❝②❝•✐❝ ❣r❛♣❤ ❤❛✈✐♥❣ t❤❡ ❜❛s❡ r❡•❛t✐♦♥s ❛s •❡❛❢ ♥♦❞❡s ❛♥❞ t❤❡ ♥♦❞❡ v ❛s ❛ r♦♦t ♥♦❞❡ ❛♥❞ ❝♦♥s✐sts ♦❢ ❛ s❡t ♦❢ ♦♣❡r❛t✐♦♥ ♥♦❞❡s ✭❖♣✲◆♦❞❡s✮ ❛♥❞ ❡q✉✐✈❛•❡♥❝❡ ♥♦❞❡s ✭❊q✲◆♦❞❡s✮✳ ❚❤❡ ❖♣✲♥♦❞❡s ❤❛✈❡ ♦♥•② ❊q✲♥♦❞❡s ❛s ❝❤✐•❞r❡♥ ❛♥❞ ❊q✲♥♦❞❡s ❤❛✈❡ ♦♥•② ❖♣✲♥♦❞❡s ❛s ❝❤✐•❞r❡♥✳ ❊❛❝❤ ❖♣✲◆♦❞❡ ❝♦rr❡s♣♦♥❞s t♦ ❛♥ ❛•❣❡❜r❛✐❝ ❡①♣r❡ss✐♦♥ ✭❙❡•❡❝t✲Pr♦•❡❝t✲❏♦✐♥✮ ✇✐t❤ ♣♦ss✐❜•❡ ❛❣❣r❡❣❛t❡ ❢✉♥❝t✐♦♥✳ ■t r❡♣r❡s❡♥ts t❤❡ ❡①♣r❡ss✐♦♥ ❞❡✜♥❡❞ ❜② t❤❡ ♦♣❡r❛♥❞ ❛♥❞ ✐ts ✐♥♣✉ts✳ ❆♥ ❊q✲◆♦❞❡ r❡♣r❡s❡♥ts ❛♥ ❡①♣r❡ss✐♦♥ t❤❛t ✐s ❞❡✜♥❡❞ ❜② t❤❡ ❝❤✐•❞ ♦♣❡r❛t✐♦♥ ♥♦❞❡ ❛♥❞ ✐ts ✐♥♣✉ts✳ ❊❛❝❤ ❊q✲◆♦❞❡ r❡♣r❡s❡♥ts ❛ ✈✐❡✇ t❤❛t ❝♦✉•❞ ❜❡ s❡•❡❝t❡❞ ❢♦r ♠❛t❡r✐❛•✐③❛t✐♦♥✳ ■♥ ❛♥ ❆◆❉✲❉❆• r❡♣r❡s❡♥t❛t✐♦♥s✱ ❡❛❝❤ ❖♣✲♥♦❞❡ op i ❤❛s ❛ss♦❝✐❛t❡❞ ✇✐t❤ ✐t ❛♥ ❆◆❉ ❛r❝ ✇❤✐❝❤ ✐s ✐♥❞✐❝❛t❡❞ ❜② ❞r❛✇✐♥❣ ❛ s❡♠✐❝✐r❝•❡✱ t❤r♦✉❣❤ t❤❡ ❡❞❣❡s ✭op i ✱v c1 ✮✱✭ op i ✱v c2 ✮✱✳✳✳✱✭op i ✱v ci ✮✳ ❚❤✐s ❞❡♣❡♥❞❡♥❝❡ ♠❡❛♥s t❤❛t ❛•• t❤❡ ✈✐❡✇s v c1 ✱ v c2 ✱✳✳✳✱v ci t❤❛t ❛r❡ t❤❡ ❝❤✐•❞ ♥♦❞❡s ♦❢ op i ❛r❡ ♥❡❡❞❡❞ t♦ ❝♦♠♣✉t❡ t❤❡ ✈✐❡✇ v p ✇❤✐❝❤ ✐s t❤❡ ♣❛r❡♥t ♥♦❞❡ ♦❢ op i ✳ ❉❡✜♥✐t✐♦♥ ✹✳✷ ✭❆◆❉✲❖| ❱✐❡✇ •r❛♣❤✮ ❆ ❣r❛♣❤ ✐s ❝❛••❡❞ ❛♥ ❆◆❉✲❖| ✈✐❡✇ ❣r❛♣❤ ✐❢ ❢♦r ❡❛❝❤ q✉❡r② ♦r ❛ ✈✐❡✇ v✱ t❤❡r❡ ✐s ❛♥ ❆◆❉✲❖|✲❉❆• r❡♣r❡s❡♥t❛t✐♦♥✳ ❆•• t❤❡ ♣♦ss✐❜•❡ ❆◆❉✲❉❆• r❡♣r❡s❡♥t❛t✐♦♥s ❢♦r v✱ ❞❡s❝r✐❜❡❞ ✐♥ t❤❡ ♣r❡✈✐♦✉s ❞❡✜♥✐t✐♦♥✱ ❜❡❝♦♠❡ t❤❡ ❆◆❉✲❖| ❉❆• ✇❤✐❝❤ ❝♦♥s✐sts ♦❢ ❛•• ♣♦ss✐❜•❡ ❡①❡❝✉t✐♦♥ ♣•❛♥s ❢♦r v✳ ■❢ ❛ ♣❛r❡♥t ✈✐❡✇ v p ❤❛s ♦✉t❣♦✐♥❣ ❡❞❣❡s t♦ ❝❤✐•❞r❡♥ ♦♣❡r❛t✐♦♥ ♥♦❞❡s op 1 ✱op 1 ✱✳✳✳✱op i ✱ t❤❡♥ v p ❝❛♥ ❜❡ ❝♦♠♣✉t❡❞ ❢r♦♠ ❛♥② ♦♥❡ ♦❢ ✐ts ❝❤✐•❞r❡♥✳ ❚❤✐s ❞❡♣❡♥❞❡♥❝❡ ✐s ✐♥❞✐✲ ❝❛t❡❞ ❜② ❞r❛✇✐♥❣ ❛ s❡♠✐❝✐r❝•❡✱ ❝❛••❡❞ ❛♥ ❖| ❛r❝✳ ❚❤❡ ❆◆❉✲❖| ✈✐❡✇ ❣r❛♣❤ ❝❛♥ ❜❡ ❝♦♥str✉❝t❡❞ ❜② ♠❡r❣✐♥❣ t❤❡ ❆◆❉✲❖| ❉❆• ❢♦r ❡❛❝❤ q✉❡r② ✇❤❡r❡ t❤❡ ❝♦♠♠♦♥ s✉❜✲❡①♣r❡ss✐♦♥s ❛r❡ r❡♣r❡s❡♥t❡❞ ♦♥❝❡✳ ❚❤❡ ❉❆• r❡♣r❡s❡♥t❛t✐♦♥ ♦❢ t❤❡ q✉❡r✐❡s q 1 ✿ P ⋊ ⋉ P❙ ⋊ ⋉ ❙ ❛♥❞ q 2 ✿ P❙ ⋊ ⋉ ❙ ⋊ ⋉ ◆✱ ❛r❡ s❤♦✇♥ ✐♥ ✜❣✉r❡ ✷✳ ❚❤❡ s✉❜s❝r✐♣ts P✱ P❙✱ ❙ ❛♥❞ ◆ ❞❡♥♦t❡ r❡s♣❡❝t✐✈❡•② t❤❡ ❜❛s❡ r❡•❛t✐♦♥s ♦❢ ❚P❈✲❍ ❜❡♥❝❤♠❛r❦✿ P❛rt✱ P❛rt❙✉♣♣✱ ❙✉♣♣•✐❡r ❛♥❞ ◆❛t✐♦♥✳ ■♥ t❤❡ ❆◆❉ ✈✐❡✇ ❣r❛♣❤ ✭s❡❡ ✜❣✉r❡ ✷❛✮✱ t❤❡r❡ ✐s ♦♥•② ♦♥❡ ✇❛② t♦ ❛♥s✇❡r ♦r ✉♣❞❛t❡ ❛ ✈✐❡✇ ✭♦r q✉❡r②✮✳ ■♥❞❡❡❞✱ t❤❡ ✈✐❡✇s P✲P❙✲❙ ❛♥❞ P❙✲❙✲◆✱ ❝♦rr❡s♣♦♥❞✐♥❣ r❡s♣❡❝✲ t✐✈❡•② t♦ t❤❡ r❡s✉•t ♦❢ t❤❡ q✉❡r② q 1 ❛♥❞ q 2 ✱ ❝❛♥ ❜❡ ❝♦♠♣✉t❡❞ ♦r ✉♣❞❛t❡❞ ♦♥ ♦♥•② ♦♥❡ ✇❛② ✭✐t ❝♦♥s✐❞❡r ♦♣t✐♠❛• q✉❡r② ♣•❛♥s✮✿ q 1 ✿✭✭P ⋊ ⋉ P❙✮ ⋊ ⋉ ❙✮ q 2 ✿✭✭P❙ ⋊ ⋉ ❙✮ ⋊ ⋉ ◆✮ ❍♦✇❡✈❡r✱ ❛•• ♣♦ss✐❜•❡ ✇❛②s ❢♦r ❡✈❛•✉❛t✐♥❣ t❤❡ q✉❡r✐❡s ❤❛✈❡ ❜❡❡♥ ❝♦♥s✐❞❡r❡❞ ✐♥ t❤❡ ❆◆❉✲❖| ✈✐❡✇ ❣r❛♣❤ ✭s❡❡ ✜❣✉r❡ ✷❜✮✳ ❋♦r s✐♠♣•✐❝✐t②✱ ✇❡ r❡♣r❡s❡♥t ♦♥•② t✇♦ ❡①❡❝✉t✐♦♥ ♣•❛♥s ❢♦r t❤❡ ✈✐❡✇ P✲P❙✲❙ ✇❤✐❝❤ ✐s t❤❡ q✉❡r② r❡s✉•t ♦❢ q 1 ❛♥❞ ♦♥❡ ❡①❡❝✉t✐♦♥ ♣•❛♥ ❢♦r t❤❡ ✈✐❡✇ P❙✲❙✲◆ t❤❛t ✐s t❤❡ q✉❡r② r❡s✉•t ♦❢ q 2 ✿ q 1 ✿④✭✭P ⋊ ⋉ P❙✮ ⋊ ⋉ ❙✮✱ ✭P ⋊ ⋉ ✭P❙ ⋊ ⋉ ❙✮✮⑥ ✴✴ t✇♦ ❡①❡❝✉t✐♦♥ ♣•❛♥s q 2 ✿✭✭P❙ ⋊ ⋉ ❙✮ ⋊ ⋉ ◆✮ ✴✴ ♦♥❡ ❡①❡❝✉t✐♦♥ ♣•❛♥ ❚❤❡ r❡♠❛✐♥✐♥❣ ❡①❡❝✉t✐♦♥ ♣•❛♥s ❛r❡ •✉st ✐♥❞✐❝❛t❡❞ ✐♥ ✜❣✉r❡ ✷❜ ❜② ❞❛s❤❡❞ •✐♥❡s✳ ■♥ t❤✐s ♣❛♣❡r✱ ✇❡ ✉s❡ t❤❡ ❆◆❉✲❖| ✈✐❡✇ ❣r❛♣❤ t♦ ❝♦♠♣❛❝t•② r❡♣r❡s❡♥t ❛•t❡r✲ ♥❛t✐✈❡ q✉❡r② ♣•❛♥s ❛♥❞ ❡①❤✐❜✐t ❝♦♠♠♦♥ s✉❜❡①♣r❡ss✐♦♥✳ ❋♦r ♠♦r❡ ❞❡t❛✐•s ❛❜♦✉t ❝♦♥str✉❝t✐♥❣ t❤❡ ❆◆❉✲❖| ✈✐❡✇ ❣r❛♣❤ ❢♦r t❤❡ q✉❡r✐❡s ♦❢ ✇♦r❦•♦❛❞✱ ✇❡ ♠❛② r❡❢❡r t❤❡ r❡❛❞❡r t♦ ❬✷✽(✳ ❖✉r ♠♦t✐✈❛t✐♦♥ t♦ ✉s❡ t❤❡ ❆◆❉✲❖| r❡♣r❡s❡♥t❛t✐♦♥ r❛t❤❡r t❤❛♥ t❤❡ ❆◆❉ r❡♣r❡s❡♥t❛t✐♦♥ s✐♥❝❡ t❤❡ •❛tt❡r ♠❛❦❡s •♦❝❛• ♦♣t✐♠❛• ❝❤♦✐❝❡s✱ ❛♥❞ ♠❛② ♠✐ss ❣•♦❜❛• ♦♣t✐♠❛• ♣•❛♥s✳ ❚❤❡ ❝❤♦✐❝❡ ♦❢ ♠❛t❡r✐❛•✐③❡❞ ✈✐❡✇s ♠✉st ❜❡ ❞♦♥❡ ✐♥ ❝♦♥•✉♥❝t✐♦♥ ✇✐t❤ ❝❤♦♦s✐♥❣ ❡①❡❝✉t✐♦♥ ♣•❛♥s ❢♦r q✉❡r✐❡s✳ ❋♦r ✐♥st❛♥❝❡✱ ❛ ♣•❛♥ t❤❛t s❡❡♠s q✉✐t❡ ✐♥❡✣❝✐❡♥t ❝♦✉•❞ ❜❡❝♦♠❡ t❤❡ ❜❡st ♣•❛♥ ✐❢ s♦♠❡ ✐♥t❡r♠❡❞✐❛t❡ r❡s✉•t ♦❢ t❤❡ ♣•❛♥ ✐s ❝❤♦s❡♥ t♦ ❜❡ ♠❛t❡r✐❛•✐③❡❞ ❛♥❞ ♠❛✐♥t❛✐♥❡❞ ❛s t❤❡ ❢♦••♦✇✐♥❣ ❡①❛♠♣•❡ ❞❡♠♦♥str❛t❡s ✐t✳ ❊①❛♠♣•❡✳ ▲❡t ✉s ❝♦♥s✐❞❡r t❤❡ ✈✐❡✇s P✲P❙✲❙ ❛♥❞ P❙✲❙✲◆ ✇❤✐❝❤ ❛r❡ r❡s♣❡❝✲ t✐✈❡•② ❝♦♠♣✉t❡❞ ❜② ✉s✐♥❣ t❤❡ ♣•❛♥ ✭✭P ⋊ ⋉ P❙✮ ⋊ ⋉ ❙✮ ❛♥❞ t❤❡ ♣•❛♥ ✭✭P❙ ⋊ ⋉ ❙✮ ⋊ ⋉ ◆✮✱ ❛s ✐t ✐s s❤♦✇♥ ✐♥ ✜❣✉r❡ ✷❛✳ ❚❤❡s❡ ❡①❡❝✉t✐♦♥ ♣•❛♥s r❡♣r❡s❡♥t t❤❡ ♦♣t✐♠❛• ♣•❛♥s ❢♦r q 1 ❛♥❞ q 2 ✳ ❍♦✇❡✈❡r✱ ✐❢ ✇❡ ❝❤♦♦s❡ t❤❡ ❛•t❡r♥❛t✐✈❡ ♣•❛♥ ✭P ⋊ ⋉ ✭P❙ ⋊ ⋉ ❙✮✮ t♦ ❝♦♠♣✉t❡ t❤❡ ✈✐❡✇ P✲P❙✲❙✱ t❤❡ ✈✐❡✇ P❙✲❙ ❜❡❝♦♠❡s ❛ ❝♦♠♠♦♥ s✉❜❡①♣r❡ss✐♦♥ ✭s❡❡ ✜❣✉r❡ ✷❜✮✳ ■t ❝❛♥ ❜❡ ❝♦♠♣✉t❡❞ ♦♥❝❡ ❛♥❞ ✉s❡❞ ❢♦r ❜♦t❤ q✉❡r✐❡s q 1 ❛♥❞ q 2 ✳ ❚❤✐s ❛•t❡r♥❛t✐✈❡ ✇✐t❤ s❤❛r✐♥❣ ♦❢ t❤❡ ✈✐❡✇ P❙✲❙ ♠❛② ❜❡ t❤❡ ❣•♦❜❛• ♦♣t✐♠❛• ❝❤♦✐❝❡✳ ■♥ t❤❡ ❝♦♥t❡①t ♦❢ ✈✐❡✇ ♠❛✐♥t❡♥❛♥❝❡✱ ❝♦♠♠♦♥ s✉❜✲❡①♣r❡ss✐♦♥s ❝❛♥ ❜❡ ❡①♣•♦✐t❡❞ t♦ ✜♥❞ ❛♥ ❡✣❝✐❡♥t ♣•❛♥ ❢♦r ♠❛✐♥t❡♥❛♥❝❡ ♦❢ ❛ s❡t ♦❢ ✈✐❡✇s✳ ■♥❞❡❡❞✱ t❤❡ ✈✐❡✇ P✲P❙✲ ❙ ♠❛② ❛•s♦ ❜❡ ✉s❡❞ ❢♦r s❤❛r✐♥❣ ✉♣❞❛t❡s ❛♥❞ ❤❡♥❝❡ r❡❞✉❝✐♥❣ t❤❡ ✈✐❡✇ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st✳ ◆♦t❡ t❤❛t ✐♥ t❤❡ ❆◆❉✲❖| ✈✐❡✇ ❣r❛♣❤✱ ❡❛❝❤ ❡q✉✐✈❛•❡♥❝❡ ♥♦❞❡✱ ✇❤✐❝❤ r❡♣✲ r❡s❡♥ts ❛ ❝❛♥❞✐❞❛t❡ ✈✐❡✇ v i t♦ ♠❛t❡r✐❛•✐③❛t✐♦♥✱ ❤❛s t❤❡ ❢♦••♦✇✐♥❣ ♣❛r❛♠❡t❡rs ❛ss♦❝✐❛t❡❞ t♦ ✐t✿ ◗✉❡r② ❝♦st Qc ✭t❤❡ ❡✈❛•✉❛t✐♦♥ ❝♦st ♦❢ t❤❡ ❝❤❡❛♣❡st ❡♠❜❡❞❞❡❞ ❡①♣r❡ss✐♦♥ ❆◆❉✲❉❆• ❢♦r v i ✮✱ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st M c ✭t❤❡ ❝♦st r❡q✉✐r❡❞ ❢♦r ✉♣✲ ❞❛t✐♥❣ v i ✇❤❡♥ t❤❡ r❡•❛t❡❞ ❜❛s❡ r❡•❛t✐♦♥s ❛r❡ ❝❤❛♥❣❡❞✮✱ r❡❛❞✐♥❣ ❝♦st Rc✱ q✉❡r② ❢r❡q✉❡♥❝② f q ✭✐❢ t❤❡ ❡q✉✐✈❛•❡♥❝❡ ♥♦❞❡ ✐s ❛ r♦♦t ♥♦❞❡✮ ❛♥❞ t❤❡ ✉♣❞❛t❡ ❢r❡q✉❡♥❝② f u ✭t❤❡ ❢r❡q✉❡♥❝② ♦❢ ✉♣❞❛t✐♥❣ v i ✐♥ r❡s♣♦♥s❡ t♦ ❝❤❛♥❣❡ t♦ t❤❡ ✉♥❞❡r•②✐♥❣ ❞❛t❛✮✳ ❚♦ ❡❛❝❤ ♦♣❡r❛t✐♦♥ ♥♦❞❡ op i ✱ t❤❛t r❡♣r❡s❡♥ts ❛ r❡•❛t✐♦♥❛• ♦♣❡r❛t♦r✱ ❛ ❝♦st ✐s ❛ss♦✲ ❝✐❛t❡❞ ✇✐t❤ ✐t ✇❤✐❝❤ ✐s t❤❡ ❝♦st ✐♥❝✉rr❡❞ ❞✉r✐♥❣ t❤❡ ❝♦♠♣✉t❛t✐♦♥ ♦❢ t❤❡ ♣❛r❡♥t ♥♦❞❡ ♦❢ op i ❢r♦♠ t❤❡ ❝❤✐•❞r❡♥ ♥♦❞❡s ♦❢ op i ✳ ❚❤❡ ✈✐❡✇ s❡•❡❝t✐♦♥ ♣r♦❜•❡♠ ❢♦r ❆◆❉✲❖| ✈✐❡✇ ❣r❛♣❤s ❝❛♥ ❜❡ ❢♦r♠✉•❛t❡❞ ❛s ❢♦••♦✇s✿ •✐✈❡♥ ❛♥ ❆◆❉✲❖| ✈✐❡✇ ❣r❛♣❤ G✱ ❛ ♠❛①✐♠✉♠ st♦r❛❣❡ s♣❛❝❡ Sp max ✭❛✈❛✐•❛❜•❡ s♣❛❝❡✮✱ ❛ t♦t❛• ✈✐❡✇ ♠❛✐♥t❡♥❛♥❝❡ •✐♠✐t U max ✭❛✈❛✐•❛❜•❡ ♠❛✐♥t❡♥❛♥❝❡ t✐♠❡✮✱ t❤❡ ♣r♦❜•❡♠ ✐s t♦ s❡•❡❝t ❛ s❡t ♦❢ ✈✐❡✇s t♦ ❜❡ ♠❛t❡r✐❛•✐③❡❞ M V ✱ ❛ s✉❜s❡t ♦❢ t❤❡ ❡q✉✐✈❛•❡♥❝❡ ♥♦❞❡s ♦❢ G✱ t❤❛t ♠✐♥✐♠✐③❡s t❤❡ t♦t❛• q✉❡r② ❝♦st✱ ✉♥❞❡r t❤❡ ❝♦♥str❛✐♥t t❤❛t t❤❡ t♦t❛• s♣❛❝❡ ♦❝❝✉♣✐❡❞ ❜② M V ✐s •❡ss ♦r ❡q✉❛• t❤❛♥ Sp max ❛♥❞ t❤❡ t♦t❛• ♠❛✐♥t❡♥❛♥❝❡ t✐♠❡ ♦❢ M V ✭✐✳❡✳✱ ✈✐❡✇ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st✮ ✐s •❡ss ♦r ❡q✉❛• t❤❛♥ U max ✳ ✺ ❖✉r ✈✐❡✇ s❡•❡❝t✐♦♥ ❛♣♣r♦❛❝❤ ▲❡t ✉s ♥♦✇ ✐♥tr♦❞✉❝❡ t❤❡ ❝♦♥str❛✐♥t s❛t✐s❢❛❝t✐♦♥ ♠♦❞❡• t❤❛t ✇❡ ❤❛✈❡ ♣r♦♣♦s❡❞ ❢♦r t❤❡ ✈✐❡✇ s❡•❡❝t✐♦♥ ♣r♦❜•❡♠✳ ❲❡ t❤❡♥ ♣r❡s❡♥t t❤❡ s❡❛r❝❤ str❛t❡❣② t❤❛t ✇❡ ❤❛✈❡ ❞❡✜♥❡❞ ✇✐t❤✐♥ t❤❡ ❝♦♥str❛✐♥t s♦•✈❡r ❢♦r ♦♣t✐♠✐③❛t✐♦♥ ♣✉r♣♦s❡✳ ✺✳✶ ▼♦❞❡•✐♥❣ ❱✐❡✇ ❙❡•❡❝t✐♦♥ Pr♦❜•❡♠ ❛s ❛ ❈♦♥str❛✐♥t ❙❛t✐s❢❛❝t✐♦♥ Pr♦❜•❡♠ ✭❈❙P✮ ❚❤✐s s❡❝t✐♦♥ ❞❡s❝r✐❜❡s ❤♦✇ t♦ ♠♦❞❡• t❤❡ ✈✐❡✇ s❡•❡❝t✐♦♥ ♣r♦❜•❡♠ ❛s ❛ ❈❙P✳ ❚❤❡♥✱ ✐ts r❡s♦•✉t✐♦♥ ✐s s✉♣♣♦rt❡❞ ❛✉t♦♠❛t✐❝❛••② ❜② t❤❡ ❝♦♥str❛✐♥t s♦•✈❡r✳ ■♥ t❤❡ ❢♦••♦✇✲ ✐♥❣✱ ✇❡ ❞❡✜♥❡ ❛•• t❤❡ s②♠❜♦•s ❛s ✇❡•• ❛s t❤❡ ✈❛r✐❛❜•❡s t❤❛t ✇❡ ❤❛✈❡ ✉s❡❞ ✐♥ ♦✉r ❝♦♥str❛✐♥t s❛t✐s❢❛❝t✐♦♥ ♠♦❞❡•✳ ✕ G✳ ❚❤❡ ❆◆❉✲❖| ✈✐❡✇ ❣r❛♣❤ ❞❡s❝r✐❜❡❞ ✐♥ t❤❡ ♣r❡✈✐♦✉s s❡❝t✐♦♥✳ ✕ Q(G)✳ ❚❤❡ ✈✐❡✇s ✇❤✐❝❤ ❝♦rr❡s♣♦♥❞ t♦ t❤❡ q✉❡r② r❡s✉•ts ✭t❤❡ r♦♦t ♥♦❞❡s ✐♥ t❤❡ ❆◆❉✲❖| ✈✐❡✇ ❣r❛♣❤ G✮✳ ✕ V (G)✳ ❚❤❡ s❡t ♦❢ ✈✐❡✇s ✐♥ G ✇❤✐❝❤ ❛r❡ ❝❛♥❞✐❞❛t❡ t♦ ♠❛t❡r✐❛•✐③❛t✐♦♥✳ ✕ U (v i )✳ ❚❤❡ s❡t ♦❢ ✉♣❞❛t❡s ♦♥ v i ✐♥ r❡s♣♦♥s❡ t♦ ❝❤❛♥❣❡s ♦❢ t❤❡ ❛ss♦❝✐❛t❡❞ ❜❛s❡ r❡•❛t✐♦♥s✳ ✕ δ(v i , u)✿ ❚❤❡ ❞✐✛❡r❡♥t✐❛• r❡s✉•t ♦❢ ✈✐❡✇ v i ✇✐t❤ r❡s♣❡❝t t♦ ✉♣❞❛t❡ u✳ ✕ f q (v i )✳ ❚❤❡ ❛❝❝❡ss ❢r❡q✉❡♥❝② ♦r ✐♠♣♦rt❛♥❝❡ ♦❢ t❤❡ ❛ss♦❝✐❛t❡❞ ✈✐❡✇ ✭♦r q✉❡r②✮ v i ✳ ✕ f u (v i )✳ ❚❤❡ ❢r❡q✉❡♥❝② ♦❢ ♣r♦♣❛❣❛t✐♥❣ t❤❡ ❝❤❛♥❣❡s ♦❢ ❡❛❝❤ ❛ss♦❝✐❛t❡❞ ❜❛s❡ r❡•❛t✐♦♥ t♦ t❤❡ ✈✐❡✇ v i ✳ ✕ Sp max ✳ ❚❤❡ ♠❛①✐♠✉♠ st♦r❛❣❡ s♣❛❝❡ t❤❛t ❝❛♥ ❜❡ ✉s❡❞ t♦ ✈✐❡✇ ♠❛t❡r✐❛•✐③❛✲ t✐♦♥✳ ✕ U max ✳ ❚❤❡ t✐♠❡ t❤❛t ❝❛♥ ❜❡ ❛••♦tt❡❞ t♦ ❦❡❡♣ ✉♣ t♦ ❞❛t❡ t❤❡ ♠❛t❡r✐❛•✐③❡❞ ✈✐❡✇s✳ ✕ size(v i )✳ ❚❤❡ s✐③❡ ♦❢ t❤❡ ✈✐❡✇ v i ✐♥ t❡r♠s ♦❢ ♥✉♠❜❡r ♦❢ ❜②t❡s✳ ❈❙P ✈❛r✐❛❜•❡s ❛♥❞ t❤❡✐r ❞♦♠❛✐♥s ✕ M at vi ✳ ❚❤❡ ♠❛t❡r✐❛•✐③❛t✐♦♥ ✈❛r✐❛❜•❡ ✇❤✐❝❤ ❞❡♥♦t❡s ❢♦r ❡❛❝❤ ✈✐❡✇ v i ✭❡q✉✐✈✲ ❛•❡♥❝❡ ♥♦❞❡ ✐♥ t❤❡ ❆◆❉✲❖| ✈✐❡✇ ❣r❛♣❤ G✮✱ ✐❢ ✐t ✐s ♠❛t❡r✐❛•✐③❡❞ ♦r ♥♦t ♠❛t❡r✐❛•✐③❡❞✳ ■t ✐s ❛ ❜✐♥❛r② ✈❛r✐❛❜•❡✱ d M atv i ❂④✵✱✶⑥ ✭✵✿ v i ✐s ♥♦t ♠❛t❡r✐❛•✐③❡❞✱ ✶✿ v i ✐s ♠❛t❡r✐❛•✐③❡❞✮✳ ✕ Qc(v i )✳ ❚❤❡ q✉❡r② ❝♦st ❝♦rr❡s♣♦♥❞✐♥❣ t♦ t❤❡ ✈✐❡✇ v i ✳ ❚❤❡ ❞♦♠❛✐♥ ✐s ❛ ✜♥✐t❡ s✉❜s❡t ♦❢ N * s✉❝❤ ❛s d Qc(vi) ⊂ N * ✳ ✕ M c(v i )✳ ❚❤❡ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ❝♦rr❡s♣♦♥❞✐♥❣ t♦ ❛ ✈✐❡✇ v i ✱ ✇❤❡r❡ d Qc(vi) ⊂ N * ✳ ❚❤❡ ✈✐❡✇ s❡•❡❝t✐♦♥ ♣r♦❜•❡♠ ❝❛♥ ❜❡ ❢♦r♠✉•❛t❡❞ ❜② t❤❡ ❢♦••♦✇✐♥❣ ❝♦♥str❛✐♥t s❛t✲ ✐s❢❛❝t✐♦♥ ♠♦❞❡•✳ ■t ❝♦♥s✐sts ✐♥ s♣❡❝✐❢②✐♥❣ ✐♥ ❛ ❞❡❝•❛r❛t✐✈❡ ✇❛② t❤❡ ❈❙P ✈❛r✐❛❜•❡s✱ t❤❡✐r ❞♦♠❛✐♥s✱ ❛♥❞ t❤❡ ❝♦♥str❛✐♥ts t❤❛t ❛r❡ ♦✈❡r t❤❡♠✳ minimize vi∈Q(G) f q (v i ) * Qc(v i ) ✭✶✮ subject to vi∈V (G) M at vi * size(v i ) ≤ Sp max ✭✷✮ vi∈V (G) M at vi * f u (v i ) * M c(v i ) ≤ U max ✭✸✮ ■♥ ♦✉r ❛♣♣r♦❛❝❤✱ t❤❡ ♠❛✐♥ ♦❜•❡❝t✐✈❡ ✐s t❤❡ ♠✐♥✐♠✐③❛t✐♦♥ ♦❢ t❤❡ t♦t❛• q✉❡r② ❝♦st✳ ■t ✐s ❝♦♠♣✉t❡❞ ❜② s✉♠♠✐♥❣ ♦✈❡r t❤❡ ❝♦st ♦❢ ♣r♦❝❡ss✐♥❣ ❡❛❝❤ ✐♥♣✉t q✉❡r② r❡✇r✐tt❡♥ ♦✈❡r t❤❡ ♠❛t❡r✐❛•✐③❡❞ ✈✐❡✇s✳ ❈♦♥str❛✐♥ts ✭✷✮ ❛♥❞ ✭✸✮ st❛t❡ t❤❛t t❤❡ ✈✐❡✇s ❛r❡ s❡•❡❝t❡❞ t♦ ❜❡ ♠❛t❡r✐❛•✐③❡❞ ✉♥❞❡r ❛ •✐♠✐t❡❞ ❛♠♦✉♥t ♦❢ r❡s♦✉r❝❡s✳ ❈♦♥✲ str❛✐♥t ✭✷✮ ❡♥s✉r❡s t❤❛t t❤❡ t♦t❛• s♣❛❝❡ ♦❝❝✉♣✐❡❞ ❜② t❤❡ ♠❛t❡r✐❛•✐③❡❞ ✈✐❡✇s ✐s •❡ss t❤❛♥ ♦r ❡q✉❛• t♦ t❤❡ ♠❛①✐♠✉♠ st♦r❛❣❡ s♣❛❝❡ ❝❛♣❛❝✐t②✳ ❈♦♥str❛✐♥t ✭✸✮ ❣✉❛r❛♥t❡❡s t❤❛t t❤❡ t♦t❛• ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ♦❢ t❤❡ s❡t ♦❢ ♠❛t❡r✐❛•✐③❡❞ ✈✐❡✇s ✐s •❡ss t❤❛♥ ♦r ❡q✉❛• t♦ t❤❡ t♦t❛• ✈✐❡✇ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st •✐♠✐t✳ ❚❤❡ q✉❡r② ❛♥❞ ♠❛✐♥t❡♥❛♥❝❡ ❝♦sts ❝♦rr❡s♣♦♥❞✐♥❣ t♦ ❛ ✈✐❡✇ ❛r❡ ✐♠♣•❡♠❡♥t❡❞ ❜② ✉s✐♥❣ ❛ ❞❡♣t❤✲✜rst tr❛✈❡rs❛• ♦❢ t❤❡ ❆◆❉✲❖| ✈✐❡✇ ❣r❛♣❤✳ ❲❡ ❤❛✈❡ ❜❡❡♥ ✐♥✲ s♣✐r❡❞ ❜② t❤❡ ❢♦r♠✉•❛s ❞❡s❝r✐❜❡❞ ✐♥ ❬✷✹✱✷✽( t♦ ❝♦♠♣✉t❡ t❤❡s❡ t✇♦ ❝♦sts✳ ◆♦t❡ t❤❛t t❤❡ q✉❡r② ❛♥❞ ♠❛✐♥t❡♥❛♥❝❡ ❝♦sts ❝♦rr❡s♣♦♥❞✐♥❣ t♦ ❛ ❜❛s❡ r❡•❛t✐♦♥ ❛r❡ ❡q✉❛• t♦ ③❡r♦✳ ❚❤❡② ♠❛② ❜❡ ❢♦r♠✉•❛t❡❞ ❛s ❢♦••♦✇s✳ ◗✉❡r② ❝♦st Qc(v i ) = CCost(v i ) if M at vi = 0 Rc(v i ) otherwise ✭✹✮ where CCost(v i ) = min opj ∈child(vi) cost(op j ) + v k ∈child(opj ) Qc(v k ) ✭✺✮ ❈♦♥str❛✐♥t ✭✹✮ st❛t❡s t❤❛t t❤❡ q✉❡r② ❝♦st ❝♦rr❡s♣♦♥❞✐♥❣ t♦ ❡❛❝❤ ❣✐✈❡♥ ✈✐❡✇ ✐♥ t❤❡ ❆◆❉✲❖| ✈✐❡✇ ❣r❛♣❤ ✐s t❤❡ ♠✐♥✐♠✉♠ ❝♦st ♣❛t❤s ❢r♦♠ t❤❡ ✈✐❡✇ t♦ ✐ts r❡•❛t❡❞ ❜❛s❡ r❡•❛t✐♦♥s ♦r ✈✐❡✇s✳ ❚❤❡ r❡❛❞✐♥❣ ❝♦st ✐s ❝♦♥s✐❞❡r❡❞ ✐❢ t❤❡ ✈✐❡✇ ❤❛s ❜❡❡♥ ♠❛t❡r✐❛•✐③❡❞✳ ❈♦♥str❛✐♥t ✭✺✮ ❡♥s✉r❡s t❤❛t t❤❡ ♠✐♥✐♠✉♠ ❝♦st ♣❛t❤ ✐s s❡•❡❝t❡❞ ❢♦r ❝♦♠♣✉t✐♥❣ ❛ ❣✐✈❡♥ ✈✐❡✇✳ ❊❛❝❤ ♠✐♥✐♠✉♠ ❝♦st ♣❛t❤ ✐♥❝•✉❞❡s ❛•• t❤❡ ❝♦st ♦❢ ❡①❡❝✉t✐♥❣ t❤❡ ♦♣❡r❛t✐♦♥ ♥♦❞❡s ♦♥ t❤❡ ♣❛t❤ ❛♥❞ t❤❡ q✉❡r② ❝♦st ❝♦rr❡s♣♦♥❞✐♥❣ t♦ t❤❡ r❡•❛t❡❞ ❜❛s❡s r❡•❛t✐♦♥s ♦r ✈✐❡✇s✳ ❱✐❡✇ ♠❛✐♥t❡♥❛♥❝❡ ❈♦st M c(v i ) = 0 if M at vi = 0 u∈U (vi) M cost(v i , u) otherwise ✭✻✮ where M cost(v i , u) = min opj ∈child(vi)
cost(op j , u)

+ v k ∈child(opj ) U Cost(v k , u) ✭✼✮ U Cost(v k , u) = M cost(v k , u) if M at v k = 0 δ(v k , u) otherwise ✭✽✮ ❈♦♥str❛✐♥t ✭✻✮ ❣✉❛r❛♥t❡❡s t❤❛t t❤❡r❡ ✐s ♥♦ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ✐❢ t❤❡ ✈✐❡✇ ❤❛s ♥♦t ❜❡❡♥ ♠❛t❡r✐❛•✐③❡❞✳ ❖t❤❡r✇✐s❡✱ t❤❡ ✈✐❡✇ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ✐s ❝♦♠♣✉t❡❞ ❜② s✉♠♠✐♥❣ t❤❡ ♥✉♠❜❡r ♦❢ ❝❤❛♥❣❡s ✐♥ t❤❡ ❜❛s❡ r❡•❛t✐♦♥s ❢r♦♠ ✇❤✐❝❤ t❤❡ ✈✐❡✇ ✐s ✉♣❞❛t❡❞✳ ❲❡ ❛ss✉♠❡ ✐♥❝r❡♠❡♥t❛• ♠❛✐♥t❡♥❛♥❝❡ t♦ ❡st✐♠❛t❡ t❤❡ ✈✐❡✇ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st✳ ❚❤❡r❡❢♦r❡✱ t❤❡ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ✐s t❤❡ ❞✐✛❡r❡♥t✐❛• r❡s✉•ts ♦❢ ♠❛t❡r✐❛•✐③❡❞ ✈✐❡✇s ❣✐✈❡♥ t❤❡ ❞✐✛❡r❡♥t✐❛• ✭✉♣❞❛t❡s✮ ♦❢ t❤❡ ❜❛s❡s r❡•❛t✐♦♥s✳ ❈♦♥str❛✐♥ts ✭✼✮ ❛♥❞ ✭✽✮ ✐♥s✉r❡ t❤❛t t❤❡ ❜❡st ♣•❛♥ ✇✐t❤ t❤❡ ♠✐♥✐♠✉♠ ❝♦st ✇✐•• ❜❡ s❡•❡❝t❡❞ t♦ ♠❛✐♥t❛✐♥ ❛ ✈✐❡✇✳ ❚❤❡ ✈✐❡✇ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ✐s ❝♦♠♣✉t❡❞ s✐♠✐•❛r•② t♦ t❤❡ q✉❡r② ❝♦st✱ ❜✉t t❤❡ ❝♦st ♦❢ ❡❛❝❤ ♠✐♥✐♠✉♠ ♣❛t❤ ✐s ❝♦♠♣♦s❡❞ ♦❢ ❛•• t❤❡ ❝♦st ♦❢ ❡①❡❝✉t✐♥❣ t❤❡ ♦♣❡r❛t✐♦♥ ♥♦❞❡s ✇✐t❤ r❡s♣❡❝t t♦ t❤❡ ✉♣❞❛t❡s ♦♥ t❤❡ ♣❛t❤ ❛♥❞ t❤❡ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ❝♦rr❡s♣♦♥❞✐♥❣ t♦ t❤❡ r❡•❛t❡❞ ❜❛s❡ r❡•❛t✐♦♥s ♦r ✈✐❡✇s✳ ✺✳✷ ❙❡❛r❝❤ str❛t❡❣② ❆ ❦❡② ✐♥❣r❡❞✐❡♥t ♦❢ ❛♥② ❝♦♥str❛✐♥t s❛t✐s❢❛❝t✐♦♥ ❛♣♣r♦❛❝❤ ✐s ❛♥ ❡✣❝✐❡♥t s❡❛r❝❤ str❛t❡❣②✳ ❆s ♠❡♥t✐♦♥❡❞ ✐♥ ❙❡❝t✐♦♥ ✸✳✷✱ t❤❡ s❡❛r❝❤ ✐s ♦r❣❛♥✐③❡❞ ❛s ❛♥ ❡♥✉♠❡r❛✲ t✐♦♥ tr❡❡✱ ✇❤❡r❡ ❡❛❝❤ ♥♦❞❡ ❝♦rr❡s♣♦♥❞s t♦ ❛ s✉❜s♣❛❝❡ ♦❢ t❤❡ s❡❛r❝❤✳ ❚❤❡ tr❡❡ ✐s ♣r♦❣r❡ss✐✈❡•② ❝♦♥str✉❝t❡❞ ❜② ❛♣♣•②✐♥❣ s❡r✐❡s ♦❢ ❜r❛♥❝❤✐♥❣ str❛t❡❣✐❡s t❤❛t ❞❡✜♥❡ t❤❡ ✇❛② t♦ ❜r❛♥❝❤ ❢r♦♠ ❛ tr❡❡ s❡❛r❝❤ ♥♦❞❡✳ ■♥ t❤❡ ❝♦♥str❛✐♥t s♦•✈❡r✱ ❜r❛♥❝❤✐♥❣ ❤❛s ❜❡❡♥ ❛♣♣•✐❡❞ t♦ ❞❡❝✐s✐♦♥ ✈❛r✐❛❜•❡s✳ ■♥ ♦✉r ❝♦♥str❛✐♥t s❛t✐s❢❛❝t✐♦♥ ♠♦❞❡•✱ t❤❡ ♠❛t❡r✐❛•✐③❛t✐♦♥ ✈❛r✐❛❜•❡ M at vi ✐s t❤❡ ❞❡❝✐s✐♦♥ ✈❛r✐❛❜•❡ s✐♥❝❡ t❤❡ ❛✐♠ ♦❢ t❤❡ ✈✐❡✇ s❡•❡❝t✐♦♥ ♣r♦❜•❡♠ ✐s t♦ ❞❡❝✐❞❡ ✇❤✐❝❤ ✈✐❡✇s t♦ ♠❛t❡r✐❛•✐③❡✳ ❚❤❡ ♠♦st ❝♦♠♠♦♥ ❜r❛♥❝❤✐♥❣ str❛t❡❣✐❡s ✐♥ t❤❡ ❝♦♥str❛✐♥t s♦•✈❡r ❛r❡ ❜❛s❡❞ ♦♥ t❤❡ ❛ss✐❣♥♠❡♥t ♦❢ ❛ s❡✲ •❡❝t❡❞ ✈❛r✐❛❜•❡ t♦ ♦♥❡ ♦r s❡✈❡r❛• s❡•❡❝t❡❞ ✈❛•✉❡s ✭♦♥❡ ❛ss✐❣♥♠❡♥t ✐♥ ❡❛❝❤ ❜r❛♥❝❤✮✳ ❱❛r✐❛❜•❡ s❡•❡❝t♦r ❞❡✜♥❡s t❤❡ ✇❛② t♦ ❝❤♦♦s❡ ❛ ♥♦♥ ✐♥st❛♥t✐❛t❡❞ ✈❛r✐❛❜•❡ ♦♥ ✇❤✐❝❤ t❤❡ ♥❡①t ❞❡❝✐s✐♦♥ ✇✐•• ❜❡ ♠❛❞❡✳ ❖♥❝❡ t❤❡ ✈❛r✐❛❜•❡ ❤❛s ❜❡❡♥ ❝❤♦s❡♥✱ t❤❡ s♦•✈❡r ❤❛s t♦ ❝♦♠♣✉t❡ ✐ts ✈❛•✉❡✳ ✺✳✷✳✶ ❚❤❡ ❞❡❢❛✉•t s❡❛r❝❤ str❛t❡❣② ❚❤❡ ❞❡❢❛✉•t s❡❛r❝❤ str❛t❡❣② ✐s ❛♣♣•✐❡❞ t♦ t❤❡ ❞❡❝✐s✐♦♥ ✈❛r✐❛❜•❡s ♦❢ t❤❡ s♦•✈❡r ✇❤❡♥ ♥♦ s❡❛r❝❤ str❛t❡❣② ✐s s♣❡❝✐✜❡❞✳ ❚❤❡ ❞❡❢❛✉•t str❛t❡❣② s❡•❡❝ts t❤❡ ❞❡❝✐s✐♦♥ ✈❛r✐❛❜•❡s t♦ ❜❡ ✐♥st❛♥t✐❛t❡❞ ❜② ✉s✐♥❣ t❤❡ ❢♦••♦✇✐♥❣ ❜r❛♥❝❤✐♥❣ str❛t❡❣✐❡s✳ ❱❛r✐❛❜•❡ s❡•❡❝t✐♦♥ ❤❡✉r✐st✐❝✿ ❉♦♠❖✈❡r❲❉❡❣✳ ❚❤❡ str❛t❡❣② s❡•❡❝ts t❤❡ ✈❛r✐❛❜•❡ M at vi ✇✐t❤ t❤❡ s♠❛••❡st r❛t✐♦ r✿ r = dom w * deg ✇❤❡r❡ dom ✐s t❤❡ ❝✉rr❡♥t ❞♦♠❛✐♥ s✐③❡✱ deg ✐s t❤❡ ❝✉rr❡♥t ♥✉♠❜❡r ♦❢ ♥♦♥ ✐♥st❛♥✲ t✐❛t❡❞ ❝♦♥str❛✐♥ts ✐♥✈♦•✈✐♥❣ t❤❡ ✈❛r✐❛❜•❡✱ ❛♥❞ w t❤❡ s✉♠ ♦❢ t❤❡ ❝♦✉♥t❡rs ♦❢ t❤❡ ❢❛✐•✉r❡s ❝❛✉s❡❞ ❜② ❡❛❝❤ ❝♦♥str❛✐♥t ❢r♦♠ t❤❡ ❜❡❣✐♥♥✐♥❣ ♦❢ t❤❡ s❡❛r❝❤✳ ❚♦ ❡❛❝❤ ✈❛r✐❛❜•❡ M at(v i ) ❛r❡ ❛ss♦❝✐❛t❡❞✱ ❛t ❛♥② t✐♠❡ t❤❡ dom✱ deg ❛♥❞ w ✈❛•✉❡s✳ ❱❛•✉❡ s❡•❡❝t✐♦♥ ❤❡✉r✐st✐❝✿ ▼✐♥❱❛•✳ ❚❤❡ ✈❛r✐❛❜•❡ M at vi ✇❤✐❝❤ ❤❛s ❜❡❡♥ ❝❤♦s❡♥ ✭❜② ❛♣♣•②✐♥❣ t❤❡ ✈❛r✐❛❜•❡ s❡•❡❝t✐♦♥ ❤❡✉r✐st✐❝✮ ✐s t❤❡♥ ❛ss✐❣♥❡❞✱ ✐♥ t❤❡ ✜rst ❜r❛♥❝❤✱ t♦ ✐ts s♠❛••❡st ✈❛•✉❡✿ val = min(d M atv i ) ■♥ t❤❡ ♥❡①t ❜r❛♥❝❤✱ t❤❡ ✈❛•✉❡ val ✐s r❡♠♦✈❡❞ ❢r♦♠ t❤❡ ✈❛r✐❛❜•❡ ❞♦♠❛✐♥ d M atv i ✳ ✺✳✷✳✷ ❖✉r ♦✇♥ s❡❛r❝❤ str❛t❡❣② ❆s ♠❡♥t✐♦♥❡❞ ✐♥ ❙❡❝t✐♦♥ ✸✳✷✱ ❝♦♥str❛✐♥t ♣r♦✲ ❣r❛♠♠✐♥❣ ♦✛❡rs ❢❛❝✐•✐t✐❡s t♦ ❝♦♥tr♦• t❤❡ s❡❛r❝❤ ❜❡❤❛✈✐♦r✳ ❉❡✜♥✐♥❣ ♦✉r ♦✇♥ s❡❛r❝❤ str❛t❡❣② ✐s ✈❡r② ✐♠♣♦rt❛♥t s✐♥❝❡ ❛ ✇❡••✲s✉✐t❡❞ s❡❛r❝❤ str❛t❡❣② ❝❛♥ r❡❞✉❝❡ t❤❡ ♥✉♠✲ ❜❡r ♦❢ ❡①♣❛♥❞❡❞ ♥♦❞❡s ❛♥❞ ❤❡♥❝❡ t❤❡ t✐♠❡ t❤❛t t❤❡ s♦•✈❡r t❛❦❡s t♦ ✜♥❞ s♦•✉t✐♦♥s t♦ t❤❡ ✈✐❡✇ s❡•❡❝t✐♦♥ ♣r♦❜•❡♠✳ ■♥ t❤❡ ❢♦••♦✇✐♥❣ ✇❡ ❞❡s❝r✐❜❡ t❤❡ ✈❛r✐❛❜•❡ ❛♥❞ ✈❛•✉❡ s❡•❡❝t✐♦♥ ❤❡✉r✐st✐❝s t❤❛t ✇❡ ❤❛✈❡ ❞❡✜♥❡❞ ✐♥ t❤❡ s❡❛r❝❤ str❛t❡❣②✳ ❱❛r✐❛❜•❡ ❛♥❞ ✈❛•✉❡ s❡•❡❝t✐♦♥ ❤❡✉r✐st✐❝s✳ ❖✉r ❛✐♠ ✐s t♦ ♠✐♥✐♠✐③❡ t❤❡ q✉❡r② ❝♦st ✇✐t❤ ❛ ❝♦♥str❛✐♥t ♦♥ ✉♣❞❛t❡ t✐♠❡ ✭♠❛✐♥t❡♥❛♥❝❡ ❝♦st ❝♦♥str❛✐♥t✮ ❛♥❞ st♦r❛❣❡ s♣❛❝❡ ✭s♣❛❝❡ ❝♦♥str❛✐♥t✮✳ ▲♦✇ q✉❡r② ❝♦st ❝❛♥ ❜❡ ♦❜t❛✐♥❡❞ ❜② ♠❛t❡r✐❛•✐③✐♥❣ ❛•• t❤❡ q✉❡r✐❡s ♦❢ t❤❡ ✇♦r❦•♦❛❞ ✭♠❛t❡r✐❛•✐③✐♥❣ t❤❡ r♦♦t •❡✈❡• ✐♥ t❤❡ ❆◆❉✲❖| ✈✐❡✇ ❣r❛♣❤✮✳ ■♥ t❤✐s ❝❛s❡ t❤❡ ✈✐❡✇ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ✇✐•• ❜❡ ❤✐❣❤✳ ▲♦✇ ✈✐❡✇ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ❝❛♥ ❜❡ ❛❝❤✐❡✈❡❞ ❜② •❡❛✈✐♥❣ ❛•• t❤❡ ✈✐❡✇s ✈✐rt✉❛• ❛♥❞ ✐♥ t❤✐s ❝❛s❡ t❤❡ q✉❡r② ❝♦st ✇✐•• ❜❡ ❤✐❣❤ ✭r❡♣•✐❝❛t✐♥❣ t❤❡ ❜❛s❡ r❡•❛t✐♦♥s ✇❤✐❝❤ ❛r❡ ✐♥ t❤❡ •❡❛❢ •❡✈❡• ♦❢ t❤❡ ❆◆❉✲ ❖| ✈✐❡✇ ❣r❛♣❤✮✳ ❋♦r t❤✐s ♠❛tt❡r✱ ♦✉r str❛t❡❣② ❝♦♥s✐sts ✐♥ ✜♥❞✐♥❣ ❛♥ ✐♥t❡r♠❡❞✐❛r② •❡✈❡• ❢♦r ❡❛❝❤ q✉❡r② tr❡❡ ✐♥ t❤❡ ❆◆❉✲❖| ✈✐❡✇ ❣r❛♣❤ t❤❛t ♦♣t✐♠✐③❡s t❤❡ q✉❡r② ❝♦st ✇✐t❤♦✉t ✈✐♦•❛t✐♥❣ t❤❡ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ❛♥❞ s♣❛❝❡ ❝♦♥str❛✐♥ts✳ ❚❤❡r❡❢♦r❡✱ ♦✉r str❛t❡❣② ✐s ❜❛s❡❞ ♦♥ t❤❡ ♥♦t✐♦♥ ♦❢ •❡✈❡• ✐♥ t❤❡ ❆◆❉✲❖| ✈✐❡✇ ❣r❛♣❤ ❬✹(✳ ❋♦r t❤✐s ♣✉r♣♦s❡✱ ❡❛❝❤ ✈✐❡✇ ✭❡q✉✐✈❛•❡♥❝❡ ♥♦❞❡✮ ✐s ❛ss♦❝✐❛t❡❞ t♦ ❛ •❡✈❡•✱ ✇❤✐❝❤ ✐s ❞❡✜♥❡❞ ❛s ❢♦••♦✇s✿ level(baserelation) = 0 level(view) = max vc∈child(view) level(v c ) + 1 ❆s ♣r❡s❡♥t❡❞ ✐♥ t❤❡ ❝♦❞❡ ❜❡•♦✇✱ ✇❡ ❡①♣•❛✐♥ ❤♦✇ t♦ ❝♦♠♣✉t❡ ❢♦r ❡❛❝❤ q✉❡r② t❤❡ r❡•❛t✐✈❡ q✉❡r② ❝♦st r❡❞✉❝t✐♦♥ ❛ss♦❝✐❛t❡❞ t♦ t❤❡ ❞✐✛❡r❡♥t •❡✈❡•s ✐♥ t❤❡ q✉❡r② tr❡❡✳ levels = ∅ //set
of levels with their cost saving ❢♦r each q in Q(G) ❞♦ levelCS = ∅//M ap : key = level; val = cost saving // each view in the query tree is associated to a level ❢♦r each l in AllLevels(q) ❞♦

space = 0 maint = 0 ❢♦r each v in AllV iews(l) ❞♦ space = space + size(v) maint = maint + M c(v) ❡♥❞ ❢♦r ✐❢ space ≤ Sp M ax and maint ≤ U M ax t❤❡♥
LevelCostSaving(q, l) //LevelCostSaving is def ined as the relative //query cost reduction when the views associated // to level l are materialized ❡•s❡

LevelCostSaving(q, l) = -1 ❡♥❞ ✐❢ levelCS.put(l, LevelCostSaving) ❡♥❞ ❢♦r levels = levels ∪ {levelCS} ❡♥❞ ❢♦r ■♥ ♦r❞❡r t♦ ❣✉✐❞❡ t❤❡ s❡❛r❝❤ t♦ t❤❡ ♦♣t✐♠❛• s♦•✉t✐♦♥✱ t❤❡ ✈❛r✐❛❜•❡ s❡•❡❝t♦r ❤❛s t♦ st❛rt ❜② ✐♥st❛♥t✐❛t✐♥❣ t❤❡ ♠❛t❡r✐❛•✐③❛t✐♦♥ ✈❛r✐❛❜•❡s ♦❢ t❤❡ r❡❝♦♠♠❡♥❞❡❞ ✈✐❡✇s✳ ❚❤❡s❡ ✈✐❡✇s ❛r❡ t❤♦s❡ ❛ss♦❝✐❛t❡❞ t♦ t❤❡ •❡✈❡•s t❤❛t ♠✐♥✐♠✐③❡ t❤❡ q✉❡r② ❝♦st s✉❜•❡❝t t♦ s♣❛❝❡ ❛♥❞ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ❝♦♥str❛✐♥ts✳ ❋♦
❢♦r each l s in LSort ❞♦ ❢♦r each v s in l s ❞♦ M V = M V ∪ {M at vs } ❡♥❞ ❢♦r ❡♥❞ ❢♦r ❋✐♥❛••②✱ t❤❡ ✈❛r✐❛❜•❡ s❡•❡❝t♦r ✇✐•• ❝❤♦♦s❡ t❤❡ ♠❛t❡r✐❛•✐③❛t✐♦♥ ✈❛r✐❛❜•❡s t♦ ❜❡ ✐♥st❛♥t✐❛t❡❞ ✐♥ t❤❡ ♦r❞❡r t❤❡② ❛♣♣❡❛r ✐♥ M V ✳ ❖♥❝❡ t❤❡ ✈❛r✐❛❜•❡ ❤❛s ❜❡❡♥ ❝❤♦s❡♥✱ t❤❡ ✈❛•✉❡ s❡•❡❝t♦r ✇✐•• ❛ss✐❣♥ t❤❡ ♠❛t❡r✐❛•✐③❛t✐♦♥ ✈❛r✐❛❜•❡ t♦ ✐ts ❤✐❣❤❡st ✈❛•✉❡✿ max(d M atv i )✳ ◆♦t❡ t❤❛t t❤❡s❡ ✈❛r✐❛❜•❡ ❛♥❞ ✈❛•✉❡ ❤❡✉r✐st✐❝s ❞♦ ♥♦t ✐♥❤✐❜✐t t❤❡ s♦•✈❡r t♦ ❝♦♠♣✉t❡ s♦•✉t✐♦♥s ✐♥ ✇❤✐❝❤ ✐t ✇✐•• st❛rt ❜② ♠❛t❡r✐❛•✐③✐♥❣ ❛♥♦t❤❡r s❡t ♦❢ ✈✐❡✇s✳ ❇② ❞❡✜♥✐♥❣ t❤❡s❡ ❤❡✉r✐st✐❝s ✐♥ t❤❡ s❡❛r❝❤ str❛t❡❣②✱ ✇❡ ❡①♣❡❝t t❤❡ s♦•✈❡r t♦ ❝♦♥✈❡r❣❡ ❢❛st❡r t♦ t❤❡ ♦♣t✐♠❛• s♦•✉t✐♦♥ ❛♥❞ ❛✈♦✐❞ ❜r♦✇s✐♥❣ ❛ •❛r❣❡ ♥✉♠❜❡r ♦❢ ✐♥❢❡r✐♦r s♦•✉t✐♦♥s✳ ✻ P❡r❢♦r♠❛♥❝❡ ❊✈❛•✉❛t✐♦♥ ■♥ t❤✐s s❡❝t✐♦♥✱ ✇❡ ❡✈❛•✉❛t❡ t❤❡ ♣❡r❢♦r♠❛♥❝❡ ♦❢ ♦✉r ❛♣♣r♦❛❝❤ t❤r♦✉❣❤ ❡①♣❡r✐♠❡♥✲ t❛t✐♦♥s ♦✈❡r t❤❡ ❞❛t❛❜❛s❡ s❝❤❡♠❛ ♦❢ t❤❡ ❚P❈✲❍ ❜❡♥❝❤♠❛r❦ ❬✷(✳ ❖✉r ❛♣♣r♦❛❝❤ t❛❦❡s ❛s ✐♥♣✉t ❛ s❡t ♦❢ s❡•❡❝t✐♦♥✲♣r♦•❡❝t✐♦♥✲•♦✐♥ ✭❙P❏✮ q✉❡r✐❡s t❤❛t ♠❛② ✐♥✈♦•✈❡ ❛❣❣r❡❣❛t✐♦♥ ❛♥❞ ❣r♦✉♣ ❜② ❝•❛✉s❡ ❛s ✇❡••✳ ❋♦r ❡❛❝❤ q✉❡r②✱ ✇❡ ❝♦♥s✐❞❡r ❛•• ♣♦ss✐❜•❡ ❡①❡❝✉t✐♦♥ ♣•❛♥s ✇❤✐❝❤ r❡♣r❡s❡♥t ✐ts ❡①❡❝✉t✐♦♥ str❛t❡❣✐❡s✳ ❚❤❡♥✱ ❛•• t❤❡ q✉❡r✐❡s ❛r❡ ♠❡r❣❡❞ ✐♥t♦ t❤❡ s❛♠❡ ❣r❛♣❤ ✭s❡❡ ❙❡❝t✐♦♥ ✹✮ ✐♥ ♦r❞❡r t♦ ❞❡t❡❝t t❤❡ ♦✈❡r•❛♣♣✐♥❣ ❛♥❞ ❝❛♣t✉r❡ t❤❡ ❞❡♣❡♥❞❡♥❝✐❡s ❛♠♦♥❣ t❤❡♠✳ ❖✉r ❛♣♣r♦❛❝❤ ♣r♦❞✉❝❡s ❛s ♦✉t♣✉t t❤❡ s❡t ♦❢ ♠❛t❡r✐❛•✐③❡❞ ✈✐❡✇s✳ ❚❤❡ ♣❡r❢♦r♠❛♥❝❡ ♦❢ ♦✉r ❛♣♣r♦❛❝❤ ✇❛s ❡✈❛•✉❛t❡❞ ❜② ♠❡❛s✉r✐♥❣ t❤❡ ❣❛✐♥ ✐♥ s♦•✉t✐♦♥ q✉❛•✐t② ♦❜t❛✐♥❡❞ ❜② t❤❡ ♠❛t❡r✐❛•✐③❡❞ ✈✐❡✇s✳ ❚❤❡ r❡st ♦❢ t❤✐s s❡❝t✐♦♥ ✐s ♦r❣❛♥✐③❡❞ ❛s ❢♦••♦✇s✳ ■♥ ❙❡❝t✐♦♥ ✻✳✶✱ ✇❡ ❞❡s❝r✐❜❡ ♦✉r ❡①♣❡r✐♠❡♥t❛• s❡t✉♣✱ ❛♥❞ t❤❡ r❛♥❞♦♠✐③❡❞ ♠❡t❤♦❞ ✉s❡❞ ❢♦r ❝♦♠♣❛r✐s♦♥✳ ■♥ ❙❡❝t✐♦♥ ✻✳✷✱ ✇❡ st✉❞② t❤❡ ✐♠♣❛❝t ♦❢ ✈❛r✐❛❜•❡ ❛♥❞ ✈❛•✉❡ s❡•❡❝t✐♦♥ ❤❡✉r✐st✐❝s ♦♥ t❤❡ s❡❛r❝❤ s♣❛❝❡ ❡①♣•♦r❡❞ ❜② ♦✉r ❛♣♣r♦❛❝❤✳ ■♥ ❙❡❝t✐♦♥ ✻✳✸✱ ✇❡ ✜rst r❡♣♦rt ❡①♣❡r✐♠❡♥t❛• r❡s✉•ts ✇❤❡♥ t❤❡ ✈✐❡✇ s❡•❡❝t✐♦♥ ✐s ❞❡❝✐❞❡❞ ✉♥❞❡r r❡s♦✉r❝❡ ❝♦♥str❛✐♥ts ❛♥❞ ✇❡ ♣r❡s❡♥t t❤❡ r❡s✉•ts ♦♥ ♣❡r❢♦r♠❛♥❝❡ ❜② ✐♥❝r❡❛s✐♥❣ t❤❡ ♥✉♠❜❡r ♦❢ q✉❡r✐❡s✳ ❚❤❡♥✱ ✇❡ ❡✈❛•✉❛t❡ t❤❡ ❡✛❡❝t ♦❢ t❤❡ ❢r❡q✉❡♥❝② ♦❢ q✉❡r✐❡s ❛♥❞ ✉♣❞❛t❡s ❛s ✇❡•• ❛s t❤❡ q✉❡r② ❝♦♠♣•❡①✐t② ♦♥ ♣❡r❢♦r♠❛♥❝❡✳ ■♥ ❙❡❝t✐♦♥ ✻✳✹✱ ✇❡ st✉❞② t❤❡ ❜❡♥❡✜t ♦❢ ✉s✐♥❣ ♠❛t❡r✐❛•✐③❡❞ ✈✐❡✇s t♦ ✐♠♣r♦✈❡ q✉❡r② ♣❡r❢♦r♠❛♥❝❡✳ ❋✐♥❛••②✱ ✇❡ s✉♠♠❛r✐③❡ t❤❡ ♣❡r❢♦r♠❛♥❝❡ r❡s✉•ts ✐♥ ❙❡❝t✐♦♥ ✻✳✺✳ ✻✳✶ ❊①♣❡r✐♠❡♥t❛• ❙❡t✉♣ ❲❡ ❤❛✈❡ ✐♠♣•❡♠❡♥t❡❞ ♦✉r ❛♣♣r♦❛❝❤ ❛♥❞ ❝♦♠♣❛r❡❞ ✐t ✇✐t❤ ❛ r❛♥❞♦♠✐③❡❞ ♠❡t❤♦❞ ✐✳❡✳✱ ❣❡♥❡t✐❝ ❛•❣♦r✐t❤♠ ✳ ❚❤❡ •❛tt❡r ✇❛s ❝❤♦s❡♥ ❢♦r ❝♦♠♣❛r✐s♦♥ s✐♥❝❡ ✐t ❤❛s ❜❡❡♥ ❛r❣✉❡❞ t❤❛t t❤❡ ❣❡♥❡t✐❝ ❛•❣♦r✐t❤♠ ♣r♦✈✐❞❡s ❛ ❣♦♦❞ ❜❛•❛♥❝❡ ❜❡t✇❡❡♥ t❤❡ ❝♦♠♣✉t✲ ✐♥❣ ❝♦sts t❤❛t ❛♥ ❛•❣♦r✐t❤♠ ✐♥❝✉rs ❢♦r ✜♥❞✐♥❣ t❤❡ ♠❛t❡r✐❛•✐③❡❞ ✈✐❡✇s ❛♥❞ t❤❡ ❣❛✐♥ t♦ ❜❡ r❡❛•✐③❡❞ ✐♥ q✉❡r② ♣r♦❝❡ss✐♥❣ ❜② ♠❛t❡r✐❛•✐③✐♥❣ t❤❡s❡ ✈✐❡✇s ✭s❡❡ ❙❡❝t✐♦♥ ✷✮✳ ❆•• t❤❡ ❛•❣♦r✐t❤♠s ❛r❡ ✐♠♣•❡♠❡♥t❡❞ ✐♥ ❏❛✈❛ ❛♥❞ ❛•• t❤❡ ❡①♣❡r✐♠❡♥ts ✇❡r❡ ❝❛rr✐❡❞ ♦✉t ♦♥ ❛♥ ■♥t❡• ❈♦r❡ ✷ ❉✉♦ P✽✻✵✵ ❈P❯ ❅ ✷✳✹✵ •❍③ ♠❛❝❤✐♥❡ r✉♥♥✐♥❣ ✇✐t❤ ✸•❇ ♦❢ |❆▼ ❛♥❞ ❲✐♥❞♦✇s ❳P Pr♦❢❡ss✐♦♥❛• ❙P✸✳ ■♥ ♦r❞❡r t♦ s♦•✈❡ t❤❡ ✈✐❡✇ s❡•❡❝t✐♦♥ ♣r♦❜•❡♠ ❛s ❛ ❝♦♥str❛✐♥t s❛t✐s❢❛❝t✐♦♥ ♣r♦❜✲ •❡♠✱ ✇❡ ❤❛✈❡ ✉s❡❞ t❤❡ •❛t❡st ♣♦✇❡r❢✉• ✈❡rs✐♦♥ ♦❢ ❈❍❖❈❖ ❬✶( ✭❦♥♦✇✐♥❣ t❤❛t t❤❡ ❝♦♥str❛✐♥t s♦•✈❡rs ❛r❡ str✉❝t✉r❡❞ ❛r♦✉♥❞ ❛♥♥✉❛• ❝♦♠♣❡t✐t✐♦♥s ❬✶✼(✮✳ ❋♦r t❤❡ ❣❡✲ ♥❡t✐❝ ❛•❣♦r✐t❤♠✱ ✇❡ ❤❛✈❡ ✐♠♣•❡♠❡♥t❡❞ t❤❡ ♦♥❡ ♣r❡s❡♥t❡❞ ✐♥ ❬✺( ❜② ✐♥❝♦r♣♦r❛t✐♥❣ s♣❛❝❡ ❛♥❞ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ❝♦♥str❛✐♥ts ✐♥t♦ t❤❡ ❛•❣♦r✐t❤♠ ❛♥❞ ✇✐t❤♦✉t t❛❦✐♥❣ ✐♥t♦ ❛❝❝♦✉♥t t❤❡ ❞❛t❛ ♣•❛❝❡♠❡♥t✳ ■♥ ♦r❞❡r t♦ •❡t t❤❡ ❣❡♥❡t✐❝ ❛•❣♦r✐t❤♠ ❝♦♥✲ ✈❡r❣❡ q✉✐❝❦•②✱ ✇❡ ❣❡♥❡r❛t❡❞ ❛♥ ✐♥✐t✐❛• ♣♦♣✉•❛t✐♦♥ ✇❤✐❝❤ r❡♣r❡s❡♥ts ❛ ❢❛✈♦r❛❜•❡ ✈✐❡✇ ❝♦♥✜❣✉r❛t✐♦♥ r❛t❤❡r t❤❛♥ ❛ r❛♥❞♦♠ s❛♠♣•✐♥❣✳ ❋❛✈♦r❛❜•❡ ✈✐❡✇ ❝♦♥✜❣✉r❛t✐♦♥ s✉❝❤ ❛s t❤❡ ✈✐❡✇s ✇❤✐❝❤ ♠✐♥✐♠✐③❡ t❤❡ q✉❡r② ❝♦st ✇✐t❤♦✉t ✈✐♦•❛t✐♥❣ s♣❛❝❡ ❛♥❞ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ❝♦♥str❛✐♥ts ❛r❡ ♠♦st •✐❦❡•② s❡•❡❝t❡❞ ❢♦r ♠❛t❡r✐❛•✐③❛t✐♦♥✳ ❚♦ ❡✈❛•✉❛t❡ t❤❡ ♣❡r❢♦r♠❛♥❝❡ ♦❢ ✈✐❡✇ s❡•❡❝t✐♦♥ ♠❡t❤♦❞s✱ ✇❡ ♠❡❛s✉r❡ t❤❡ ❢♦•✲ •♦✇✐♥❣ ♠❡tr✐❝✳ ✶✳ ❙♦•✉t✐♦♥ ◗✉❛•✐t②✳ ❚❤❡ ♣❡r❢♦r♠❛♥❝❡ ♦❢ ✈✐❡✇ s❡•❡❝t✐♦♥ ♠❡t❤♦❞s ✇❛s ❡✈❛•✲ ✉❛t❡❞ ❜② ♠❡❛s✉r✐♥❣ t❤❡ s♦•✉t✐♦♥ q✉❛•✐t② ✇❤✐❝❤ r❡s✉•ts ❢r♦♠ ❡✈❛•✉❛t✐♥❣ t❤❡ q✉❛•✐t② ♦❢ t❤❡ ♦❜t❛✐♥❡❞ s❡t ♦❢ ♠❛t❡r✐❛•✐③❡❞ ✈✐❡✇s ✐♥ t❡r♠s ♦❢ ❝♦st s❛✈✐♥❣✳ ■♥ t❤❡ ❡①♣❡r✐♠❡♥t❛• r❡s✉•ts✱ t❤❡ s♦•✉t✐♦♥ q✉❛•✐t② ❞❡♥♦t❡❞ ❜② Q s ✐s ❝♦♠♣✉t❡❞ ❛s ❢♦••♦✇s✿ Q s = W M -vi∈Q(G) f q (v i ) * Qc(v i ) W M -ALLM ✭✾✮ ❲❤❡r❡ W M ✐s t❤❡ t♦t❛• q✉❡r② ❝♦st ♦❜t❛✐♥❡❞ ✉s✐♥❣ t❤❡ ✧❲✐t❤♦✉t▼❛t✧ ❛♣✲ ♣r♦❛❝❤ ✇❤✐❝❤ ❞♦❡s ♥♦t ♠❛t❡r✐❛•✐③❡ ✈✐❡✇s ❛♥❞ ❛•✇❛②s r❡❝♦♠♣✉t❡s q✉❡r✐❡s✱ AllM ✐s t❤❡ ✧❆••▼❛t✧ ❛♣♣r♦❛❝❤ ✇❤✐❝❤ ♠❛t❡r✐❛•✐③❡s t❤❡ r❡s✉•t ♦❢ ❡❛❝❤ q✉❡r② ♦❢ t❤❡ ✇♦r❦•♦❛❞✳ ❚❤❡ ✧❲✐t❤♦✉t▼❛t✧ ❛♥❞ ✧❆••▼❛t✧ ❛♣♣r♦❛❝❤❡s ❛r❡ ✉s❡❞ ❛s ❛ ❜❡♥❝❤♠❛r❦ ❢♦r ♦✉r ♥♦r♠❛•✐③❡❞ r❡s✉•ts✳ ❆s ❞❡✜♥❡❞ ✐♥ ❙❡❝t✐♦♥ ✺✱ Qc(v i ) ✐s t❤❡ q✉❡r② ❝♦st ❝♦rr❡s♣♦♥❞✐♥❣ t♦ t❤❡ ✈✐❡✇ v i ❛♥❞ f q (v i ) ✐s t❤❡ ❢r❡q✉❡♥❝② ♦❢ t❤❡ ✈✐❡✇ v i ✳ ✷✳ ❙♣❛❝❡ ❝♦♥str❛✐♥t✳ ■♥ t❤❡ ❝❛s❡ ✇❤❡r❡ t❤❡ ✈✐❡✇ s❡•❡❝t✐♦♥ ♣r♦❜•❡♠ ✐s ❞❡❝✐❞❡❞ ✉♥❞❡r ❛ s♣❛❝❡ ❝♦♥str❛✐♥

  st ✐s ❡st✐♠❛t❡❞ ❛s t❤❡ t✐♠❡ ♥❡❡❞❡❞ t♦ ♣r♦❝❡ss ❡❛❝❤ t✉♣•❡ ♦❢ t❤❡ r❡•❛t✐♦♥ ❡✳❣✳✱ ❝❤❡❝❦✐♥❣ s❡•❡❝t✐♦♥ ❝♦♥❞✐t✐♦♥s✳ ✕ ❚❤❡ ■❖ ❝♦st ❡st✐♠❛t✐♦♥ ✐s t❤❡ t✐♠❡ ♥❡❝❡ss❛r② ❢♦r ❢❡t❝❤✐♥❣ ❡❛❝❤ t✉♣•❡ ♦❢ t❤❡ r❡•❛t✐♦♥✳ ✕ ❚❤❡ ❝♦sts ❛r❡ ❡st✐♠❛t❡❞ ❛❝❝♦r❞✐♥❣ t♦ t❤❡ s✐③❡ ♦❢ t❤❡ ✐♥✈♦•✈❡❞ r❡•❛t✐♦♥s ❛♥❞ ✐♥ t❡r♠s ♦❢ t✐♠❡✳ ❊st✐♠❛t❡❞ ❝♦st ♦❢ r❡•❛t✐♦♥❛• ♦♣❡r❛t✐♦♥s✳ ✕ ❊st✐♠❛t❡❞ ❝♦st ♦❢ ✉♥❛r② ♦♣❡r❛t✐♦♥s • cost(op) = (IO * card * length) + (CP U * card * lengthP ) ✇❤❡r❡ ♦♣ ✐s ❛ s❡•❡❝t✐♦♥ ♦♣❡r❛t✐♦♥ • cost(op) = (IO * card * log(card) * length) + (CP U * card * log(card) * lengthP ) ✇❤❡r❡ ♦♣ ✐s ❛ ♣r♦•❡❝t✐♦♥ ♦♣❡r❛t✐♦♥ • cost(op) = (IO * card * length) + (CP U * card * lengthA) ✇❤❡r❡ ♦♣ ✐s ❛♥ ❛❣❣r❡❣❛t✐♦♥ ♦♣❡r❛t✐♦♥ ✕ ❊st✐♠❛t❡❞ ❝♦st ♦❢ ❜✐♥❛r② ♦♣❡r❛t✐♦♥s • cost(op) = (IO * lcard * rcard * (llength + rlength)) + (CP U * lcard * rcard * lengthP ) ✇❤❡r❡ ♦♣ ✐s ❛ •♦✐♥ ♦♣❡r❛t✐♦♥ ❲❤❡r❡ card ✐s t❤❡ ♥✉♠❜❡r ♦❢ t✉♣•❡s ♦❢ t❤❡ ♦♣❡r❛♥❞✱ length ✐s t❤❡ •❡♥❣t❤ ✭✐♥ ❜②t❡s✮ ♦❢ ❛ t✉♣•❡✱ lengthP ✐s t❤❡ •❡♥❣t❤ ♦❢ ❝♦•✉♠♥s ❝❤❡❝❦❡❞ ❜② ♣r❡❞✐❝❛t❡s✱lengthA ✐s t❤❡ •❡♥❣t❤ ♦❢ t❤❡ t✉♣•❡s ❜❡✐♥❣ ❛❣❣r❡❣❛t❡❞✱ lcard ❛♥❞ rcard ❛r❡ r❡s♣❡❝✲ t✐✈❡

  r t❤✐s ♣✉r♣♦s❡✱ ✇❡ s♦rt t❤❡ q✉❡r② •❡✈❡•s ❛❝❝♦r❞✐♥❣ t♦ t❤❡✐r LevelCostSaving ✐♥ ❞❡s❝❡♥❞✐♥❣ ♦r❞❡r ✭❛s ✐t ✐s ♣r❡s❡♥t❡❞ ❜❡•♦✇✮✳ ❲❡ ✐t❡r❛t❡ ♦✈❡r t❤❡ s♦rt❡❞ s❡t st❛rt✐♥❣ ✇✐t❤ t❤❡ •❡✈❡•s ✇❤✐❝❤ ❤❛✈❡ t❤❡ ❤✐❣❤❡st q✉❡r② ❝♦st r❡❞✉❝t✐♦♥✳ ❲❡ t❤❡♥ st♦r❡ ❡❛❝❤ ✈✐❡✇ ❛ss♦❝✐❛t❡❞ t♦ t❤❡s❡ •❡✈❡•s ✐♥ t❤❡ ✈❛r✐❛❜•❡ M V ✳ //sort the levels according to their LevelCostSaving in //descending order LSort = SortLevels(levels)

✭✶✵✮✇❤❡r❡

  Sp AllM ✐s t❤❡ s✐③❡ ♦❢ t❤❡ ✇❤♦•❡ ✇♦r❦•♦❛❞ ❛♥❞ α ✐s ❛ ❝♦♥st❛♥t✳ ■♥ ♦✉r ❡①♣❡r✐♠❡♥ts✱ ✇❡ ❛ss✉♠❡ t❤❡ ❝❛s❡ ✇❤❡r❡ t❤❡ ✈✐❡✇ s❡•❡❝t✐♦♥ ✐s st✉❞✐❡❞ ✉♥❞❡r r❡str✐❝t✐✈❡ ❝♦♥str❛✐♥ts ❛♥❞ ❤❡♥❝❡ ✇❡ s❡t α t♦ ✶✵✪✳ ❲❡ ❛•s♦ ❡①❛♠✐♥❡ t❤❡ ❝❛s❡ ✇❤❡r❡ t❤❡ ❝♦♥str❛✐♥ts ❛r❡ ♥♦t ✈❡r② t✐❣❤t ❛♥❞ ❛t t❤❛t ❝❛s❡ α ✇❛s s❡t t♦ ✸✵✪✳✸✳ ▼❛✐♥t❡♥❛♥❝❡ ❈♦st ❈♦♥str❛✐♥t✳ ■♥ t❤❡ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ❝♦♥str❛✐♥❡❞ ♠♦❞❡•✱ t❤❡ t♦t❛• ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ♦❢ t❤❡ s❡t ♦❢ ♠❛t❡r✐❛•✐③❡❞ ✈✐❡✇s ❤❛s t♦ ❜❡ •❡ss t❤❛♥ ♦r ❡q✉❛• t♦ t❤❡ t♦t❛• ✈✐❡✇ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st •✐♠✐t U max ✳ ❆s ✐♥ ♣r❡✈✐♦✉s ✇♦r❦ ❬✶✵(✱ U max ✐s ❝❛•❝✉•❛t❡❞ ❛s ❛ ❢✉♥❝t✐♦♥ ♦❢ t❤❡ t♦t❛• ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ✇❤❡♥ ❛•• t❤❡ q✉❡r✐❡s ❛r❡ ♠❛t❡r✐❛•✐③❡❞✳ U max = β * M c AllM ✭✶✶✮ ✇❤❡r❡ M c AllM ✐s t❤❡ t♦t❛• ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ✇❤❡♥ t❤❡ r❡s✉•t ♦❢ ❡❛❝❤ q✉❡r② ♦❢ t❤❡ ✇♦r❦•♦❛❞ ✐s ♠❛t❡r✐❛•✐③❡❞ ❛♥❞ β ✐s ❛ ❝♦♥st❛♥t✳ ❚❤❡ ✈❛•✉❡ ♦❢ β ✇❛s s❡t s✐♠✐•❛r t♦ α ✭s❡❡ ❛❜♦✈❡✮✳ ✹✳ |✉♥t✐♠❡✳ ❚❤❡ |✉♥t✐♠❡ ✇❤✐❝❤ ✇❡ ❝♦♥s✐❞❡r ❤❡r❡ ✐s t❤❡ t✐♠❡ t❤❛t ▼②❙◗▲ s❡r✈❡r t❛❦❡s t♦ ❝♦♠♣✉t❡ q✉❡r② r❡s✉•ts ✉s✐♥❣ ♠❛t❡r✐❛•✐③❡❞ ✈✐❡✇✳ ❚❤✐s ♠❡tr✐❝ ❤❛s ❜❡❡♥ ✉s❡❞ ✐♥ ❙❡❝t✐♦♥ ✻✳✹ t♦ ♠❡❛s✉r❡ t❤❡ r✉♥♥✐♥❣ t✐♠❡ ♦❢ t❤❡ q✉❡r② ✇♦r❦•♦❛❞ ❣✐✈❡♥ ❛ s❡t ♦❢ ♠❛t❡r✐❛•✐③❡❞ ✈✐❡✇s✳ ❚❤✉s✱ t❤❡ r✉♥t✐♠❡ ✐s ❛ ❣♦♦❞ ♠❡tr✐❝ t♦ st✉❞② t❤❡ ❜❡♥❡✜t t❤❛t ♠❛t❡r✐❛•✐③❡❞ ✈✐❡✇s ❢♦✉♥❞ ❜② ♦✉r ❛♣♣r♦❛❝❤ ❜r✐♥❣ t♦ q✉❡r② ❡✈❛•✉❛t✐♦♥✳ ■t ✐s ❛•s♦ ❛ ❣♦♦❞ ✐♥❞✐❝❛t♦r ❢♦r ❝♦♠♣❛r✐♥❣ t❤❡ ♣❡r❢♦r♠❛♥❝❡ ♦❢ ♦✉r ❛♣♣r♦❛❝❤ t♦ t❤♦s❡ ♦❢ t❤❡ ❣❡♥❡t✐❝ ❛•❣♦r✐t❤♠✳ ✻✳✷ ■♠♣❛❝t ♦❢ ✈❛r✐❛❜•❡ ❛♥❞ ✈❛•✉❡ s❡•❡❝t✐♦♥ ❤❡✉r✐st✐❝s ❍❡r❡✱ ✇❡ st✉❞② t❤❡ ✐♠♣❛❝t ♦❢ ✈❛r✐❛❜•❡ ❛♥❞ ✈❛•✉❡ s❡•❡❝t✐♦♥ ❤❡✉r✐st✐❝s t❤❛t ✇❡ ❤❛✈❡ ♣r❡s❡♥t❡❞ ✐♥ ❙❡❝t✐♦♥ ✺✳✷✳✷✱ ♦♥ t❤❡ s❡❛r❝❤ s♣❛❝❡ ❡①♣•♦r❡❞ ❜② ♦✉r ❛♣♣r♦❛❝❤✳ ❚♦ ❡✈❛•✉❛t❡ t❤✐s✱ ✇❡ ❛tt❡♠♣t❡❞ t♦ ❝♦♠♣❛r❡ t❤❡ s♦•✉t✐♦♥ q✉❛•✐t② ❢♦✉♥❞ ❜② t❤❡ ❝♦♥str❛✐♥t s♦•✈❡r ✐♥ t❤❡ ❝❛s❡ ✇❤❡r❡ ✭✐✮ t❤❡ ❞❡❢❛✉•t s❡❛r❝❤ str❛t❡❣② ✐s ✉s❡❞ ❛♥❞ ✭✐✐✮ t❤❡ ✈❛r✐❛❜•❡ ❛♥❞ ✈❛•✉❡ s❡•❡❝t✐♦♥ ❤❡✉r✐st✐❝s t❤❛t ✇❡ ❤❛✈❡ ❞❡✜♥❡❞ ✐♥ ❙❡❝t✐♦♥ ✺✳✷✳✷ ❛r❡ ✐♠♣•❡♠❡♥t❡❞ ✐♥ t❤❡ s❡❛r❝❤ str❛t❡❣②✳ ❆s ♠❡♥t✐♦♥❡❞ ✐♥ ❙❡❝t✐♦♥ ✸✳✷✱ t❤❡ ❝♦♥str❛✐♥t s♦•✈❡r ✭❈❍❖❈❖ ❙♦•✈❡r✮ ❝❛♥ ✜♥❞ ❛ s❡t ♦❢ ❢❡❛s✐❜•❡ s♦•✉t✐♦♥s ✐♥ ✇❤✐❝❤ ❛•• t❤❡ ❝♦♥str❛✐♥ts ❛r❡ s❛t✐s✜❡❞ ❜❡❢♦r❡ r❡❛❝❤✐♥❣ t❤❡ ♦♣t✐♠❛• s♦•✉t✐♦♥✳ ■♥ t❤✐s ❝❛s❡✱ ✇❡ ✉s❡ t✐♠❡♦✉t ❝♦♥❞✐t✐♦♥ t♦ ❡✈❛•✉❛t❡ t❤❡ q✉❛•✐t② ♦❢ t❤❡ ❞✐✛❡r❡♥t s♦•✉t✐♦♥s ❢♦✉♥❞ ❜② t❤❡ s♦•✈❡r✳ ❆ ✇♦r❦•♦❛❞ ♦❢ ✷✵ q✉❡r✐❡s s✉✣❝❡s t♦ ✐••✉str❛t❡ t❤✐s✳ α ❛♥❞ β✱ ✇❤✐❝❤ ❞❡✜♥❡ r❡s♣❡❝t✐✈❡•② t❤❡ st♦r❛❣❡ s♣❛❝❡ ❛♥❞ t❤❡ ✈✐❡✇ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st •✐♠✐ts✱ ✇❛s s❡t t♦ ✸✵✪✳ ❚❤❡ r❡s✉•ts ❛r❡ s❤♦✇♥ ✐♥ ✜❣✉r❡ ✸✳ ❚❤❡ s♦•✈❡r ✐s •❡❢t t♦ r✉♥ ✉♥t✐• r❡❛❝❤✐♥❣ t❤❡ ♦♣t✐♠❛• s♦•✉t✐♦♥✳ ❞❡❢❛✉•ts❡❛r❝❤ ❞❡♥♦t❡s t❤❡ ❞❡❢❛✉•t s❡❛r❝❤ str❛t❡❣② ❋✐❣✳ ✸✿ ■♠♣❛❝t ♦❢ ❤❡✉r✐st✐❝s ♦♥ t❤❡ s❡❛r❝❤ ✭❛✮ β❂✶✵✪ ✭❜✮ β❂✸✵✪ ✭❝✮ α❂✶✵✪ ✭❞✮ α❂✸✵✪ ❋✐❣✳ ✹✿ ❙♦•✉t✐♦♥ q✉❛•✐t② ✇❤✐•❡ ✈❛r②✐♥❣ t❤❡ s♣❛❝❡ ♦r t❤❡ ♠❛✐♥t❡♥❛♥❝❡ ❝♦st ❝♦♥✲ str❛✐♥t

  t✱ t❤❡ t♦t❛• s♣❛❝❡ ♦❝❝✉♣✐❡❞ ❜② t❤❡ ♠❛t❡r✐❛•✐③❡❞ ✈✐❡✇s ❤❛s t♦ ❜❡ •❡ss t❤❛♥ ♦r ❡q✉❛• t♦ t❤❡ ♠❛①✐♠✉♠ st♦r❛❣❡ s♣❛❝❡ Sp max ✳ ❙✐♠✐•❛r t♦ ❬✶✵( Sp max ✐s ❝♦♠♣✉t❡❞ ❛s ❛ ❢✉♥❝t✐♦♥ ♦❢ t❤❡ s✐③❡ ♦❢ t❤❡ ❛ss♦❝✐❛t❡❞ q✉❡r② ✇♦r❦•♦❛❞✳ Sp max = α * Sp AllM


Vincent Iehlé
email: vincent.iehle@dauphine.fr

The lattice structure of the S-Lorenz core *

Keywords: constrained egalitarian allocation, cooperative game, lattice, Lorenz core, Lorenz order. JEL classification: C71, D63

For any TU game and any ranking of players, the set of all preimputations compatible with the ranking, equipped with the Lorenz order, is a bounded join semi-lattice.

Furthermore the set admits as sublattice the S-Lorenz core intersected with the region compatible with the ranking. This result uncovers a new property about the structure of the S-Lorenz core. As immediate corollaries we obtain complementary results to the findings of Dutta and Ray, Games Econ. Behav., 3(4) p. 403-422 (1991), by showing that any S-constrained egalitarian allocation is the (unique) Lorenz greatest element of the S-Lorenz core on the rank-preserving region the allocation belongs to. Besides, our results suggest that the comparison between W-and S-constrained egalitarian allocations is more puzzling than what is usually admitted in the literature.

Introduction

The Lorenz criterion is widely accepted to compare profiles of revenues on the ground of egalitarianism. A profile Lorenz dominates another if its cumulative distribution, from rich to poor, is lower than the other one. But the use of that rule as a social value may be conflicting with the maximizing behavior of agents. The cooperative game theory provides an appropriate framework to assess whether individual interest and egalitarianism can be accommodated together (see, e.g., [START_REF] Arin | Lorenz undominated allocations for TU-games: The weighted coalitional Lorenz solutions[END_REF][START_REF] Arin | Egalitarian solutions in the core[END_REF][START_REF] Dutta | The egalitarian solution and reduced game properties in convex games[END_REF][START_REF] Dutta | The egalitarian solution and reduced game properties in convex games[END_REF]Ray, 1989, 1991;[START_REF] Hougaard | On the set of Lorenz-maximal imputations in the core of a balanced game[END_REF][START_REF] Jaffray | Constrained egalitarianism in a simple redistributive model[END_REF][START_REF] Llerena | A simple procedure for computing strong constrained egalitarian allocations[END_REF][START_REF] Roth | Pairwise kidney exchange[END_REF] and complements the classical analysis of inequality measurement (see, e.g., [START_REF] Atkinson | The comparison of multi-dimensioned distributions of economic status[END_REF][START_REF] Dasgupta | Notes on the measurement of inequality[END_REF][START_REF] Kolm | Multidimensional egalitarianisms[END_REF]. 1We consider here the solution concepts defined by [START_REF] Dutta | The egalitarian solution and reduced game properties in convex games[END_REF]Ray (1989, 1991) in cooperative games with transferable utility. The root concept is given by the notion of Lorenz core, defined recursively, that embody egalitarianism and maximizing behavior together with the property of robustness against credible multilateral deviations of coalitions of players. The Lorenz core is defined in two manners depending whether the weak or strong domination relation is chosen in the definition of deviation (W-Lorenz core and S-Lorenz core in the remainder). The central solution in the analysis of [START_REF] Dutta | The egalitarian solution and reduced game properties in convex games[END_REF]Ray (1989, 1991) is given by the Constrained Egalitarian Allocation, also defined in two manners according to the chosen relation. A WCEA (resp. SCEA) is a Lorenz undominated allocation in the W-Lorenz core (resp. S-Lorenz core). Hence, the distinction between the two definitions of a constrained egalitarian allocation is tight. However, it leads to contrasted results.

The sets of WCEAs and SCEAs are not comparable in general (see [START_REF] Dutta | Constrained egalitarian allocations[END_REF], for a list of examples). Both solutions have also different qualitative properties. For the WCEA, [START_REF] Dutta | A concept of egalitarianism under participation constraints[END_REF] find that the solution is unique, while its existence is not granted, except for convex games. In addition they show that the solution is the Lorenz greatest allocation of the core in convex games, but not necessarily the greatest of the W-Lorenz core. For the SCEA, [START_REF] Dutta | Constrained egalitarian allocations[END_REF] find that the solution exists under the mild assumption of weak superadditivity but is not unique in general. The outcome is therefore very sensitive to the choice of the domination criterion and, in practice, the trade-off between uniqueness and existence may lead to a dilemma.

We complement some of the findings of [START_REF] Dutta | Constrained egalitarian allocations[END_REF]. Our conclusions derive from an abstract (though not difficult!) result which underpins the structure of the S-Lorenz core. For any TU game and any ranking of players, the set of all preimputations compatible with the ranking, equipped with the Lorenz order, is a bounded join semi-lattice. Furthermore the set admits as sublattice the S-Lorenz core intersected with the region compatible with the ranking (Theorem 2). The result allows to compare easily S-Lorenz core allocations and to construct new allocations that Lorenz dominate others in the S-Lorenz core. As an immediate corollary, we obtain that the set of SCEAs is either empty or a singleton on each rank-preserving region (Corollary 1). As a by-product result, we also obtain that the set of SCEAs is finite, and what is more, the cardinality of the set can be made more precise according to the location of some SCEAs (Corollary 2). The underlying property beyond these results is that each SCEA is the Lorenz greatest element of the S-Lorenz core on the rank-preserving region of the allocation.

The note is organized as follows: Section 2 is devoted to notations and basic definitions; Section 3 presents the lattice structure result and its corollaries; in Section 4 we discuss briefly the implications of the lattice structure property; the proof of our main result, Theorem 2, is postponed to Appendix.

Preliminaries

Let N = {1, ..., n} be a finite set of players and v be a real valued function defined over the nonempty subsets of N . The pair (N, v) is called a cooperative game with transferable utility (TU game for short). A preimputation for S is a vector x ∈ R S such that i∈S x i = v(S).

Let F S be the set of preimputations of S (we use F instead of F N and preimputation instead of preimputation of N ). For each coalition S ⊆ N , a(S) := v(S)

|S| is the equal division payoff of S. Player i is at least as desirable as j in the game v, denoted by i d(v) j, if for all S ⊆ N \ {i, j}, v(S ∪ {i}) ≥ v(S ∪ {j}). Coalition S is an equity coalition if a(S) ≥ a(T ) for all T ⊆ S. A partition of S ⊆ N is a family π = {S 1 , . . . , S m } where ∪ m k=1 S k = S, and

S k ∩ S = ∅ for any k, ∈ {1 . . . , m}, k = . The set of all partitions of S is denoted P (S). A game (N, v) is weakly superadditive if, for each partition π ∈ P (N ), v(N ) ≥ m i=1 v(S i
). Let Σ be the set of all bijective functions from N to itself (an element σ ∈ Σ is a permutation of N ). We use the notation x σ to define the transformation of x according to σ, i.e. (x σ ) i = x σ(i)

for every i = 1, . . . , n.

Consider now the following domain

A ⊆ {x ∈ R T | i∈T x i = v} where T ⊆ N , |T | = t,
and v ∈ R. For any x ∈ A, x is the vector obtained by permuting the indices such that

x1 ≥ x2 ... ≥ xt . The allocation y ∈ A weakly Lorenz dominates x ∈ A, y L x, if j i=1 ȳi ≤ j i=1
xi for all j = 1, . . . , t, and Lorenz dominates x ∈ A, y L x, if the inequalities hold with at least one strict inequality for some j. Let EA be the set of allocations x ∈ A such that there is no y ∈ A that Lorenz dominates x.

Structure of the S-Lorenz core and SCEAs

The Lorenz core and constrained egalitarian allocations are defined recursively by [START_REF] Dutta | The egalitarian solution and reduced game properties in convex games[END_REF]Ray (1989, 1991). An important feature of their solution is that the Lorenz criterion is part of the objectives of the whole population of players and also of any subgroup of the population taken separately. Given this consensus among the players, every coalition can still weigh on the final outcome via the threat of credible blocking (which accounts for egalitarianism). Thus it worths pointing out that the solution differs from a narrower view of egalitarianism within the core that considers simply as solution concept the Lorenz undominated allocations of the core, and where, consequently, blocking does not account for any egalitarian requirement (see, e.g., [START_REF] Arin | Lorenz undominated allocations for TU-games: The weighted coalitional Lorenz solutions[END_REF][START_REF] Arin | Egalitarian solutions in the core[END_REF][START_REF] Hougaard | On the set of Lorenz-maximal imputations in the core of a balanced game[END_REF].

The S-Lorenz core and SCEAs are defined as follows.

Definition 1 The S-Lorenz core of a singleton coalition {i} is L * ({i}) = v({i}). The S-Lorenz core of a coalition of S is then defined by:

L * (S) = x ∈ F S | there is no T ⊆ S, y ∈ EL * (T ) s.t. y i > x i ∀i ∈ T .
The set of SCEAs is EL * (N ). 2 [START_REF] Dutta | Constrained egalitarian allocations[END_REF] show that the SCEA is not always unique, contrary to the set of WCEAs, which is either empty or a singleton as shown by [START_REF] Dutta | A concept of egalitarianism under participation constraints[END_REF]. Nevertheless they alleviate this drawback by producing a set of sufficient conditions under which the locations of SCEAs can be inferred precisely (Dutta and Ray, 1991, Theorem 3). Let us recall their result. (3) N is an equity coalition. Then all SCEAs have the same Lorenz curve. 3

The conclusion of Theorem 1 has two interesting implications. First, two different SCEAs, say x and y, cannot produce the same ranking of players with respect to their payoffs since two different allocations x and y with the same Lorenz curve satisfy necessarily x i > x j and y i < y j for some i, j = 1, . . . , n. Second, the set of SCEAs is necessarily finite. We obtain those two properties, without any assumption on the TU game, as immediate corollaries of our main result.

The following example illustrates how one can even strengthen the conclusion of Theorem 1.

2 The WCEA is obtained by requiring y i ≥ x i ∀i ∈ T , with y = x, instead of y i > x i ∀i ∈ T , in the definition of the S-Lorenz core (that is, the W-Lorenz core).

3 Two allocations x and y are on the same Lorenz curve if x = ȳ.

Example 1 Consider the following example taken from Dutta and Ray (1991, Example 1) where

N = {1, 2, 3}, v(N ) = v({1, 2} = 2.2, v({1, 3} = v({2, 2}), v({1}) = v({2}) = 1, v (
{3}) = 0 (clearly the game satisfies the assumptions of Theorem 1). Then

L * (N ) = x ∈ R 3 | (x 1 ≥ 1.1, x 2 ≥ 1) or (x 1 ≥ 1, x 2 ≥ 1.1) and x 1 + x 2 + x 3 = 2.2
and EL * (N ) = {x 1 , x 2 } where x 1 = {1.1, 1, 0.1) and x 2 = (1, 1.1, 0.1). 4 One easily checks

that x 1 L x for all x ∈ L * (N ) ∩ R 1 and x 2 L x for all x ∈ L * (N ) ∩ R 2 , where R 1 = {x ∈ R 3 | x 1 ≥ x 2 ≥ x 3 } and R 2 = {x ∈ R 3 | x 2 ≥ x 1 ≥ x 3 }.
In other words, each SCEA is the (unique) greatest Lorenz element of the S-Lorenz core on the region that preserves the ranking of players it belongs to. Again, this property holds in general for any TU game and can be deduced from our main result.

We turn now to the formal statement of the announced results. First, we make precise what we mean by rank-preserving regions.

Definition 2 Given a permutation σ ∈ Σ, the rank-preserving region R σ (according to σ)

is the subset of R N defined by

R σ = {x ∈ R N | x σ(1) ≥ • • • ≥ x σ(N ) }
Two vectors x and y belong to the same region if, and only if, x, y ∈ R σ for some σ ∈ Σ.5

Let R = {R σ | σ ∈ Σ} be the family of all rank-preserving regions. First, it is an easy matter to verify that there is a bijection between R and Σ. Second, it holds that

∪ R R = R N , |R| = n! and (x, . . . , x) ∈ ∩ R R for every x ∈ R. Next, given R ∈ R, the relation L defined over F ∩ R is a partial order, in particular L is antisymmetric on F ∩ R. 6
A set P equipped with a partial order defined on P is said to be a partially ordered set (poset for short). A poset (P, ) is a join semi-lattice if for any x, y ∈ P , the least upper bound of {x, y}, denoted by x ∨ y, exists. A join sublattice of (P, ) is (M, ), with ∅ = M ⊆ P , such that x ∨ y ∈ M for any x, y ∈ M . 7

We state now the main result of the paper. Its proof is postponed to Appendix.

Theorem 2 Let (N, v) be a TU game and R ∈ R.

1. The poset L := (F ∩ R, L ) is a join semi-lattice, with greatest element the vector with components a(N ).

2. If L * (N ) ∩ R = ∅ then the poset (L * (N ) ∩ R, L ) is a join sublattice of L. 8
The proof consists in providing the algebraic definition of the least upper bound operator ∨. This operator will be defined as follows. Let x, y be two preimputations that belong to the same rank-preserving region R σ * ; define z 1 := min{x 1 , ȳ1 } and, for each i = 2, ..., n,

z i := min i j=1 xj ; i j=1 ȳj - i-1 j=1 z i .
Let x ∨ y be the vector z σ * -1 . We show through a sequence of short claims that ∨ is the least upper bound operator for the poset L := (F ∩ R, L ). In addition, we show that if

x, y ∈ L * (N ) then x ∨ y also belongs to L * (N ), that is L * (N ) ∩ R forms a join sublattice of L if L * (N ) ∩ R is nonempty. These facts will lead us to the statements 1. and 2. of Theorem 2.

The next example illustrates better how natural is the construction of the least upper bound x ∨ y, in a simple case.

Example 2 Consider Table 1 where the ordered profiles x and ȳ of seven players have been reported together with the profile z. The allocations x = (4, 0.5, 5, 4, 12, 1.5, 9) and y = (3, 0, 9, 6, 9, 0, 9) belong to a same rank-reserving region but are not Lorenz comparable.

7 See [START_REF] Davey | Introduction to lattice and order[END_REF] for more details.

8 Note that L * (N ) ∩ R is different, and a priori not comparable, from the S-Lorenz core of the game restricted to imputations F S ∩ R S for every S, where R S ∈ R S is the region preserving the ranking of players in S given by R. We have not explored further that solution.

It can be read immediately in Table 1 that the resulting allocation z σ * -1 Lorenz dominates both x and y. player payoff 5 7 3 4 1 6 2

x 12 9 5 4 4 1.5 0.5 ȳ 9 9 9 6 3 0 0 z 9 9 8 4 4 1.5 0.5

Table 1: Construction of the least upper bound x ∨ y

Remark 1 (only) From a theoretical point of view, finding the greatest lower bound operator would be of interest to define fully a lattice structure. Here the natural candidate is the following operator x ∧ y := z σ * -1 , where z 1 := max{x 1 , ȳ1 } and, for each i = 2, ..., n,

z i := max i j=1 xj ; i j=1 ȳj - i-1 j=1 z i .
But x ∧ y does not belong F ∩ R as shown in the example reported in Table 2 (with σ = Id). player payoff 1 2 3 4

x 5 5 5 0

ȳ 8 3 2 2 z 8 3 4 0 Table 2: x ∧ y does not exist in F ∩ R
As a direct consequence of Theorem 2, two Lorenz undominated allocations x, y of the S-Lorenz core cannot coexist in the same rank-preserving region. For otherwise, z constructed as above would Lorenz dominate x and y and belong to the S-Lorenz core, which cannot be the case. What is more, the unique Lorenz undominated allocation is necessarily the Lorenz greatest element of the S-Lorenz core on the region it belongs to (by using a similar argument). This leads to the following straightforward corollaries, which provide new features on the SCEAs and complements Theorem 1.

Corollary 1 Let (N, v) be a TU game. For every rank-preserving region R ∈ R, if there is

an SCEA x ∈ R then x is the greatest Lorenz element of L * (N ) ∩ R.
Hence the set of SCEAs is finite and contains at most n! elements (the number of rankpreserving regions), and even more precisely at most #{R ∈ R : L * (N ) ∩ R = ∅} elements.9

The previous statement can be reinforced if an SCEA belongs to several adjacent regions (typically if some components of the vector are equal).

Corollary 2 Let (N, v) be a TU game. If there is an SCEA x such that x ∈ ∩ T R for some subfamily T ⊆ R then x is the greatest Lorenz element of L * (N ) ∩ (∪ T R).

If the above condition is fulfilled, there are at most n! -|T | + 1 SCEAs. For the polar case T = R, the set of SCEAs is a singleton, equal to the vector with components a(N ).

Corollaries 1 and 2 are probably the most eloquent results to be deduced from Theorem 2, so we do not state any further variations in the same spirit.

Finally, note that above properties are not satisfied by the W-Lorenz core (i.e., with a weak domination relation) and the WCEAs. Dutta and Ray (1989, Example 5) construct a convex game where there exists a W-Lorenz core allocation, in the same region R as the unique WCEA, that is not Lorenz dominated by the WCEA (and thus this W-Lorenz core allocation must be Lorenz dominated by another W-Lorenz core allocation). The example is striking at first glance, but it simply says that the W-Lorenz core intersected with R, and equipped with the Lorenz order, is not a sublattice of (F ∩ R, L ).

Concluding remarks

Our main result deals with the structure of the S-Lorenz core. We did not use here any formal result of lattice theory but we have shown that embedding the S-Lorenz core into lattices leads to a better understanding of the location of these allocations. To the best of our knowledge, such feature has never been suggested before for any core-like solutions in cooperative games, except of course in the specific setting of two-sided matching models where the lattice structure of stable matchings plays a great role, (see, e.g., [START_REF] Knuth | Mariages stables et leurs relations avec d'autres problèmes combinatoires[END_REF][START_REF] Roth | Two-Sided Matching: A Study in Game-Theoretic Modelling and Analysis[END_REF]). 10

Our approach provides also a handy framework to derive qualitative properties of the SCEAs and identify better the differences between the WCEAs and SCEAS. If we follow an admitted view by comparing them in terms of qualitative properties -existence (SCEA)

versus uniqueness (WCEA) -our results show that the comparison is more puzzling than expected. 11 Indeed, on any given rank-preserving region, we have shown that the SCEA is the unique greatest Lorenz element of the S-Lorenz core, while it is known that the unique WCEA does not necessarily Lorenz dominate every other element of the W-Lorenz core (Dutta and Ray, 1989, Example 5). [START_REF] Dutta | A concept of egalitarianism under participation constraints[END_REF] obtain their main positive results for convex games à la Shapley (1971). Recall that convexity in a cooperative game simply refers to the supermodularity of the characteristic function of the game. Besides, supermodularity is also known to be the baseline for comparative statics in lattice-embedded environments (see, e.g., Milgrom andShannon, 1994, 1996). It is therefore tempting to ask how supermodularity operates with respect to the lattice framework based on the Lorenz order.

10 Grabisch and Funaki (2012) adopts the lattice framework to define a value for games in partition function form.

11 See also the discussion Dutta and Ray (1991, p.405 & 415).

Since x i ≤ x i-1 and y i ≤ y i-1 , it follows that 2 i-2 j=1 x j + x i-1 + x i ≤ 2 i-1 j=1 x j and 2 i-2 j=1 y j + y i-1 + y i ≤ i-1 j=1 y j . Therefore: (x ∨ y) i -(x ∨ y) i-1 ≤ 0.

Claim 3 if neither x L y nor y L x then x ∨ y L x and x ∨ y L y.

Proof. From the definition of ∨: for all i = 1, ..., n, i j=1 (x ∨ y) j ≤ i j=1 x j and i j=1 (x ∨ y) i ≤ i j=1 y j . Since x L y does not hold, there is k such that k j=1 xj > k j=1 y j . It follows that x ∨ y L x. The symmetric reasoning leads to the same conclusion for y.

Claim 4 x L y iff x ∨ y = x.

Proof. Obvious from the definition of Lorenz dominance and the construction of z.

Claim 5 if z L x and z L y then z x ∨ y. Proof. Suppose not then i j=1 (x ∨ y) i = min{ i j=1 x j ; i j=1 y j } < i j=1 z j for some i = 1, . . . , n, which contradicts that z L x and z L y.

The above 5 claims prove statement 1. of Theorem 2 (and observe that a N L x for every x ∈ F ).

Claim 6 (x ∨ y) i ≥ min{x i , y i }, i = 1, ..., n.

Proof. It is true for i = 1, for i ≥ 2 it suffices to remark that from the definition of (x∨y) i and (x ∨ y) i-1 , it holds that i j=1 (x ∨ y) j = min{ i j=1 x j ; i j=1 y j } ≥ min{ i-1 j=1 x j ; i-1 j=1 y j } + min{x i ; y i } = i-1 j=1 (x ∨ y) j + min{x i ; y i }. It follows that (x ∨ y) i ≥ min{x i ; y i }.

We show now the statement 2. of Theorem 2. Suppose by way of contradiction that

x, y ∈ L * (N ) ∩ R and x ∨ y / ∈ L * (N ). Dutta and Ray (1991, Theorem 1, p. 411) prove the following:

L * (N ) = {x ∈ F | for no S ⊆ N : a(S) > x i ∀i ∈ S} Hence there exists S ⊆ N such that a(S) > (x ∨ y) i for all i ∈ S. Since min{x i ; y i } ≤ (x ∨ y) i for all i ∈ N (from Claim 6), it holds that min{x i * ; y i * } ≤ (x∨y) i * for some i * such that i * ≤ j for any j ∈ S. Suppose that min{x i * ; y i * } = x i * . Then it holds that x i * ≤ (x ∨ y) i * < a(S).

Since σ * = Id, it also holds that x i < a(S) for all i ∈ S (recall that the components of the vector x are non increasing). It follows that x does not belong to L * (N ), which is a contradiction.

Theorem 1 (

 1 [START_REF] Dutta | Constrained egalitarian allocations[END_REF] Suppose (N, v) is a weakly superadditive game satisfying any one of the following conditions: (1) the relation d(v) is complete; (2) |N | ≤ 3;

The Lorenz criterion has been also appraised in other frameworks. For instance,[START_REF] Chatterjee | A noncooperative theory of coalitional bargaining[END_REF] explore the non-cooperative foundations of the egalitarian solution;[START_REF] Goel | Fair welfare maximization[END_REF] provide a fairness ratio combining egalitarianism and efficiency;[START_REF] Kets | Inequality and network structure[END_REF] study the interplay between the degree of inequality and the structure of social networks.

In general, the SCEAs do not have the same Lorenz curve (see for instanceDutta and Ray, 1991, Example 4).

Note that x belongs to the same region as y is not a transitive relation.

Lorenz relation L is only a partial preorder on F .

Using a different strategy,[START_REF] Llerena | A simple procedure for computing strong constrained egalitarian allocations[END_REF] show that the set of SCEAs is finite for any TU game.

Appendix: proof of Theorem 2

Let σ * ∈ Σ be the permutation such that x = x σ * and ȳ = y σ * for every x, y ∈ F ∩ R. Given

x, y ∈ F ∩ R, the join operator ∨ is defined recursively as follows:

where (z σ * -1 ) i := z σ * -1 (i) for every i = 1, . . . , n.

Without loss of generality, assume from now on that σ * = Id and let x, y ∈ F ∩ R be fixed once and for all in the remaining part of the proof.

Proof. From the definition of (x∨y) n , we obtain that n j=1 (x∨y

Proof. It suffices to show that, for each i = 2, ..., n, (x∨y

From the definition of x ∨ y this can be restated as:

x j ; i-2 j=1 y j } ≤ min{2 i-2 j=1 x j + x i-1 + x i ; 2 i-2 j=1 y j + y i-1 + y i } -2 min{ i-1 j=1 x j ; i-1 j=1 y j }