Perturbation Analysis of Maximum-Weighted Bipartite Matchings with Low Rank Data

摘要

In this paper, we partially address a question raised by David Karger regarding the structure of maximum-weighted bipartite matchings when the affinity data is of low rank. The affinity data of a weighted bipartite graph G over the vertex sets U = V = {1,..., n} means the n × n matrix W whose entry W_(ij) is the weight of the edge (i, j) of G, 1≤ i, j≤ n. W has rank at most r if there are 2r vector u_i,..., u_r, v_1,...v_r∈R~n such that W= r∑i=1 u_iv_i~T.In particular, we study the following locality property of the matchings: For an integer k＞0, we say the locality of G is at most k if for every matching n of G, either π has the maximum weight, or its weight is smaller than that of another matching σ with |π|σ| ≤k and |σ π| ≤k.We prove the following theorem: For every W ∈[0, 1]~(n×n) of rank (t) and ε ∈ [0,1], there exists W ∈ [0, 1]~(n×n) such that (ⅰ) W has rank at most r + 1, (ⅱ) max_(i,j) W_(i,j)-W_(i,j)≤ε, and (ⅲ) the weighted bipartite graph with affinity data W has locality at most [r/ε]~r.