Here is a variation of a job-scheduling Problem. Let $J = \{j_1,...j_n\}$ be a set of Jobs for $1 \leq i \leq n$. Given Job length $|j_i|\in \mathbb{N}$, deadline $f_i \in \mathbb{N}$, profit $p_i \ge 0$ and starting-time $s_i \in \mathbb{N}$. I am looking for a greedy approximation factor given that the Job length may only be distinguished by factor k.

$$max_i|j_i| \leq k \cdot min_i|j_i|$$

The Greedy algorithm of this Problem is fairly stupid. Greedy takes a job with the biggest profit. I created an example (3-Job-Scheduling):

Let $J = \{j_1,j_2,j_3\}$ with $|j_1| = 2, j_2 = j_3 = 1$ and

$s_1 = 0; s_2 = 0; s_3 = 1$,

$f_1 = 2;f_2 = 1; f_3 = 2$

$p_1 = w; p_2 = p_3 = (w-1)$

What I want to show is that Greedy gives us w while 2(w-1) is the optimal solution.

My question: Is this valid for n-Job-Scheduling (the general case). Is this the worst-case?

I can't think of anything worse. So I figured since the problem is a k-Matroid (is this a common term?) there will be a an approximation factor $\frac{1}{k-\epsilon}$ for any $\epsilon > 0.$ I know this is not exactly a proof yet, but am I on the right way?

Thanks for your help!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.