DIMACS Special Seminar

Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

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


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.