[Discrete-math-seminar] Thursday Sept 21 1:15pm seminar: Hemanshu Kaul

[Robert Ellis]

Thursday Sept. 21 Talk
======================
Speaker: Hemanshu Kaul
Title: Finding large bipartite subgraphs
Time: 1:15pm
Location: E1 122

Abstract:  Finding a bipartite subgraph with maximum number of edges in a 
given graph is a classical problem in combinatorial optimization and 
extremal graph theory. It has been studied in computer science from an 
algorithmic point of view (as the MAX-CUT problem) and in combinatorics 
from a more structural point of view. The problem is NP-complete, so the 
focus of research has been on heuristics, approximation algorithms, and 
extremal results (conditions on graph parameters that guarantee large 
bipartite subgraphs).

We will discuss open problems and related resullts from both the extremal 
and algorithmic realms. In particular, we will discuss some recent results 
on locally improving algorithms.