Title: Diameter and k-Center in Sliding Windows
Speaker: Chris Schwiegelsohn, TU Dortmund
Date: Wednesday, March 1, 2017 1:00-2:00pm
Location: CoRE Building, Room 433, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In a data streaming environment we process a sequence of items and aim to solve an optimization problem using significantly less space than simply storing the entire data set. Sliding Windows are a generalization that allows us model time series by deleting the oldest items from the window. Our items will consist of points in a finite metric space.
I will present a (3+eps)-approximation algorithm for approximating the diameter in a window of size n using a constant number of points and a lower bound of sqrt(n) points for any algorithm that improves on a 3-approximation factor. I will also show how these techniques may be used for the k-center clustering problem.