Fall 2013

Real Analysis Weekly Seminar

Nov. 7, 2013 11:00 am12:00 pm

Add to Calendar

Approximability of submouldar optimization and constraint satisfaction problems.
A lot of progress has been made on the algorithms and hardness of approximating NP-hard problems from submodular optimization and constraint satisfaction problems. On the other hand, the  techniques used in these two area seems to be very different from each other.  In this talk, we will first study the approximability of the hypergraph multiway cut problem problem which lies at the intersection of submodular optimization and constraint satisfaction problem. Then we will establish some general connections on the approximaiblity of problems from these two areas.