Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, March 17, 2011, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Aris Anagnostopoulos (Univ. of Rome)

Algorithms on Dynamic Data

In this talk I will present a new computational model for dynamic data. In this model, the input data change gradually (deterministically or stochastically) and the goal of an algorithm is to maintain the solution to some problem at each time step, under the constraint that it only has a limited access to the data each time. As the data is constantly changing and the algorithm might be unaware of these changes, it cannot be expected to always output the exact right solution; we are interested in algorithms that guarantee to output an approximate solution.

After presenting the model, I will focus on the problems of sorting and of selecting an element of a given rank when the true ordering of the elements changes slowly and randomly. I will give lower bounds and algorithms achieving near-optimal performance in expectation and with high probability. Depending on the time, I will finish with the application of the model on some graph-related problems.

Based on joint work with Ravi Kumar, Mohammad Mahdian, Eli Upfal, and Fabio Vandin.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login