Tata Institute of Fundamental Research
Matchings, Random Walks, and Sampling
Seminar
Speaker:
Professor Sanjeev Khanna (University of Pennsylvania
Department of Computer and Information Science
574, Moore GRW
3330 Walnut Street
Philadelphia, PA 19104
United States of America)
Organiser:
Jaikumar Radhakrishnan
Date:
Wednesday, 18 Dec 2013, 14:00 to 15:00
Venue:
AG-69
(Scan to add to calendar)
Abstract:
Abstract: The maximum matching problem is among the most well-studied problems in combinatorial optimization with many applications. In this talk, we will describe some results that illustrate surprising effectiveness of randomization in solving exact and approximate matching problems in small space or time. Specifically, the first part of the talk will focus on the problem of finding a perfect matching in a regular bipartite graph. We will show that sampling and random walks can be used to obtain surprisingly fast sublinear time exact algorithms for this problem. Our approach also yields an efficient algorithm for computing the Birkhoff-von-Neumann decomposition of a doubly-stochastic matrix as well as a near-linear time algorithm for rounding a fractional flow solution. In the second part of the talk, we will consider the problem of estimating the size of a maximum matching using small space in the streaming model. We show that if the edges of the graph are streamed in a random order, then poly-logarithmic space suffices to estimate the maximum matching size to within a poly-logarithmic factor. This is based on joint works with Ashish Goel, Michael Kapralov, and Madhu Sudan.
| Speaker: | Professor Sanjeev Khanna (University of Pennsylvania Department of Computer and Information Science 574, Moore GRW 3330 Walnut Street Philadelphia, PA 19104 United States of America) |
| Organiser: | Jaikumar Radhakrishnan |
| Date: | Wednesday, 18 Dec 2013, 14:00 to 15:00 |
| Venue: | AG-69 |
(Scan to add to calendar)
Abstract:
Abstract: The maximum matching problem is among the most well-studied problems in combinatorial optimization with many applications. In this talk, we will describe some results that illustrate surprising effectiveness of randomization in solving exact and approximate matching problems in small space or time. Specifically, the first part of the talk will focus on the problem of finding a perfect matching in a regular bipartite graph. We will show that sampling and random walks can be used to obtain surprisingly fast sublinear time exact algorithms for this problem. Our approach also yields an efficient algorithm for computing the Birkhoff-von-Neumann decomposition of a doubly-stochastic matrix as well as a near-linear time algorithm for rounding a fractional flow solution. In the second part of the talk, we will consider the problem of estimating the size of a maximum matching using small space in the streaming model. We show that if the edges of the graph are streamed in a random order, then poly-logarithmic space suffices to estimate the maximum matching size to within a poly-logarithmic factor. This is based on joint works with Ashish Goel, Michael Kapralov, and Madhu Sudan.