Weighted fractional and integral k-matching in hypergraphs

Weighted fractional and integral k-matching in hypergraphs

0.00 Avg rating0 Votes
Article ID: iaor19971074
Country: Netherlands
Volume: 57
Issue: 2/3
Start Page Number: 255
End Page Number: 269
Publication Date: Feb 1995
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: graphs
Abstract:

The authors 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. They 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 et al. and Alon et al.

Reviews

Required fields are marked *. Your email address will not be published.