Relationship between the Lemma and the Theorem

Question

I am trying to understand the paper at

[Fair Online Scheduling for Selfish Jobs on Heterogeneous Machines1

Objective is to minimize total flow-time plus energy consumed It discusses a Theorem 3.1 (attached Figure ). Theorem talks about k=1/absolon and the resulting complexity is O(1/(absolon^2)).

And then they talked about the Lemma: 3.2 (attached Figure). I can’t understand the use of less than relationship in Lemma. Lemma uses k as a multiplicative term whereas in the complexity k is equal to inverse of absolon. absolon is defined as a value between zero and 1. Other term of lemma is delta(ij) which the text says as the increase of flow time but in the Lemma we are saying that delta (ij) is less than or equal to multiplication of (k+2) with the flow time of job j on machine i at the arrival time r_j represented by Fij(r_j). I think we have to use greater than relationship instead of less than relationship in the Lemma.

Somebody please guide me.

Answer 1

I am able to understand the relationship between theorem and Lemma. Theorem tells us the value of 'k' and we can use this value in the Lemma. From theorem it is clear that 'k' is greater than 1. At one place they have used the (1+absolon). That's why they are using (k+2). Now according to the text:

delta(ij) > Fij(rj)

but in the Lemma they are saying:

delta(ij) <= (k+2) Fij(j)

Which might be true.

Zulfi.