Near Approximation of Maximum Weight Matching through Efficient Weight Reduction

摘要

Let G be an edge-weighted hypergraph on n vertices, m edges of size ≤ s, where the edges have real weights in an interval [1, W. We show that if we can approximate a maximum weight matching in G within factor α in time T{n, m, W) then we can find a matching of weight at least (α - e) times the maximum weight of a matching in G in time (∈~(-1)~(O(1))× max_(1≤q≤O(∈ log n/∈/log ∈~(-1)) max _(m_1+...m_q=m∑_1~q T(min{n,sm_j},m_j,(∈~(-1))~(O(∈~(-1))). We obtain our result by an approximate reduction of the original problem to O(∈ log n/∈/log ∈~(-1)) subproblems with edge weights bounded by (∈~(-1)~(O(∈~(-1))). In particular, if we combine our result with the recent (1 - ∈)-approximation algorithm for maximum weight matching in graphs due to Duan and Pettie whose time complexity has a poly-logarithmic dependence on W then we obtain a (1 - ∈)-approximation algorithm for maximum weight matching in graphs running in time (∈~(-1))~(O(1))(m + n).