Title: Streaming Algorithms for Matching Problems

Description: Speaker: Dr. Sagar Kale

Time: Wednesday, 16 October 2019, 2:15pm
Venue: Dept. of CSE, Room no. 109, 01st Floor, New CSE/CC Bldg.


Abstract:
The advent of big data necessitated design of algorithms that could cope with it. Streaming algorithms are viable for big data because they process their input sequentially and use a small amount of working memory. In this talk, I will present my research on streaming algorithms for matching problems. Matching problems have played a significant historical role in not just combinatorial optimization specifically but computer science at large and are our benchmark problems for development and understanding of a computational model. Indeed, studying them in the streaming model has led me to fastest algorithms for some combinatorial optimization problems---streaming or otherwise.

In the maximum matching problem, edges of the input graph arrive one-by-one in the stream and the goal is to compute a matching of large size. Weighted matching is a well-studied generalization of maximum matching where the graph is edge-weighted, and, in a further generalization, a submodular function is defined on the edges. Submodular functions have received a lot of attention in theoretical computer science as well as, more recently, in machine learning.

I will discuss a reduction from submodular matching to weighted matching that also extends to streaming algorithms for very general constraints such as matroids. Then I will give an overview of how to obtain almost optimal weighted matchings in constant number of passes over the stream and also in the MapReduce framework. I will conclude with future research directions.


Speaker Profile:
Details available at: https://sagark4.github.io/

Organization:
EPFL, Lausanne



Host:
Prof. Rohit Gurjar

Date: Wednesday, 16 October, 2019
Time: 2:15pm IST
Access: Public
Category: Talk*
Created by: Department Calendar
Updated: Sunday, 10 November, 2019 1:29pm IST
Send Reminder: Yes  -  284 hours 6 minutes before start
Participants: Department Calendar
<office@cse.iitb.ac.in> (External User)
_NUC_department <all@cse.iitb.ac.in> (External User)