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 affinity data is low rank. The weighted graph G over vertex sets U = V {1,...,n} means n×n matrix W whose entry ij weight edge (i,j) G, 1 ≤ i,j n. has rank at most r if there are 2r vector u 1,...,u r, v 1,...v ∈ ℝn such that $$W \sum_{i=1}^r \bf{u}_i \mathbf{v}^T_i.$$