grafos-ml/okapi — pull request #11 by gdfm (2014-07-17 15:54:03+00:00)
Title: Maximum b-matching algorithm

Greedy algorithm for the Maximum B-Matching problem as described in G. De Francisci Morales, A. Gionis, M. Sozio "Social Content Matching in MapReduce" in PVLDB: Proceedings of the VLDB Endowment, 4(7):460-469, 2011.

Given a weighted undirected graph, with integer capacities assigned to each vertex, the maximum b-matching problem requires to select a subgraph of maximum weight such that the number of edges incident to each vertex in the subgraph does not exceed its capacity. This is a greedy algorithm that provides a 1/2 approximation guarantee.