We analyze the addition of a simple local improvement step to various known randomized approximation algorithms. Let $\alpha \simeq 0.87856$ denote the best approximation ratio currently known for the Max Cut problem on general graphs~\cite{GW95}. We consider a semidefinite relaxation of the Max Cut problem, round it using the random ... more >>>

We show that in the bounded degree model for graph property testing, adaptivity is essential. An algorithm is *non-adaptive* if it makes all queries to the input before receiving any answers. We call a property *non-trivial* if it does not depend only on the degree distribution of the nodes. We ... more >>>