GraphXD Seminar: Vector Representations of Graphs and the Maximum Cut Problem

GraphXD Seminar: Vector Representations of Graphs and the Maximum Cut Problem

Other Related Seminars
Feb 26, 2018, 04:00 PM - 05:30 PM | 1011 Evans Hall | Happening As Scheduled
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...