2
$\begingroup$

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!

$\endgroup$

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.