SEMI-DEFINITE RELAXATION ALGORITHM OF MULTIPLE KNAPSACK PROBLEM

The multiple knapsack problem denoted by MKP (B,S,m,n) can be defined as fol- lows.A set B of n items and a set Sof m knapsacks are given such thateach item j has a profit pjand weightwj,and each knapsack i has a capacity Ci.The goal is to find a subset of items of maximum profit such that they have a feasible packing in the knapsacks.MKP(B,S,m,n) is strongly NP- Complete and no polynomial- time approximation algorithm can have an approxima- tion ratio better than0 .5 .In the last ten years,semi- definite programming has been empolyed to solve some combinatorial problems successfully.This paper firstly presents a semi- definite re- laxation algorithm (MKPS) for MKP (B,S,m,n) .It is proved that MKPS have a approxima- tion ratio better than 0 .5 for a subclass of MKP (B,S,m,n) with n≤ 1 0 0 ,m≤ 5 and maxnj=1{ wj} minmi=1{ Ci} ≤ 2 3 .

GPS： a constraint-based gene position procurement in chromosome for solving large-scale multiobjective multiple knapsack problems

The multiple knapsack problem （MKP） forms a base for resolving many real-life problems. This has also been considered with multiple objectives in genetic algorithms （GAs） for proving its efficiency. GAs use self- adaptability to effectively solve complex problems with constraints, but in certain cases, self-adaptability fails by converging toward an infeasible region. This pitfall can be resolved by using different existing repairing techniques; however, this cannot assure convergence toward attaining the optimal solution. To overcome this issue, gene position-based suppression （GPS） has been modeled and embedded as a new phase in a classical GA. This phase works on the genes of a newly generated individual after the recombination phase to retain the solution vector within its feasible region and to im- prove the solution vector to attain the optimal solution. Genes holding the highest expressibility are reserved into a subset, as the best genes identified from the current individuals by re- placing the weaker genes from the subset. This subset is used by the next generated individual to improve the solution vec- tor and to retain the best genes of the individuals. Each gene＇s positional point and its genotype exposure for each region in an environment are used to fit the best unique genes. Further, suppression of expression in conflicting gene＇s relies on the requirement toward the level of exposure in the environment or in eliminating the duplicate genes from the environment.The MKP benchmark instances from the OR-library are taken for the experiment to test the new model. The outcome por- trays that GPS in a classical GA is superior in most of the cases compared to the other existing repairing techniques.

Efficient Multi-Tenant Virtual Machine Allocation in Cloud Data Centers

Virtual Machine（VM） allocation for multiple tenants is an important and challenging problem to provide efficient infrastructure services in cloud data centers. Tenants run applications on their allocated VMs, and the network distance between a tenant＇s VMs may considerably impact the tenant＇s Quality of Service（Qo S）. In this study, we define and formulate the multi-tenant VM allocation problem in cloud data centers, considering the VM requirements of different tenants, and introducing the allocation goal of minimizing the sum of the VMs＇ network diameters of all tenants. Then, we propose a Layered Progressive resource allocation algorithm for multi-tenant cloud data centers based on the Multiple Knapsack Problem（LP-MKP）. The LP-MKP algorithm uses a multi-stage layered progressive method for multi-tenant VM allocation and efficiently handles unprocessed tenants at each stage. This reduces resource fragmentation in cloud data centers, decreases the differences in the Qo S among tenants, and improves tenants＇ overall Qo S in cloud data centers. We perform experiments to evaluate the LP-MKP algorithm and demonstrate that it can provide significant gains over other allocation algorithms.