- Series
- ACO Student Seminar
- Time
- Friday, January 25, 2019 - 1:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Mohit Singh – ISyE, Georgia Tech – mohit.singh@isye.gatech.edu – https://www2.isye.gatech.edu/~msingh94/
- Organizer
- He Guo
We present a new general and simple method for rounding semi-definite programs, based on Brownian motion. Our approach is inspired byrecent results in algorithmic discrepancy theory. We develop and present toolsfor analyzing our new rounding algorithms, utilizing mathematical machineryfrom the theory of Brownian motion, complex analysis, and partial differentialequations. We will present our method to several classical problems, including Max-Cut, Max-di-cut and Max-2-SAT, and derive new algorithms that are competitive with the best known results. In particular, we show that the basic algorithm achieves 0.861-approximation for Max-cut and a natural variant of the algorithm achieve 0.878-approximation, matching the famous Goemans-Williamson algorithm upto first three decimal digits. This is joint work with Abbas-Zadeh, Nikhil Bansal, Guru Guruganesh, Sasho Nikolov and Roy Schwartz.