Srivastav, Anand and Stangier, Peter (1995). Weighted Fractional and Integral k-Matching in Hypergraphs. Elsevier. ["eprint_fieldopt_monograph_type_preprint" not defined].

[img]
Preview
 PDF
zpr92-123.pdf
Download (258kB) | Preview

Abstract

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.

Item Type: Preprints, Working Papers or Reports (["eprint_fieldopt_monograph_type_preprint" not defined])
Creators:
CreatorsEmailORCIDORCID Put Code
Srivastav, AnandUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Stangier, PeterUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
URN: urn:nbn:de:hbz:38-546759
Journal or Publication Title: Discrete Applied Mathematics
Volume: 57
Number: 2-3
Page Range: pp. 255-269
Date: 1995
Publisher: Elsevier
Language: English
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects: Data processing Computer science
Refereed: No
URI: http://kups.ub.uni-koeln.de/id/eprint/54675

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item