The Project consists in the study of ``Packing and Partitioning Problems in Graphs and Hypergraphs''. We call graph partitioning problems those problems in which the instance consists of a graph, say G, with weights assigned to its edges, and the objective is to find a partition of the vertex set of G - satisfying certains restrictions - so as to minimize the sum of the weights of the edges whose ends lie in distinct subsets of the partition. According to the restrictions imposed on the desired partition, different versions of these problems are obtained, a number of which have already been treated in the literature ([1, 2, 3, 4, 6, 7, 14, 15, 23, 25]). In the case of hypergraphs, these problems are defined analogously.
Our objective is to continue the research that has been done by the participants of this Project ([9, 10, 14, 15]), in special on the use of polyhedral combinatorics methods in the treatment of these types of problems. Making use of these methods, we hope to obtain interesting theoretical results concerning the polyhedra that are associated with the problems under consideration, and also design algorithms based in these results that might be very useful from the practical point of view.
As far as the Packing Problems, we intend to continue the research that we have been done in the tridimensional packing problem which consists in finding a packing of a list of (small) boxes in a (large) box, so as to minimize the height of the packing. We have obtained some preliminary results and proposed new approximation algorithms whose asymptotic performance we have been able to prove to be better than those of the other algorithms so far mentioned in the literature ([5, 17, 19]).