Name
Abstract | ||
|---|---|---|
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 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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.tcs.2010.10.003 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
data change,high probability,limited access,Dynamic data,dynamic data,Algorithms,exact right solution,Sorting,approximate solution,elements change,new computational model,time step,fundamental problem | Journal | 412 |
Issue | ISSN | Citations |
24 | Theoretical Computer Science | 3 |
PageRank | References | Authors |
0.55 | 4 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aris Anagnostopoulos | 1 | 1054 | 67.08 |
| Ravi Kumar | 2 | 13932 | 1642.48 |
| Mohammad Mahdian | 3 | 2689 | 226.62 |
| Eli Upfal | 4 | 4310 | 743.13 |