#
Sort me if you can: how to sort dynamic data

##
Will Devanny

We formulate and study a new computational model for dynamic data. In
this model the data changes gradually and the goal of an algorithm is to
compute the solution to some problem on the data 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. In particular, we focus on the
fundamental problems of sorting and selection, where the true ordering
of the elements changes slowly. We provide algorithms with performance
close to the optimal in expectation and with high probability.

(Based on a paper in ICALP
2009 by Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian, and Eli
Upfal.)