BEGIN:VCALENDAR
PRODID:-//Microsoft Corporation//Outlook MIMEDIR//EN
VERSION:1.0
BEGIN:VEVENT
DTSTART:20141118T231500Z
DTEND:20141119T010000Z
LOCATION:New Orleans Theater Lobby
DESCRIPTION;ENCODING=QUOTED-PRINTABLE:ABSTRACT: Given a graph, b-Matching problem is to an edge weighted matching with maximum weight with constraint that every vertex v can match with at most a specified number of b vertices. It has been shown that b-Matching is useful in various machine learning problems such as classification, spectral clustering, graph sparsification, graph embedding and data privacy. The exact algorithms for this problem have high time as well as storage requirements, are inherently sequential, and therefore, are not practical solving large problems. We propose a 1/2-approximation algorithm which runs in linear time in the number of edges and also requires less storage. We show that our algorithm can solve large problems and can get up to 96% of the optimal solution. We also show that our algorithm scales up to 10x on 16 cores of Intel Xeon machines and up to 50x on 60 cores of Intel Xeon Phi machines.
SUMMARY:Computing Approximate b-Matchings in Large Graphs and an Application to k-Anonymity
PRIORITY:3
END:VEVENT
END:VCALENDAR