Research And Application Of Measure And Conquer In Set Packing

NP-complexity theory is the most important basic theory in the fieldof algorithm research, which has great important status in the field ofcomputer, electrical engineering and operational research.In this paper,we study problems of this class on the basis of algorithm technology, withthe hope that we can have some new breakthrough in the ways of solvingthose problems.The measure and conquer technique, a new way for analyzingalgorithms, was first introduced by F. V. Fomin. This approach is basedon the choice of the measure of the sub-problem recursively generated bythe algorithm considered, in order to obtain the best running time in worstcase. It adopt quasi-convex programming to determine each weight inmeasure and conquer, which makes the time complicacy is minimum. Wealso give a new measure which uses evolutionary algorithm to determinethe weight function yielding the smallest upper bound, and to make sureweight.We further research the Set Packing problem by application scope ofmeasure and conquer. According to the differences of the concernedproblem, we divide the set packing problem into five classes and give thecorresponding definition. This paper gives a detailed presentation of allthe current algorithms for the problems of the five classes, and putsemphasis on the analysis and comparison of the technique used in thoseparameterized algorithms. At last, we present some developmentorientation in algorithm research for the set packing problem.The measure and conquer reduce running time via a more carefulchoice of the measure without modifying the algorithm. In this paper, the"measure and conquer" method is used to analyze a very simplebacktracking algorithm for the problem which has the instance of nsubsets and N elements. We still convert it into the maximum independentset and introduce the size of universe of elements. It is not expected to beseen when convert the GSP problem into the maximum independent set,and its running time is O^*(1.1686^n+N). When N≤n/4, it is more efficientthan the present best algorithm O^*(1.2209ⁿ).