What is the approximation ratio of this randomized algorithm for finding matchings?
Suppose that the only feasible solution are single edges and $\{(1,1),(2,2),\ldots,(n,n)\}$. The optimal solution thus has value $n$. On the other hand, the optimal solution on a random bipartite graph is $1$ with probability $1-2^{-n}$. Thus algorithm BA would have to take $T=\Omega(2^n)$ in order to guarantee a constant approximation ratio, even though algorithm LA always outputs the optimal solution.