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

详细信息    查看全文

• 作者：Xingwu Liu^a ; ¹ ; ^{Xingwuliu@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Shang-Hua Teng^b ; ² ; ^{shanghua@usc.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Bipartite graphs ; Maximum matching ; Matrix decomposition ; Permutation
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：28 March 2016
• 年：2016
• 卷：621
• 期：Complete
• 页码：82-91
• 全文大小：378 K

文摘

The maximum-weighted bipartite matching problem between two sets U=V=[1:n]$U=V=[1:n]$ is defined by a matrix W=(w_ij)_n×n$\mathbf{W}={(w_{ij})}_{n\times n}$ of “affinity” data. Its goal is to find a permutation π   over [1:n]$[1:n]$ whose total weight ∑_iw_i,π(i)${\sum }_i{w}_{i,\pi (i)}$ is maximized. In various practical applications,³ 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 u₁,…,u_r,v₁,…v_r∈Rⁿ${\mathbf{u}}_1,\dots ,{\mathbf{u}}_r,{\mathbf{v}}_1,\dots {\mathbf{v}}_r\in {\mathbb{R}}^n$ such that

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>0$k>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×n$W\in {[0,1]}^{n\times n}$ of rank r   and ϵ∈[0,1]$ϵ\in [0,1]$, there exists $\tilde{W}\in {[0,1]}^{n\times n}$ such that (i) $\tilde{W}$ has rank at most r+1$r+1$, (ii) the entry-wise ∞-norm ${\Vert W-\tilde{W}\Vert }_{\infty }\le ϵ$, and (iii) the weighted bipartite graph with affinity data $\tilde{W}$ has locality at most ⌈r/ϵ⌉^r${\lceil r/ϵ\rceil }^r$. In contrast, this property is not true if perturbations are not allowed. We also give a tight bound for the binary case.