Centre for Formal Design
Verification of Software

Wednesday Seminars

Next SeminarSeminar ListingHome

Date- 19th March 2014
Time- 03:15 PM
Speaker- Sumedh Tirodkar, Ph.D. student, Dept. of CSE
Title- Online preemptive matching (lower bound)
Venue- CFDVS Conference room, IIT Bombay.

Hide Details


The Maximum Weight Matching (MWM) problem is considered in the online preemptive setting. Edges of underlying graph are presented one after other. At every stage the given edge has to be either accepted or rejected in the current matching. Once rejected, the edge can never be considered again in current matching. Once accepted, the edge can be later on removed from current matching. The goal is to output a Maximum Weight Matching.
The deterministic upper and lower bounds for the competitive ratio for this problem are tight. But there is a large gap between randomised upper and lower bounds. We wish to fill this gap. In last talk, I spoke on the randomized algorithm. In this talk, I will discuss the lower bound due to Epstien et.al.

  1. Improved Bounds for Online Preemptive Matching, STACS, 2013 by L. Epstein, A. Levin, D. Segev, O. Weimann.
  2. Finding graph matchings in data streams, APPROX, 2005 by A. McGregor.
  3. Buyback problem ÿÿ approximate matroid intersection with cancellation costs, ICALP, 2011 by A. Badanidiyuru Varadaraja.

—> Principal Investigators
—> Research Employees
—> Students

—> Weekly Meetings
—> Formal Methods Update '05
—> Workshop'05
—> Workshop 2002
—> Workshop 2017

—> R & D Projects
—> Sponsored Projects
—> Exploratory Projects

—> Papers
—> Technical Reports
—> Theses

—> Course Material
—> Online documentation

—> Photographs
—> Internal Website
—> Webmail
[   Home  |   CSE  |   IIT Bombay  |   Contact  ]
For suggestions and comments contact: Webmaster