Paper Info
Title
Group-Aware Weighted Bipartite B-Matching
Abstract
The weighted bipartite B-matching (WBM) problem models a host of data management applications, ranging from recommender systems to Internet advertising and e-commerce. Many of these applications, however, demand versatile assignment constraints, which WBM is weak at modelling. In this paper, we investigate powerful generalisations of WBM. We first show that a recent proposal for conflict-aware WBM by Chen et al. is hard to approximate by reducing their problem from Maximum Weight Independent Set. We then propose two related problems, collectively called group-aware WBM. For the first problem, which *constrains the degree* of groups of vertices, we show that a linear programming formulation produces a Totally Unimodular (TU) matrix and is thus polynomial-time solvable. Nonetheless, we also give a simple greedy algorithm subject to a 2-extendible system that scales to higher workloads. For the second problem, which instead *limits the budget* of groups of vertices, we prove its NP-hardness but again give a greedy algorithm with an approximation guarantee. Our experimental evaluation reveals that the greedy algorithms vastly outperform their theoretical guarantees and scale to bipartite graphs with more than eleven million edges.
Year
DOI
Venue
2016
10.1145/2983323.2983770
ACM International Conference on Information and Knowledge Management
Keywords
Field
DocType
graph theory,assignment problem,approximation algorithms,NP-hardness,linear programming,k-extendible systems
Recommender system,Discrete mathematics,Data mining,Mathematical optimization,Vertex (geometry),Matrix (mathematics),Computer science,Bipartite graph,Greedy algorithm,Independent set,Linear programming,Unimodular matrix
Conference
Citations 
PageRank 
References 
1
0.36
23
Authors
5
Name
Order
Citations
PageRank
Cheng Chen1704.40
Sean Chester213912.70
S. Venkatesh3537.11
Kui Wu4305.06
Alex Thomo541849.02