0
$\begingroup$

I'm trying to solve exercise 13 from Chapter 04 of Algorithms Design (Eva Tardos) books. The problem is the following:

enter image description here

The way I solved: was to have a greedy solution, where I always choose, for an i, biggest wi*ti for the job to be added.
Moreover on the solutions: it is written that is the choice is biggest wi/ti.

For me then, to choose decreasing wi*ti or decreasing wi/ti is the same, so I continue the prove.

So for the prove:

  • I suppose a solution O with an inversion, where j is chosen before i, and I try to show that my greedy choice A (where i is chosen before j) won't augment the total weight. On this case, since O is an inversion and A is the correct choice, wi*ti <= wj*tj

So then before swap I can say the cost is: wi(ti) + wj(ti+tj) So then after swap I can say the cost is: wj(tj) + wi(tj+ti)

Then since I want the cost to be less or equal after the swap, i have after <= before which is:

  • wj(tj) + wi(tj+ti) <= wi(ti)+wj(ti+tj).
    then cutting both sides, i have

    wi*tj <= wj*ti

And then I block on my end of prove. How can I get this wi*tj <= wj*ti and prove that with my swap (where wi*ti <= wj*tj) the weight is not augmented?

$\endgroup$
3
  • 2
    $\begingroup$ I might be misunderstanding your approach, but I am not sure I understand why you claim picking the largest $w_it_i$ is equivalent to picking the largest $\frac{w_i}{t_i}$. Consider the following: $a=2$, $b=3$, $c=2$, and $d=4$. We then have $ab \leq cd$, which is $2 \times 3 \leq 2 \times 4$. However, it is not true that $\frac{a}{b} \leq \frac{c}{d}$. $\endgroup$ Commented Apr 15 at 15:35
  • $\begingroup$ Oh, I had not thought on that :( You are right, thanks! But on this case, choosing, wj/ti as the greedy approach, for the prove I will arrive in wi/tj <= wj/ti. How can I get this, and from the hipothesis 𝑤𝑖/𝑡𝑖 <= 𝑤j/𝑡j arrive in a conclusion? $\endgroup$ Commented Apr 15 at 16:03
  • 1
    $\begingroup$ I recommend you start by validating your greedy approach with random testing, before trying to prove it correct. See cs.stackexchange.com/q/59964/755 $\endgroup$
    – D.W.
    Commented Apr 15 at 17:33

2 Answers 2

1
$\begingroup$

First, observe that completion time is cumulative. If all weights were equal, you would want to schedule jobs with a shorter completion time first. Whereas, if all completion times were equal, you would schedule them in decreasing order of their weights. Intuitively, you want to schedule those jobs earlier that have bigger weights but smaller completion time. Hence, weight (profit) per unit time should be a good selection metric.

Once you have a selection metric, check a few random instances to see if it gives an optimal result in each case. The main challenge is then to formally prove the optimality of the greedy strategy. In most cases, exchange argument works. I hope this helps.

$\endgroup$
2
$\begingroup$

Imagine one of your customers is a company with ten departments. They are huge, so the weight and the time for their job are huge. If you split their order into ten departments then each has one tenth of the weight and execution time. Scheduling these ten departments in the same time slot should make no difference.

Your algorithm however puts these ten jobs to the end of the queue. Prioritising jobs based on w_i / t_I avoids that.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.