Graph Secretary

We know the standard secretary problem: given n known items, they are presented in a random order; we need to either pick an item instantly as they are presented or lose it and our goal is to get the largest. The solution as many know is to observe the first n/e items and then pick the first that exceeds the largest of the first n/e elements; this has prob 1/e of being the largest. There is an exposition of the history of this problem here. This has been extended by Kleinberg, Babaioff et al, and others to graphs, matroids and more. Recently, Nitish Korula and Martin Pal have a nice result for the extension of the problem to online bipartite matching, with an elegant argument getting 8 approximation. Worth reading.