Hi all, I wonder if anyone can provide some insight into the following problem. The idea is to analyze the performance of the Ranking algorithm for online bipartite matching with random arrivals as applied to a specific graph. Background: - Given a bipartite graph; call the two sides L and R - Assume a perfect matching exists - The nodes from R arrive in an online manner - The order of arrival is a random permutation of the nodes in R selected uniformly from among all such permutations - When node j in R arrives, its edges to nodes in L are revealed - The algorithm then selects one of the neighbor nodes in L that has not previously been matched to match to j - The Ranking algorithm selects a random permutation of the nodes of L uniformly from all such permutations - When node j in R arrives, Ranking matches j to the highest ranking unmatched neighbor to j in L Goal: - Given a bipartite graph, compute the competitive ratio achieved by Ranking on the graph - The competitive ratio is the expected size of the matching achieved by Ranking divided by the size of the perfect matching Specific graph G: - L consists of 2n nodes, labeled 1, …, 2n. Nodes 1, …, n are in L1; nodes n+1, …, 2n are in L2 - R consists of 2n nodes, labeled 1, …, 2n. Nodes 1, …, n are in R1; nodes n+1, …, 2n are in R2 - The adjacency matrix is given by: - A(i, j) = 1 if i = j - A(i, j) = 1 if i <= n and j > n - A(i, j) = 0 otherwise - In summary: - each node in L1 is adjacent to a unique neighbor in R1 - each node in L2 is adjacent to a unique neighbor in R2 - all nodes in L1 are adjacent to all nodes in R2 - Ranking will match all nodes in L1 and all nodes in R2 but whenever it includes edge (i, j) with i in L1 and j in R2, then the neighbor to i in R1 and the neighbor to j in L2 remain unmatched Specific goal: - Show that the competitive ratio of Ranking on G is a decreasing function of n with limit 0.75 Context: - This graph has been proposed in Karande, Mehta and Tripathi, Online Bipartite Matching with Unknown Distributions, to provide an upper bound on the performance of Ranking on online bipartite graphs with random arrivals. They provide a theoretical analysis to establish the 0.75 bound but I don’t believe their analysis. - I believe the bound can be established empirically via simulation. - I don’t see an obvious way to approach this from a theoretical perspective so, as it’s a cute problem that seems like it should be amenable to some form of probabilistic analysis, I thought I’d see if anyone here has any insight. Cheers, Richard