A New Class Of Combinatorial Problem Integrating Bin Packing And Network Optimization

It is known that both bin packing and network optimization are classical combinatorial optimization problems that have played an important role in Operational Research fields.With fast developments of optimization theory,fruitful theoretical results on these problems have been acquired and also they have been widely applied to many practical fields including the economic management,transportation industry,communication and network technology,and so on.In general,classical combinatorial problems are studied independently,while in this thesis we focus on a new class of combinatorial problems that integrate bin packing and network optimization problems together.Given a directed and weighted network D,it aims to find a structured subnetwork of D such that the total number of pieces of length L that are used to cut the arcs of the subnetwork in accordance with specified rules is minimized.Approximation algorithms with worst case analysis are presented in the thesis,which will be divided into four chapters.In Chapter 1,we first give the models and definitions of the classical bin packing and network optimization problems.Then we introduce the theory of computational complexity and the concepts of approximation algorithms and the(asymptotic)worst case ratios.In Chapter 2,the problems where the subnetwork is restricted to either a directed s-t path or a strongly-connected spanning subnetwork are considered.We improve the previous results on this problem by providing new algorithms with asymptotic worst case ratios of 61/36 and 61/18,respectively.Chapter 3 studies a special case in which each arc of the network has a weight no smaller than L.If the subnetwork is restricted to a s-t path,then a 4/3-approximation algorithm is designed and another algorithm with asymptotic worst case ratio 95/72 is also provided.If it is restricted to a strongly-connected spanning subnetwork,then the two corresponding bounds are shown to be 8/3 and 95/36 respectively.Finally,we give concluding remarks and the further research in Chapter 5.