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
10.12681/eadd/10816 http://hdl.handle.net/10442/hedi/10816 10816 Κουτσουπιάς, Ηλίας (Πατρώνυμο: Βασίλειος) 1994 University of California, San Diego Papadimitriou Christos
Buss Samuel
Impagliazzo Russell
Saks Michael
Sobel Joel 
Στατιστικά χρήσης
Διεύθυνση Handle
ND
Συγγραφέας
Ημερομηνία
Ίδρυμα
Εξεταστική επιτροπή
Buss Samuel
Impagliazzo Russell
Saks Michael
Sobel Joel
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
| Αλγόριθμοι | ||
| Χώρα | Η.Π.Α. | ||
| d>-->
|
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
| |
 | Κατεβάστε τη διατριβή σε μορφή PDF (1.98 MB)
(Η υπηρεσία είναι διαθέσιμη μετά από δωρεάν εγγραφή)
|
Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.
|
Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.
ΠΡΟΒΟΛΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής για την χρονική περίοδο 07/2018 - 07/2023.
Πηγή: Google Analytics.
Πηγή: Google Analytics.
ΞΕΦΥΛΛΙΣΜΑΤΑ
Αφορά στο άνοιγμα του online αναγνώστη για την χρονική περίοδο 07/2018 - 07/2023.
Πηγή: Google Analytics.
Πηγή: Google Analytics.
ΜΕΤΑΦΟΡΤΩΣΕΙΣ
Αφορά στο σύνολο των μεταφορτώσων του αρχείου της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
ΧΡΗΣΤΕΣ
Αφορά στους συνδεδεμένους στο σύστημα χρήστες οι οποίοι έχουν αλληλεπιδράσει με τη διδακτορική διατριβή. Ως επί το πλείστον, αφορά τις μεταφορτώσεις.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
Σχετικές εγγραφές (με βάση τις επισκέψεις των χρηστών)
