Take the 2-minute tour ×

I'm given the following problem:

Prove that single machine \sum U_i (number of tardy job) with release date constraints problem can reduce from 2-partition problem

I'm clueless, where should I begin?

share|improve this question
What does "single machine $\sum U_i$ (number of tardy job)" mean? It's not even correct English. –  trutheality Jun 14 '11 at 17:05
where should I begin? The usual first steps are 1: understand what you are being asked; 2: formulate your question so that others can also understand it. You have't done step 2 (perhaps neither 1?) –  leonbloy Jun 14 '11 at 17:29
You should begin by studying Garey & Johnson: amazon.com/… More specifically, there are many reductions demonstrated in that text and it remains a classic after 30 years for a reason. –  mhum Jun 15 '11 at 5:22
add comment

Your Answer



Browse other questions tagged or ask your own question.