FacebookTwitterGoogle PlusRSS News Feed

Theory Lunch Seminar

Seminars
Ph.D. Candidate
Department of Computer Science
University of Pittsburgh
A o(n)-Competitive Deterministic Algorithm for Online Matching on a Line
Wednesday, February 26, 2014 - 12:00pm to 1:00pm
6115 
Gates&Hillman Centers
Abstract:

Online matching on a line involves matching an online stream of items of various sizes to stored items of various sizes, with the objective of minimizing the average discrepancy in size between matched items. In the first part of this talk, we'll survey the current known upper and lower bounds for both randomized and deterministic algorithms for online matching on a line.

In the second part of this talk, we will show that online matching on a line is essentially equivalent to a particular search problem, that we call k-lost cows. We then obtain the first deterministic sub-linearly competitive algorithm for online matching on a line by giving such an algorithm for the k-lost cows problem.

This is joint work with Antonios Antoniadis, Michael Nugent, Kirk Pruhs, and Michele Scquizzato.

For More Information, Please Contact:

ggurugan@andrew.cmu.edu