Weighted fractional and integral \(k\)-matching in hypergraphs (Q1346702)

It is well-known that the problem of maximum \(K\)-matching in a weighted hypergraph is strongly NP-hard, i.e. it is most unlikely that a fully polynomial approximation algorithm for solving it exists. The main result of the paper is the following: Let the edge weights be rational numbers in \([0, i]\). If \(K\geq 24\ln(n/\varepsilon^ 2)\) and every \(k\) edges have total weight at least \(18\varepsilon^{-2}\), then the derandomized algorithm can find a \(K\)-matching \(M\) with \(M\geq (1- \varepsilon) M_{\text{opt}}\) in \(O(m^ 2+ \log m+ nm)\)-time, where \(i> \varepsilon> 0\) and \(M_{\text{opt}}\) is the weight of the optimum \(K\)- matching.