Near approximation of maximum weight matching through efficient weight reduction

Andrzej Lingas, Cui Di

Let G be an edge-weighted hypergraph on n vertices, m edges of size \le s, where the edges have real weights in an interval [1,W]. We show that if we can approximate a maximum weig…