Near approximation of maximum weight matching through efficient weight reduction

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Abstract: 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 weight matching in G within factor alpha in time T(n,m,W) then we can find a matching of weight at least (alpha-epsilon) times the maximum weight of a matching in G in time (epsilon^{-1})^{O(1)}max_{1le q le O(epsilon frac {log {frac n {epsilon}}} {log epsilon^{-1}})} max_{m_1+...m_q=m} sum_1^qT(min{n,sm_j},m_{j},(epsilon^{-1})^{O(epsilon^{-1})}). In particular, if we combine our result with the recent (1-epsilon)-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-epsilon)-approximation algorithm for maximum weight matching in graphs running in time (epsilon^{-1})^{O(1)}(m+n).

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Near approximation of maximum weight matching through efficient weight reduction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3010385)