2010/12/29 by Lingas, Andrzej, Di, Cui
#05C50 #68Q25 #68R10 #68W01 #68W40 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1012.5911
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 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_1≤ q ≤ O(epsilon \frac log \frac n epsilon log epsilon-1) maxm1+...mq=m sum1qT(minn,smj,mj,(epsilon-1)^O(epsilon-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 (epsilon-1)O(1)(m+n).