Sticky Brownian Rounding and its Applications to Optimization Problems

Series: 
ACO Student Seminar
Friday, January 25, 2019 - 1:05pm
1 hour (actually 50 minutes)
Location: 
Skiles 005
,  
ISyE, Georgia Tech
,  
Organizer: 
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.