Title: Approximation algorithms via matrix covers
Speaker: Noga Alon, Tel Aviv University
Date: Wednesday, October 9, 2013 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
I will describe a general technique for obtaining approximate solutions of hard quadratic optimization problems using economical covers of high dimensional sets by small cubes. The analysis of the method leads to intriguing algorithmic, combinatorial, extremal, geometric and probabilistic questions.
Based on joint work with Lee, Shraibman and Vempala.