Weighted Fractional and Integral k-Matching in Hypergraphs
We consider the problem of finding polynomial-time approximations of maximal weighted k-matchings in a hypergraph and investigate the relationship between the integral and fractional maxima of the corresponding 0-1 integer linear program and its LP-relaxation. We extend results of Raghavan, who gave a deterministic approximation algorithm for unweighted k-matching, to the weighted case and compare the so obtained lower bound for the ratio of the integer and fractional maximum with a lower bound of Aharoni, Erdös and Linial.
|Depositing User:||Archive Admin|
|Date Deposited:||02 Apr 2001 00:00|
|Last Modified:||19 Jan 2012 11:02|