A primal-dual analysis of the Ranking algorithm

The other day I was sitting next to Kamal Jain on a flight, and he told me about a neat primal-dual analysis (due to Nikhil Devanur, Bobby Kleinberg, and him) of the Karp-Vazirani-Vazirani Ranking algorithm for online matching. Since the adwords result also has a primal-dual analysis, this is a step towards unifying the results.

The n vertices on one side of the bipartite graph (indexed by i) are known in advance, the n vertices on the other side (indexed by j) arrive online, and the edges adjacent to j are revealed upon j's arrival.

Here is one way to present the Ranking algorithm: each i picks a random value y(i) independently drawn from the uniform distribution over [0,1]. When j arrives, is at least one of its neighbors is not yet matched, j gets matched to the available neighbor with smallest value y(i). Every time an edge e is added to the matching the corresponding variable x(e) is set to 1 in the standard linear programming formulation for maximum bipartite matching.

Here is how the dual is defined. There is one variable b(i) for each i, which stays at 0 as long as i is not matched, and one variable a(j) for each j, which will be set upon j's arrival. We use a water-level algorithm, so initially every i is filled with water up to level 0, and the level only goes up. When j arrives, consider the available neighbors of j. In a continuous manner, take the ones filled to the lowest level, and raise their water level together (new available neighbors of j may join in along the way if the water level reaches their current water level.) This stops when some i reaches level y(i). At that time, (j is matched to i), we set variable b(i) to (exp(y(i))/(e-1), and variable a(j) to (e-exp(y(i))/(e-1). If j stays unmatched, we set a(j) to 0.

To relate the value of the primal (number of matching edges) to the value of the dual (sum over i of a(i) plus sum over j of a(j)), we consider two cases: if j is not matched, neither the primal nor the dual change values. If j is matched, the primal increases by 1 and the dual increases by (exp(y(i))/(e-1)+(e-exp(y(i))/(e-1), which equals 1/(1-1/e), as desired. This the value of the primal is at least (1-1/e) times the value of the dual.

Obviously, the primal is feasible: it's a matching.

Unfortunately the dual might be unfeasible: the dual constraints, a(j)+b(i)>= 1 for each edge {i,j}, might be violated. The idea is that the dual solution is feasible on average. Then the expected value of the output matching will be at least (1-1/e) times the expected value of the dual, which, by feasibility of the average, is greater than (1-1/e) times OPT.

To prove that the dual is feasible on average, focus on one edge {i,j}, fix the value of y(i') arbitrarily for all i' different from i, and consider the executions of the algorithms as y(i) ranges through all values in [0,1]. In addition, consider an artificial execution in which i is not present, and for that execution, let L denote the water level at which j is matched, if there is such a level; L=1 if j stays unmatched. For that artificial execution, a(j) equals (e-exp(L))/(e-1). Now, put i back into the system and continuously decrease y(i) from 1 to zero. By monotonicity of the Ranking algorithm, a decrease in y(i) cannot decrease a(j), so a(j) will be at least (e-exp(L))/(e-1) in all executions. On the other hand, as soon as y(i) goes below L, edge {i,j} appears in the matching, and by monotonicity, a decrease in y(i) cannot cause vertex i to go from being matched to being unmatched, so b(i)=exp(y(i))/(e-1) for all values of y(i) in [0,L]. Integrating over y(i), we obtain that the value of E(a(j))+E(b(i)) is at least 1, so constraint {i,j} is satisfied. This proves feasibility of the average of the duals.