Show that Q2 || Cmax is NP-hard by giving a polynomial-time reduction from PARTI

Question

Show that Q2 || Cmax is NP-hard by giving a polynomial-time reduction from PARTITION to the Decision Version of Q2 || Cmax. Definitions of PARTITION and Decision Version of O_2 || Cmax are given as follows. Given: A list A = (a_1, a_2, .., a_k) of k integers. Question: Can A be partitioned into A_1 and A_2 such that Sigma_(aj elementof A1) a_j = sigma_(aj elementof A2) a_j = 1/2 Sigma_(i=1 to n) a_i? Given: A set of n independent jobs, {J_1, J_2, .... J_n}. Each job J_1 has a processing time p_1. 2 uniform and parallel machines. M_1 and M_2, with speed of s_1 and s_2 respectively. That is, it will take pi/s1 amount of time to finish Job J_i using machine M_1 and it will take pi/s_2 amount of time to finish Job J_i using machine M_2. A threshold T. Question: Is there a non-preemptive schedule on 2 uniform and parallel machines such that Cmax lessthanorequalto T?

Explanation / Answer

Understanding the partition problem is very important to solve the decision version problem. Once we understand the mechanism behind the partition problem,
we can create an analogous solution to the machine problem.
Partition problem states that given a set of integers in an array, divide the elements in two sets (S1 and S2) such that the sum of the elements in S1 equals to
the sum of elements in S2. This is a NP-Complete problem. But the optimized version of this problem is to minimize the difference between the sum of the elements in S1
and S2 (in some cases difference is 0) thereby making the partition problem as NP-Hard. The solution provided is pseudo-polynomial time dynamic programming solution.

Recursive Algorithm:-
* We will try to find a set S1 and insert elements from S such that the sum of elements in S1 equals to half S/2.
* Initialize two empty sets S1 and S2.
* Navigate through the given tasks in S. Each task in S has two choices. Either it will go to S1 and S2.
* Add each task recursively to each set and see if the final difference between the sums of S1 and S2 has been minimized or not.

int SumS=sum of elements in S
int *diff=INT_MAX;

void foo(int[] S, int n, int index, int[] S1, sum, int* diff)
{
   if(index==n)
   {
       if(sum-SumS<*diff)
       {  
           *diff=sum-SumS; //update to minimize the difference if we have reached the end of the array
           return;
       }
   }
   for(int i=index; i<n; i++)
   {
       sum+=S[i]; //allocation of ith element to S1 and updating the sum
       S1[i]=S[i];
       foo(S, n, i+1, S1[i], sum, *diff); //calling for rest of the elements
       sum-=S[i]; //deallocation of the ith element from S1 and updating the sum
       S1[i]=0;
       foo(S, n, i+1, S1[i], sum, *diff); //calling for rest of the elements
   }
}

As you can see the problem can be subdivided into subproblems, hence we can use dynamic programming to solve the problem in polynomial time.
We will solve the machine allocation problem using dynamic programming.

fooDP[x, y] returns true if there exists a set of elements S upto yth index such that the sum of those elements equal to/less than x.
Since we want to allocate the work between two machines such that the time is less than threshold t, we will find for fooDP[t, n] (n=number of elements in S)

bool findPartition(int[] jobs, int[] processing-time, int speed1, int speed2)
{
   bool fooDP[T+1][y+1];
   for(int i=0; i<T+1; i++)
   {
       for(int j=0; j<y+1; j++)
       {
           if(j==0)
               fooDP[i][j]=false;
           if(i==0)
               fooDP[i][j]=true; // we can allocate machines in such a way that total time is 0 for tasks equal to 0.
           else if(i-S[j-1]>0) //if the threshold is less the time taken by the jth task of S
           {
               fooDP[i][j]=fooDP[i-processing-time[j-1]/s1][j-1] || fooDP[i-processing-time[j-1]/s2][j-1];
               /* check for the two possiblities.
               1. Allocate the th job to machine 1.
               2. allocate the ith job to machine 2.
               If it returns true for any of the two cases, then fooDP[i][j]=true;
           }
           else
               fooDP[i][j]=fooDP[i][j-1];
       }
   }
   return fooDP[T][y];
}

*NOTE:- this function returns only if it is possible to schedule the jobs between the two machines to keep it under threshold.
if you need to know the job allocation as well, you need to backtrack from (x,y) index and go up to (0,0) keeping the record of job allocation

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.