Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.