Search for tag: "algorithms combinatorics and optimization (aco)"

86 Years of Ramsey R(3,k) (and counting!) - Joel Spencer

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,…

From  Kathryn Gentilello on November 15th, 2017 50 plays 0  

Modern Erdos Magic - Joel Spencer

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…

From  Kathryn Gentilello on November 13th, 2017 28 plays 0  

A constant-factor approximation algorithm for the asymmetric traveling salesman problem - László A. Végh

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…

From  Kathryn Gentilello on September 27th, 2017 31 plays 0