Online Bipartite Perfect Matching With Augmentations

12 years 10 months ago
Online Bipartite Perfect Matching With Augmentations
—In this paper, we study an online bipartite matching problem, motivated by applications in wireless communication, content delivery, and job scheduling. In our problem, we have a bipartite graph G between n clients and n servers, which represents the servers to which each client can connect. Although the edges of G are unknown at the start, we learn the graph over time, as each client arrives and requests to be matched to a server. As each client arrives, she reveals the servers to which she can connect, and the goal of the algorithm is to maintain a matching between the clients who have arrived and the servers. Assuming that G has a perfect matching which allows all clients to be matched to servers, the goal of the online algorithm is to minimize the switching cost, the total number of times a client needs to switch servers in order to maintain a matching at all times. Although there are no known algorithms which are guaranteed to yield switching cost better than the trivial O(n2 )...
Kamalika Chaudhuri, Constantinos Daskalakis, Rober
Added 24 May 2010
Updated 24 May 2010
Type Conference
Year 2009
Authors Kamalika Chaudhuri, Constantinos Daskalakis, Robert D. Kleinberg, Henry Lin
Comments (0)