de
en
Schliessen
Detailsuche
Bibliotheken
Projekt
Impressum
Datenschutz
Schliessen
Publizieren
Besondere Sammlungen
Digitalisierungsservice
Hilfe
Impressum
Datenschutz
zum Inhalt
Detailsuche
Schnellsuche:
OK
Ergebnisliste
Titel
Titel
Inhalt
Inhalt
Seite
Seite
Im Werk suchen
Page migration in dynamic networks / by Marcin Bienkowski. 2005
Inhalt
1 Introduction
1.1 Static networks
1.1.1 Competitive analysis
1.2 Dynamic networks
1.2.1 Our model
1.2.2 Our contribution
1.3 Related work
1.4 Bibliographical notes
2 Basics
2.1 Optimal offline solution
2.2 Reduction Lemma
2.3 Two-node networks
2.3.1 Randomized algorithm EDGE
2.3.2 Lower bound for oblivious adversary
2.4 Trivial algorithms
2.4.1 Algorithm JUMP
2.4.2 Reusing Page Migration algorithms
3 Adversarial Scenario
3.1 Randomization against adaptive adversary
3.1.1 Algorithm DIST
3.1.2 DIST in the first part of a step
3.1.3 DIST in the second part of a step
3.1.4 Combining DIST with other algorithms
3.2 Marking algorithms
3.2.1 Deterministic algorithm MARK
3.2.2 Randomization against oblivious adversary
3.2.3 Proofs of Phase Lemmas
3.3 Lower bounds
3.3.1 Lower bound against adaptive-online adversary
3.3.2 Lower bound against oblivious adversary
3.4 Concluding remarks
3.5 Proofs of technical claims
4 Brownian Motion Scenario
4.1 Majority algorithms
4.1.1 Epochs
4.1.2 Competitiveness of MAJ
4.2 Bounding cost of MAJ
4.3 Bounding cost of OPT
4.3.1 Narrow sets
4.3.2 Precondition: smooth movement
4.3.3 Precondition: scattered nodes
4.3.4 Proof of the Crucial Property
4.4 Extensions and conclusions
4.5 Proofs of technical claims
5 Stochastic Requests Scenario
5.1 Lower bound for the extended cost model
5.2 Algorithm MTFR
5.2.1 Lower bound for OPT
5.2.2 Upper bound for MTFR
5.2.3 Expected competitive ratio
5.3 Extensions and conclusions
5.4 Proofs of technical claims
5.4.1 Proof of the concentration bound
6 Summary and Outlook
Bibliography
Appendix
A.1 Notations
A.2 Mathematical tools
Die detaillierte Suchanfrage erfordert aktiviertes Javascript.