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

摘要

In this paper, we partially address a question raised by David Karger [5] 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_1,..., u_r, v_1,...v_r ∈ R~n such that W = ∑ from i=1 to r of (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 π 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 r and ε ∈ [0, 1], there exists W ∈ [0,1]~(n×n) such that (i) W has rank at most r + 1, (ii) max_(i,j) |W_(i,j) - W_(i,j)| ≤ ε, and (iii) the weighted bipartite graph with affinity data W has locality at most [r/ε]~r.