Saturday, June 25, 2011

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.

3 comments:

  1. hi,
    Nice way to analyze the KVV algorithm. I really liked Kamal's talk at Princeton on the same topic.

    I have the following observation - In the proof of dual feasibility we only need to argue about the feasibility of the equations corresponding to the edges belonging to the optimal solution. This is because we can restrict our analysis to the graph corresponding to the optimal solution. It suffices to show that the duals produced by the above analysis are feasible for this graph and the dual objective value is large(1-1/e of opt).

    Would love to hear your comments on this.

    --Pushkar

    ReplyDelete
  2. Yes Pushkar what you say is right, though not sure how it could be of additional help. As a mathematical fact, it suffices to demonstrate a feasible dual on any graph with equal optimal value, but again, not sure if this flexibility would be of any additional help. Kamal

    ReplyDelete
  3. Hi,

    We discussed this paper in our Algorithms Reading Group. A point came up that how does feasibility of the dual only in expectation imply an approximation ratio in expectation ? Because, even if one constraint in the dual gets violated by a lot (and all other constraints are satisfied, perhaps much over-satisfied), you can't say anything about a lower bound on the optimal.

    Can anybody please clear this up ?

    Thanks !

    ReplyDelete