Note that the expurgated allocations in the second step (if any) necessarily do not belong to TP b$_{2}$ . Together, the area covered by the expurgated slope values in the first and second step represent a loss. Further, invoking (29) (for b = b$_{2}$ ) proved in Lemma 1 we see that the replacing of slope values if done in the third step certainly results in an improvement. On the other hand, by construction the replacing of slope values if done in the fourth step results in an improvement. Let us now proceed to prove (32). Towards this end, let Δ$_{b}$$_{2}$ = ∑ b ∈B ′ 1 ¯ h ( ˜ Γ$_{b}$ , b ) − ∑ b ∈B ′ 1 ¯ h ( ˘ Γ$_{b}$ , b ) and let Ψ$_{b}$$_{2}$ denote the total macro resource assigned as slack to TP b$_{2}$ under ˘ Γ . Following Algorithm I we note that S ( Z, ˜ Γ ) , ∀ Z ∈ [ ∑ b ∈B ′ 1 ¯ h ( ˜ Γ$_{b}$ , b ) , ˜ Γ + δ ] can be obtained from S ( Z, ˘ Γ ) , ∀ Z ∈ [ ∑ b ∈B ′ 1 ¯ h ( ˘ Γ$_{b}$ , b ) , ˜ Γ + δ ] by performing the following steps: Let us apply the same procedure to obtain S ( Z, Γ ) , ∀ Z ∈ [ ∑ b ∈B ′ 1 ¯ h (Γ$_{b}$ , b ) , Γ ] from S ( Z, ˜ Γ ) , ∀ Z ∈ [ ∑ b ∈B ′ 1 ¯ h ( ˜ Γ$_{b}$ , b ) , Γ ] and to obtain S ( Z, ˆ Γ ) , ∀ Z ∈ [ ∑ b ∈B ′ 1 ¯ h ( ˆ Γ$_{b}$ , b ) , ˜ Γ ] from S ( Z, ˘ Γ ) , ∀ Z ∈ [ ∑ b ∈B ′ 1 ¯ h ( ˘ Γ$_{b}$ , b ) , ˜ Γ $^{]}$, where we define ˆ Γ = Γ + δ$_{b}$$_{2}$ e$_{b}$$_{2}$ . In either case the net loss is equal to H ( ˜ Γ$_{b}$$_{1}$ , b$_{1}$ ) − H (Γ$_{b}$$_{1}$ , b$_{1}$ ) plus the loss of the first two steps and minus the improvement of the last two steps. Now, to see that the relation in (32) holds, we can ignore the common term H ( ˜ Γ$_{b}$$_{1}$ , b$_{1}$ ) − H (Γ$_{b}$$_{1}$ , b$_{1}$ ) and first verify that the loss (or area under the expurgated slope values) when obtaining S ( Z, Γ ) , ∀ Z ∈ [ ∑ b ∈B ′ 1 ¯ h (Γ$_{b}$ , b ) , Γ ] from S ( Z, ˜ Γ ) , ∀ Z ∈ [ ∑ b ∈B ′ 1 ¯ h ( ˜ Γ$_{b}$ , b ) , Γ ] is at least as large as the loss on obtaining S ( Z, ˆ Γ ) , ∀ Z ∈ [ ∑ b ∈B ′ 1 ¯ h ( ˆ Γ$_{b}$ , b ) , ˜ Γ ] from S ( Z, ˘ Γ ) , ∀ Z ∈ [ ∑ b ∈B ′ 1 ¯ h ( ˘ Γ$_{b}$ , b ) , ˜ Γ $^{]}$. This is because the expurgated slope values in the former case are at least as large, whereas the width (or the macro resource spanned under the expurgated • Expurgate Macro allocations to TP b$_{2}$ without leaving any holes (i.e., an allocation to TP b$_{2}$ is expurgated only after all preceding allocations to TP b$_{2}$ have been expurgated) such that the width of those expurgated allocations equals min { Ψ$_{b}$$_{2}$ , Δ$_{b}$$_{2}$ } . • If Ψ$_{b}$$_{2}$ < Δ$_{b}$$_{2}$ , then expurgate the allocations corresponding to Z ∈ [ ˜ Γ + δ − (Δ$_{b}$$_{2}$ − Ψ$_{b}$$_{2}$) , ˜ Γ + δ ] . • If Ψ$_{b}$$_{2}$ ≥ Δ$_{b}$$_{2}$ , then replace slope values of all remaining allocations to TP b$_{2}$ (with width Ψ$_{b}$$_{2}$ − Δ$_{b}$$_{2}$ ) using values (in order) from S ( Z$_{b}$$_{2}$, ˜ Γ$_{b}$$_{2}$ , b$_{2}$ ) , Z$_{b}$$_{2}$ ≥ ¯ h ( ˜ Γ$_{b}$$_{2}$ , b$_{2}$ ) . • Using values (in order) from S ( Z$_{b}$$_{2}$, ˜ Γ$_{b}$$_{2}$ , b$_{2}$ ) , Z$_{b}$$_{2}$ ≥ ¯ h ( ˜ Γ$_{b}$$_{2}$ , b$_{2}$ ) + (Ψ$_{b}$$_{2}$ − Δ$_{b}$$_{2}$) + replace lower slope values (if possible) corresponding to allocations other than TP b$_{2}$ , where ( x ) + = max { 0 , x } , ∀ x ∈ I R .