Packing theorems in graph theory and packing integer programs.

摘要

In this thesis we consider three different problems.; Paul Erdo&huml;s conjectured that a graph on dn vertices, each with degree at least d(n - 1), contains d vertex-disjoint complete subgraphs of size n each. In 1970, A. Hajnal and E. Szemeredi gave a proof of this conjecture. Our first contribution is a polynomial-time algorithm for solving this problem, which also yields a much simpler proof.; We also consider a generalization of the above problem for multipartite graphs. Let G be a balanced q-partite graph on qn vertices, where q is bounded and n is large enough. In addition, assume that each vertex of G is adjacent to at least (k/(k + 1) + c)n vertices in every other vertex class, c being a positive real number. Then G has a Kq-factor.; In the third part we consider a tree network T = ( V,E), where each edge e has some integer capacity ue. We are given requests for capacity in T, each consisting of an integer demand df and a profit wf which is obtained if the request is satisfied. The objective is to find a set of demands that can be feasibly routed in the tree and which maximize profit. This generalizes well-known problems including the knapsack and b-matching problems.; When all demands are 1, we have the integer multicommodity flow problem, which was shown to be NP-hard. We establish that the natural linear programming relaxation has a constant factor gap, a factor of 4, for the case of arbitrary profits.; We then discuss the situation for arbitrary demands. When the maximum demand dmax is at most the minimum edge capacity umin, we show that the integrality gap of the LP is at most 48. This result is obtained by showing that the integrality gap for the demand version of such a problem is at most 12 times that for the unit demand case. We use techniques of Kolliopoulos and Stein to obtain this. We also obtain, via this method, improved algorithms for the line and ring networks. Applications and connections to other combinatorial problems are discussed. Moreover, we describe a general method for solving such demand problems based on cutting plane approaches to their unit demand versions.