I've read about the reduction from $2$-partition for the problem of minimizing weighted completion time with release dates but I'm not very experienced in doing reductions so I want to verify that my understanding is at least in the right direction.

First, my understanding of the problem is that we would like to complete the jobs that have high weight the earliest possible, but since there isn't any preemption and given the release dates it's hard to figure out which jobs to do first.

So in order to prove $NP$-hardness in the weak sense, I construct an instance of $2$-partition as follows,

set task weights to $1$, set $r_j = 0$ for all tasks and add an extra task with $r_j = B$, and deadline $B+1$ and a processing time of $1$, weight $0$. We add this task to split the two subsets(as required by $2$-partition). Therefore if we can solve this problem in polynomial time we can also solve $2$-partition in polynomial time.

Is my intuition correct? Also I don't expect an answer, just maybe an explanation of what I'm doing wrong

  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Jun 27 '18 at 21:49
  • $\begingroup$ The way to tell whether your answer is correct is to write it out in full detail and prove it correct. Is there any specific step in your solution that you are unsure about? $\endgroup$ – D.W. Jun 27 '18 at 21:50

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.