Speaker: Guy Kortsarz
Affiliation: Rutgers University-Camden
Title: What have we learned about cut expansion and density problems
Abstract: I will survey several problems related to the above subjects. Directed and undirected multicut. For Directed multicut I will show the approximation algorithm algorithm of Gupta. Conductance (and sparsest cut), overlapping and non overlapping clustering, the small set expansion conjecture and it equivalent to breaking the ratio of 2 for MINIMUM partial vertex cover problem, the densest subgraph problem and the dense k-subgraph problem.