Study Of The Multiple Knapsack Problem With Restriction

Knapsack problem is one of the most active and important problems in com-binatorial optimization. Knapsack problem and all kinds of its general and variant problems are hot issues in recent years. The classical knapsack problem and its general problems are NP-hard with some practical applications in the allocation of storage space, project selection, cutting and so on.We study some variants of the knapsack problem, and then design some ap-proximation algorithms or optimal algorithms to solve the related problems.This dissertation is divided into seven chapters:Chapter 1 introduces the background of graph theory and operations research, the knapsack problem, and the main results that we obtain in this dissertation.Chapter 2 introduces the basic concepts of graph theory and combinatorial optimization, then describes some relative optimization problems.Chapter 3 introduces some basic knowledge of matching, especially the basic strategy of the Hungarian algorithm. Then design an optimal algorithm for the k matching problem in general graphs, which run in the time O(n3), where n is the number of vertices.In Chapter 4, we consider the general multiple knapsack problem with k ele-ments restriction (k-GMK, for short). For different objectives, we study the Max-Sum k-GMK problem and the Max-Min k-GMK problem, respectively. Both these two problems are NP-hard. We design a^-approximation algorithm for the Max-Sum k-GMK problem (k≥ 4), and a1/k-1-approximation algorithm for the Max-Min k-GMK problem (k≥ 4), respectively. We present two optimal algorithms for these two problems when k= 2, that run in times O(n4) and O(n1/2m2), respectively, where n is the number of items, m is the number of knapsacks.In Chapter 5, we consider the multiple knapsack problem with k elements re-striction in graph (k-MKRG. for short). For different objectives, we study the Max-Sum k-MKRG problem and the Max-Min k-MKRG problem, respectively. These two problems are NP-hard when k≥ 2. We design two 1/2-approximation algorithms for each of the problem when k= 2.In Chapter 6, we consider a special version of the k-MKRG problem called k-UKRG problem, where each knapsack has the same capacity. For different objec-tives, we study the Max-Sum k-UKRG problem and the Max-Min k-UKRG problem, respectively. These problems are NP-hard. We design two 2/3aapproximation algo-rithms for each problem when k= 3. We present two optimal algorithms for the two problems when k= 2, that run in times O(n3) and O(n(|E|+nlog n)log n), respectively, where n is the number of items, E is the edge set of restriction graph.In Chapter 7, we give the conclusions and propose some further work in future.