Vector Representations of Graphs and the Maximum Cut Problem (February 26, 2018)

David P. Williamson (Operations Research and Information Engineering, Cornell University)

In this talk, I will look at a classical problem from graph theory of finding a large cut in a graph. We’ll start with a 1967 result of Erdős that showed that picking a random partition of the graph finds a cut that is at least half the largest possible cut. We’ll then describe a result due to Goemans and myself from 1995 that shows that by representing the graph as a set of vectors, one per vertex, and optimizing the set, one can find a cut of size at least .878 the largest possible. If time permits, we’ll see an additional application of this vector representation to either clustering or coloring.

License: CC BY-NC-SA 4.0
- https://creativecommons.org/licenses/...