Maximum bipartite matchings with low rank data: Locality and perturbation analysis

The maximum-weighted bipartite matching problem between two sets U=V=[1:n]U=V=[1:n] is defined by a matrix W=(wij)n×nW=(wij)n×n of “affinity” data. Its goal is to find a permutation π   over [1:n][1:n] whose total weight ∑iwi,π(i)∑iwi,π(i) is maximized. In various practical applications,3 the affinity data may be of low rank (or approximately low rank): we say W has rank at most r if there are 2r   vectors u1,…,ur,v1,…vr∈Rnu1,…,ur,v1,…vr∈Rn such thatW=∑i=1ruiviT.In this paper, we partially address a question raised by David Karger who asked for a characterization of the structure of the maximum-weighted bipartite matchings when the rank of the affinity data is low. In particular, we study the following locality property: For an integer k>0k>0, we say that the bipartite matchings of G have locality at most k if for every sub-optimal matching π of G, there exists a matching σ of larger total weight that can be reached from π by an augmenting cycle of length at most k.We prove the following main theorem: For every W∈[0,1]n×nW∈[0,1]n×n of rank r   and ϵ∈[0,1]ϵ∈[0,1], there exists W˜∈[0,1]n×n such that (i) W˜ has rank at most r+1r+1, (ii) the entry-wise ∞-norm ‖W−W˜‖∞≤ϵ, and (iii) the weighted bipartite graph with affinity data W˜ has locality at most ⌈r/ϵ⌉r⌈r/ϵ⌉r. In contrast, this property is not true if perturbations are not allowed. We also give a tight bound for the binary case.