On-Line Algorithms and the k-Server Conjecture

Περίληψη σε άλλη γλώσσα

The Work Function Algorithm, a natural algorithm for the ^-server problem, is shown to have competitive ratio at most 2k —1 for all metric spaces. It is also shown that the ^-server conjecture, which states that there is an on-line algorithm for the /^-server problem with competitive ratio k, holds for all metric spaces with k + 2 points. Furthermore, two refinements of competitive analysis are proposed and studied: diffuse adversaries and comparative analysis. They address successfully some of the drawbacks of competitive analysis. viii
Πρέπει να είστε εγγεγραμένος χρήστης για έχετε πρόσβαση σε όλες τις υπηρεσίες του ΕΑΔΔ  Είσοδος /Εγγραφή

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

DOI
10.12681/eadd/10816
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/10816
Συγγραφέας
ΚΟΥΤΣΟΥΠΙΑΣ, ΗΛΙΑΣ
Ημερομηνία
1994
Ίδρυμα
University of California, San Diego
Λέξεις-κλειδιά
Αλγόριθμοι
Χώρα
Η.Π.Α.
Γλώσσα
Αγγλικά
Άλλα στοιχεία
49 σ.