4

Let $K=\{1,\ldots,k\}$ be a set of $k$ jobs. Each job $j\in K$ has a positive weight $w_j$ and a positive profit $p_j$. Let $\ell^*$ be the job such that:

$$\dfrac{\sum_{j=1}^{\ell^*}w_j}{\sum_{j=1}^{\ell^*}p_j}=\max\limits_{1\leq\ell\leq k}\left(\dfrac{\sum_{j=1}^{\ell}w_j}{\sum_{j=1}^{\ell}p_j}\right).$$

The ratio on the left-hand side is called the $\rho$-factor of $K$, denoted $\rho(K)$. Job $\ell^*$ is referred to as the job that determines the $\rho$-factor of $K$.

Claim: If $\ell^*$ is the job that determines the $\rho$-factor of $K$, then for any $u\in\{1,\ldots,\ell^*-1\}$, we have: $$\dfrac{w_{u+1}+w_{u+2}+\ldots+w_{\ell^*}}{p_{u+1}+p_{u+2}+\ldots+p_{\ell^*}}>\dfrac{w_{1}+w_{2}+\ldots+w_{u}}{p_{1}+p_{2}+\ldots+p_{u}}.$$

How can I prove this claim?

zdm87
  • 99

1 Answers1

3

From the fact: if $\dfrac {a}{b}\leq\dfrac {c}{d}$ then $\dfrac {a+c}{b+d}\leq\dfrac {c}{d}$

if $\dfrac{w_{u+1}+w_{u+2}+\ldots+w_{\ell^*}}{p_{u+1}+p_{u+2}+\ldots+p_{\ell^*}}\leq\dfrac{w_{1}+w_{2}+\ldots+w_{u}}{p_{1}+p_{2}+\ldots+p_{u}}$ then,

$\dfrac{w_{1}+w_{2}+\ldots+w_{\ell^*}}{p_{1}+p_{2}+\ldots+p_{\ell^*}}\leq\dfrac{w_{1}+w_{2}+\ldots+w_{u}}{p_{1}+p_{2}+\ldots+p_{u}}$

But this contradicts with the maximality of $\dfrac{\sum_{j=1}^{\ell^*}w_j}{\sum_{j=1}^{\ell^*}p_j}$

Actually, equality case might not be thought as a contradiction. However, if we chose ${\ell^*}$ such that ${\ell^*}$ is minimum that satisfies $\dfrac{\sum_{j=1}^{\ell^*}w_j}{\sum_{j=1}^{\ell^*}p_j}=\max\limits_{1\leq\ell\leq k}\left(\dfrac{\sum_{j=1}^{\ell}w_j}{\sum_{j=1}^{\ell}p_j}\right)$ ,then it's certainly a contradiction.

Merdanov
  • 1,222
  • Thank you. But we want to prove the fact, how would you use it? – zdm87 Jun 07 '17 at 15:59
  • When we had the contradiction, it meant we have proved that inequality is satisfied in other direction which is what we want. Am I wrong? – Merdanov Jun 08 '17 at 01:24
  • But why did you use the fact in your first line? – zdm87 Jun 08 '17 at 17:04
  • Because if $\dfrac{w_{u+1}+w_{u+2}+\ldots+w_{\ell^}}{p_{u+1}+p_{u+2}+\ldots+p_{\ell^}}\leq\dfrac{w_{1}+w_{2}+\ldots+w_{u}}{p_{1}+p_{2}+\ldots+p_{u}}$ were true, then $\dfrac{w_{1}+w_{2}+\ldots+w_{u+1}+w_{u+2}+\ldots+w_{\ell^}}{p_{1}+p_{2}+\ldots+p_{u+1}+p_{u+2}+\ldots+p_{\ell^}}\leq\dfrac{w_{1}+w_{2}+\ldots+w_{u}}{p_{1}+p_{2}+\ldots+p_{u}}$ – Merdanov Jun 08 '17 at 17:08
  • You said, if $\dfrac {a}{b}\leq\dfrac {c}{d}$, then $\dfrac {a+c}{b+d}\leq\dfrac {c}{d}$. I don't understand why this is true. – zdm87 Jun 08 '17 at 17:09
  • okey, $\dfrac {a}{b}\leq\dfrac {c}{d}$ iff $ad \leq bc$ iff $ad+dc \leq bc+dc$ iff $\dfrac {a+c}{b+d}\leq\dfrac {c}{d}$ – Merdanov Jun 08 '17 at 17:12
  • Great. Thank you again. – zdm87 Jun 08 '17 at 17:15