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

doi:10.1016/j.tcs.2016.01.033

	Maximum bipartite matchings with low rank data: Locality and perturbation analysis
	Liu, Xingwu 1; Teng, Shang-Hua 2,3
	2016-03-28
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	621 页码:82-91
摘要	The maximum-weighted bipartite matching problem between two sets U = V = [1 : n] is defined by a matrix W = (W-ij)(nxn) of "affinity" data. Its goal is to find a permutation pi over [1 : n] whose total weight Sigma(i) w(i,pi(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 2(r) vectors u(1), . . . , u(r), v(1), . . . v(r) is an element of R-n such that W = Sigma (i =1) (T) u(i)v(i)(T). 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, we say that the bipartite matchings of G have locality at most k if for every sub-optimal matching pi of G, there exists a matching sigma of larger total weight that can be reached from it by an augmenting cycle of length at most k. We prove the following main theorem: For every W is an element of [0, 1](nxn) of rank r and is an element of is an element of [0,1], there exists (W) over tilde is an element of [0, 1](nxn) such that (i) (W) over tilde has rank at most r + 1, (ii) the entry-wise infinity-norm parallel to W - W parallel to(infinity) <= is an element of, and (iii) the weighted bipartite graph with affinity data W has locality at most [r/is an element of](r). In contrast, this property is not true if perturbations are not allowed. We also give a tight bound for the binary case. (C) 2016 Elsevier B.V. All rights reserved.
关键词	Bipartite graphs Maximum matching Matrix decomposition Permutation
DOI	10.1016/j.tcs.2016.01.033
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[61173009] ; NSF[1111270] ; NSF[0964481]
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000371939100007
出版者	ELSEVIER SCIENCE BV
引用统计	被引频次：2[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/8644
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Teng, Shang-Hua
作者单位	1.Chinese Acad Sci, Inst Comp Technol, Beijing 100864, Peoples R China 2.Univ So Calif, Dept Comp Sci, Viterbi Sch Engn, Los Angeles, CA 90089 USA 3.Univ So Calif, Los Angeles, CA USA
推荐引用方式 GB/T 7714	Liu, Xingwu,Teng, Shang-Hua. Maximum bipartite matchings with low rank data: Locality and perturbation analysis[J]. THEORETICAL COMPUTER SCIENCE,2016,621:82-91.
APA	Liu, Xingwu,&Teng, Shang-Hua.(2016).Maximum bipartite matchings with low rank data: Locality and perturbation analysis.THEORETICAL COMPUTER SCIENCE,621,82-91.
MLA	Liu, Xingwu,et al."Maximum bipartite matchings with low rank data: Locality and perturbation analysis".THEORETICAL COMPUTER SCIENCE 621(2016):82-91.