Tata Institute of Fundamental Research
On Randomized Algorithms for Online Preemptive Matching
STCS Seminar
Speaker:
Sumedh Tirodkar (Indian Institute of Technology
Department of Computer Science
and Engineering
Powai
Mumbai 400076)
Organiser:
Jaikumar Radhakrishnan
Date:
Wednesday, 30 Mar 2016, 10:00 to 11:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
The second talk in this series will be given on Friday, April 01, 2016 at 1600 hours in A-201.
Abstract: In this series of two talks, we will investigate the power of randomized algorithms for the maximum cardinality matching (MCM) and the maximum weight matching (MWM) problems in the online preemptive model. In this model, the edges of a graph are revealed one by one and the algorithm is required to always maintain a valid matching. On seeing an edge, the algorithm has to either accept or reject the edge. When an edge is accepted, the edges adjacent to it are discarded. The goal is to construct as large (heavy) a matching as possible.
The complexity of the problem is settled for deterministic algorithms. For randomized algorithms, a lower bound of $1.693$ on the competitive ratio is known for MCM with a trivial upper bound of two; an upper bound of $5.356$ is known for MWM. We initiate a systematic study of the same in this paper with an aim to isolate and understand the difficulty. We begin with a primal-dual analysis of the deterministic algorithm due to McGregor. All deterministic lower bounds are on instances which are trees at every step. Using a considerable extension of the (simple) primal-dual analysis of the deterministic case, we show a randomized algorithm that is $\frac{28}{15}$-competitive for this class of (unweighted) graphs.
In the first talk, we will review the background and earlier results. In the second talk, we will describe our randomized algorithm. We will also present other related results if time permits (based on joint work with Ashish Chiplunkar and Sundar Vishwanathan: http://arxiv.org/abs/1412.8615.)
| Speaker: | Sumedh Tirodkar (Indian Institute of Technology Department of Computer Science and Engineering Powai Mumbai 400076) |
| Organiser: | Jaikumar Radhakrishnan |
| Date: | Wednesday, 30 Mar 2016, 10:00 to 11:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
The second talk in this series will be given on Friday, April 01, 2016 at 1600 hours in A-201.
Abstract: In this series of two talks, we will investigate the power of randomized algorithms for the maximum cardinality matching (MCM) and the maximum weight matching (MWM) problems in the online preemptive model. In this model, the edges of a graph are revealed one by one and the algorithm is required to always maintain a valid matching. On seeing an edge, the algorithm has to either accept or reject the edge. When an edge is accepted, the edges adjacent to it are discarded. The goal is to construct as large (heavy) a matching as possible.
The complexity of the problem is settled for deterministic algorithms. For randomized algorithms, a lower bound of $1.693$ on the competitive ratio is known for MCM with a trivial upper bound of two; an upper bound of $5.356$ is known for MWM. We initiate a systematic study of the same in this paper with an aim to isolate and understand the difficulty. We begin with a primal-dual analysis of the deterministic algorithm due to McGregor. All deterministic lower bounds are on instances which are trees at every step. Using a considerable extension of the (simple) primal-dual analysis of the deterministic case, we show a randomized algorithm that is $\frac{28}{15}$-competitive for this class of (unweighted) graphs.
In the first talk, we will review the background and earlier results. In the second talk, we will describe our randomized algorithm. We will also present other related results if time permits (based on joint work with Ashish Chiplunkar and Sundar Vishwanathan: http://arxiv.org/abs/1412.8615.)
Abstract: In this series of two talks, we will investigate the power of randomized algorithms for the maximum cardinality matching (MCM) and the maximum weight matching (MWM) problems in the online preemptive model. In this model, the edges of a graph are revealed one by one and the algorithm is required to always maintain a valid matching. On seeing an edge, the algorithm has to either accept or reject the edge. When an edge is accepted, the edges adjacent to it are discarded. The goal is to construct as large (heavy) a matching as possible.
The complexity of the problem is settled for deterministic algorithms. For randomized algorithms, a lower bound of $1.693$ on the competitive ratio is known for MCM with a trivial upper bound of two; an upper bound of $5.356$ is known for MWM. We initiate a systematic study of the same in this paper with an aim to isolate and understand the difficulty. We begin with a primal-dual analysis of the deterministic algorithm due to McGregor. All deterministic lower bounds are on instances which are trees at every step. Using a considerable extension of the (simple) primal-dual analysis of the deterministic case, we show a randomized algorithm that is $\frac{28}{15}$-competitive for this class of (unweighted) graphs.
In the first talk, we will review the background and earlier results. In the second talk, we will describe our randomized algorithm. We will also present other related results if time permits (based on joint work with Ashish Chiplunkar and Sundar Vishwanathan: http://arxiv.org/abs/1412.8615.)