Fast Distributed Approximation for Max-Cut

דובר:
רנה לוי, הרצאה סמינריונית למגיסטר
תאריך:
יום רביעי, 9.11.2016, 14:30
מקום:
טאוב 401
מנחה:
Prof. K. Censor-Hillel and Prof. H. Shachnai

One of the fundamental tasks in many computational settings is finding the maximum cut. Surprisingly, it has been insufficiently studied in the classic distributed settings, where vertices communicate by synchronously sending messages to their neighbours according to the underlying graph. In the talk we will discuss the techniques we developed for approximating Max-Cut in the distributed setting, and present several approximation algorithms obtained using them.

בחזרה לאינדקס האירועים