Weighted Fractional and Integral k-Matching in Hypergraphs

Srivastav, Anand and Stangier, Peter (1995) Weighted Fractional and Integral k-Matching in Hypergraphs.
Published in: Discrete Applied Mathematics Vol. 57 (2-3). pp. 255-269.


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.

Download: [img] Postscript - Preprinted Version
Download (170kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr92-123
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 11:02
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/123