Journal of Discrete Algorithms · 2008 · 10 citations · 16 references
ComputingComputer ScienceComputer SystemsAlgorithmsComputer NetworksDistributed SystemsData MigrationDistributed ComputingDynamic Network AnalysisNetwork OptimizationOnline AlgorithmsDeterministic Online AlgorithmsDynamic Communication NetworksDynamic Network OptimizationOnline Approximation AlgorithmsOnline Data MigrationOnline PagingPage Migration
We present an extension of a classical data management subproblem, the page migration. The problem is investigated in dynamic networks, where costs of communication between different nodes may change with time. We construct asymptotically optimal online algorithms for this problem, both in deterministic and randomized scenarios.
16
Probabilistic computations: Toward a unified measure of complexity
Andrew Chi-Chin Yao · 1977 · 892 citations
Topology control and routing in ad hoc networks
Rajmohan Rajaraman · ACM SIGACT News · 2002 · 399 citations
On the power of randomization in online algorithms
Shalev Ben-David, Allan Borodin, Richard M. Karp et al. · 1990 · 176 citations