Paper Info
Title
Perturbation Analysis of Maximum-Weighted Bipartite Matchings with Low Rank Data.
Abstract
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 â̂̂ ân such that 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 such that (i) has rank at most r + 1, (ii) and (iii) the weighted bipartite graph with affinity data has locality at most âŒ̂r/ε⌉ r . © 2013 Springer-Verlag Berlin Heidelberg.
Year
DOI
Venue
2013
10.1007/978-3-642-38768-5_63
COCOON
Field
DocType
Volume
Rank (linear algebra),Discrete mathematics,Combinatorics,Perturbation theory,Vertex (geometry),Matrix (mathematics),Bipartite graph,Rank (graph theory),Matching (graph theory),Mean reciprocal rank,Mathematics
Conference
7936 LNCS
Issue
ISSN
Citations 
null
16113349
0
PageRank 
References 
Authors
0.34
5
2
Name
Order
Citations
PageRank
Xingwu Liu11912.77
Shang-Hua Teng23927424.26