Add to Calendar

When:

October 8, 2014 @ 12:00 pm – 1:00 pm

2014-10-08T12:00:00-04:00

2014-10-08T13:00:00-04:00

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.