China
Africa
Explore chapters and articles related to this topic
Introduction
Published in Joseph Y.-T. Leung, Handbook of SCHEDULING, 2004
To establish that the minimum makespan open shop nonpreemptive scheduling problem is NP-hard, Gonzalez and Sahni [1] reduced the partition problem to three machine problem instances ( O3∥Cmax ). Given n objects denoted by a1,a2,…,an and a size or weight function s:a→I+the partition problem is to determine whether or not the set A can be partitioned into two sets, A1 and A2, such that the sum of the weight (or size) of the objects in each set is equal to T/2, where T=∑sai.
An integer linear programing approach to find trend-robust run orders of experimental designs
Published in Journal of Quality Technology, 2019
Our solution approach is based on the 1-norm minimization. To show that this problem is non-deterministic polynomial-time hard, or NP hard, we show how another NP-hard problem naturally reduces to the 1-norm minimization. NP hardness is a property introduced by Cook (1971) that defines a class of problems characterized by their intractability. Consider an arbitrary design with model matrix X and a set of covariates contained in the matrix Z. It is straightforward to see that the partition problem (see Garey and Johnson 1979, 223) reduces to our integer optimization problem. Given a set of integers, the partition problem looks for two subsets such that the sum of the elements in each subset is equal. This problem is known to be NP hard, also when those subsets are of equal size. To see the reduction, consider a matrix X that has only one column containing an equal number of +1’s and –1’s. We include the elements of the partition set in the column vector Z. Then, if equals zero, we have found a solution to the partition problem. Therefore, in general, our mixed integer problem is NP hard, so our optimization algorithm based on integer programing techniques is justified.
A geo-aware server assignment problem for mobile edge computing
Published in International Journal of Parallel, Emergent and Distributed Systems, 2020
Consider a simple configuration of our problem: for all except for i=j, and for all . Then, it is easy to see that Because SPREAD is a constant, we can choose any locations to place the servers. Given these server locations, what remains is to minimize COST, This minimization is NP-hard because we show below that an algorithm for it can be used to solve the optimisation version of the partition problem, which is known to be NP-hard: partition a given set of positive integers, , into two subsets such that the respective subset sums differ the least. To reduce to our problem, consider servers and cells with , and let . Suppose that an optimal COST solution, , assigns a cellset to server 1 and a cellset to server 2. Without loss of generality, let . The corresponding COST is There are two cases. First, if , then partition is optimal for the partition problem because the subset sums are identical. Second, in the otherwise case, , partition is optimal for the partition problem because no partition can offer a smaller subset sum difference, Indeed, suppose by contradiction that this partition exists. Without loss of generality, let ; hence, we must have . Then, if we assign to server 1 and to server 2, COST will be This is contradictory to the assumption that is the optimal COST solution.