WEIGHTED FRACTIONAL AND INTEGRAL KAPPA-MATCHING IN HYPERGRAPHS

We consider the problem of finding polynomial-time approximations of m aximal weighted k-matchings in a hypergraph and investigate the relati onship between the integral and fractional maxima of the corresponding 0-1 integer linear program and its LP-relaxation. We extend results o f Raghavan, who gave a deterministic approximation algorithm for unwei ghted k-matching, to the weighted case and compare the so obtained low er bound for the ratio of the integer and fractional maximum with a lo wer bound of Aharoni et al. (1985) and Alon et al. (1992).