Name
Abstract | ||
|---|---|---|
We consider the online problem for a root (or a coordinator) to maintain a set of filters for the purpose of keeping track of the dominance relationship of some distributed multi-dimensional data. Such data keep changing from time to time. The objective is to minimize the communication between the root and the distributed data sources. Assume that data are chosen from the d-dimensional grid {1, 2, ..., U}d, we give an O(d log U)-competitive algorithm for this online problem. The competitive ratio is asymptotically tight as it is relatively easy to show an Ω(d log U) lower bound. |
Year | Venue | Keywords |
|---|---|---|
2010 | WAOA | competitive algorithm,dominance relationship,competitive ratio,multi-dimensional data,online problem,data source,online tracking,d-dimensional grid,lower bound |
Field | DocType | Volume |
Multi dimensional data,Mathematical optimization,Upper and lower bounds,Computer science,Theoretical computer science,Grid,Competitive analysis | Conference | 6534 |
ISSN | Citations | PageRank |
0302-9743 | 3 | 0.44 |
References | Authors | |
7 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tak-Wah Lam | 1 | 1860 | 164.96 |
| Chi-Man Liu | 2 | 96 | 7.06 |
| Hing-Fung Ting | 3 | 76 | 11.69 |