The search for the asymptotics of the Ramsey function R(3,k) has a long and fascinating history. It begins in the hill country surrounding Budapest and winding over the decades through Europe,…
Traditional Erdos Magic (a.k.a. The Probabilistic Method) proves the existence of an object with certain properties by showing that a random (appropriately defined) object will have those properties…
We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our…