Description
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.
All scheduled dates:
Upcoming
No Upcoming activities yet