Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Fast Distributed Approximation for Max-Cut
event speaker icon
Rina Levy (M.Sc. Thesis Seminar)
event date icon
Wednesday, 09.11.2016, 14:30
event location icon
Taub 401
event speaker icon
Advisor: 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.