How to generate an instance for an NP_hard proof, where each element has two inputs? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-22T00:12:46Z https://cs.stackexchange.com/feeds/question/102243 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/102243 1 How to generate an instance for an NP_hard proof, where each element has two inputs? Mostafa https://cs.stackexchange.com/users/95193 2019-01-01T12:23:15Z 2019-02-01T02:00:40Z <p>I want to prove the NP-hardness of an scheduling problem. The problem seems to be NP-hard in the ordinary sense, so I am trying with the Partition Problem, precisely the Equal Cardinality Partition (ECP). So we have:</p> <p><strong>(ECP):</strong> Let <span class="math-container">$X = \{x_1, x_2, \dots, x_{2n}\}$</span> be a set of positive integers, does there exist a partition of <span class="math-container">$X$</span> into two subsets <span class="math-container">$X_1$</span> and <span class="math-container">$X_2$</span>, such that <span class="math-container">$\sum_{x_i \in X_1}x_i = \sum_{x_i \in X_2}x_i = B$</span>, where <span class="math-container">$B$</span> is a positive integer, and such that <span class="math-container">$|X_1|=|X_2|$</span>?</p> <p>The inputs for my scheduling problem are a set of <span class="math-container">$n$</span> jobs, where each job has a processing time <span class="math-container">$p_i$</span> and a due date <span class="math-container">$d_i$</span>. So, my instance has jobs where processing times are linked to the integers from the Partition problem, i.e. <span class="math-container">$p_i=x_i$</span>.</p> <p>The issue that I have is this: If I assign a common due date for all jobs, i.e. <span class="math-container">$d_i=d$</span>, then the problem is not NP-hard. So, how I can generate the instance with non-equal due dates? For example, can I use the same integers <span class="math-container">$x_i$</span> for the due dates (e.g. <span class="math-container">$d_i=B-x_i$</span>)? Is it Ok if I use the job <em>id</em> (<span class="math-container">$i$</span>) in the due dates (e.g. <span class="math-container">$d_i=B-2i^2$</span>)?</p> <p>p.s. I realized that I cannot use the <span class="math-container">$x_i$</span> of one job in the due date of another job, as then those jobs will be related to each other thai is not correct. Actually, that makes even very simple problems to be NP-hard.</p> https://cs.stackexchange.com/questions/102243/-/102247#102247 1 Answer by Pål GD for How to generate an instance for an NP_hard proof, where each element has two inputs? Pål GD https://cs.stackexchange.com/users/4249 2019-01-01T14:37:50Z 2019-01-01T14:37:50Z <p>As you noted yourself, the problem in general is NP-hard. You can reduce from Partition by letting due date <span class="math-container">$d = B = (\sum X)/2$</span>, where <span class="math-container">$X$</span> is the input to Partition, and let there be two processes.</p> <p>The proof is quite straight forward and left as an exercise.</p> https://cs.stackexchange.com/questions/102243/-/102266#102266 0 Answer by Mostafa for How to generate an instance for an NP_hard proof, where each element has two inputs? Mostafa https://cs.stackexchange.com/users/95193 2019-01-02T00:23:28Z 2019-01-02T01:53:07Z <p>So, let resolve the issue with this problem first.</p> <p>The single machine scheduling problem is considered. There is a set of jobs <span class="math-container">$J=\{J_1,J_2,...,J_n\}$</span>, each job has a processing time <span class="math-container">$p_i$</span> and a due date <span class="math-container">$d_i$</span>. Lateness of a job is <span class="math-container">$L_i=C_i-d_i$</span>, where <span class="math-container">$C_i$</span> is the completion time of the job. The problem is to minimize the maximum lateness <span class="math-container">$L_{max}$</span>.</p> <p>We know that this problem can be polynomially solved with sequencing jobs in EDD (Earliest Due Date). However, I have a reduction from the ECP to this problem. That means my reduction is not correct, because if it is true, then the problem should be NP_hard, while it is not.</p> <p>The ECP problem is defined above, and here is the instance of the scheduling problem.</p> <p>There is a set <span class="math-container">$J$</span> of <span class="math-container">$2n$</span> jobs that can be partitioned into two subsets: <span class="math-container">$J_1=\{J_i|p_i=x_i, d_i=B\}$</span> and <span class="math-container">$J_2=\{J_i|p_i=2x_i, d_i=3B\}$</span>. Does there exists a schedule with <span class="math-container">$L_{max}&lt;=0$</span>? </p> <p>If the ECP has a solution, then we can use elements of <span class="math-container">$X_1$</span> in <span class="math-container">$J_1$</span> and elements of <span class="math-container">$X_2$</span> in <span class="math-container">$J_2$</span> and the problem has a solution. And if ECP does not have a solution, (e.g. <span class="math-container">$\sum X_1=B-1$</span>, or <span class="math-container">$\sum X_1 = B+1$</span>), then the scheduling problem does not have a solution as well.</p> <p>So this reduction seems correct to me. However, something must be wrong as the considered scheduling problem is <strong>not</strong> NP-hard. What is my mistake?</p>