View Full Document

Static Optimality and Dynamic Search Optimality in Lists and Trees



View the full content.
View Full Document
View Full Document

4 views

Unformatted text preview:

Static Optimality and Dynamic Search Optimality in Lists and Trees Avrim Blum Shuchi Chawla Adam Kalai 1 6 2002 Shuchi Chawla Carnegie Mellon University List Update Problem Query for element 9 4 7 2 9 No No No Yes 12 3 6 8 Unordered list Access for xi takes i time Shuchi Chawla Carnegie Mellon University List Update Problem 9 4 7 2 12 3 6 8 Query for element 9 Unordered list Access for xi takes i time Moving up accessed item is FREE Other reorderings cost 1 per transposition Goal minimize total cost What should the reordering policy be Shuchi Chawla Carnegie Mellon University Binary Search Tree 7 2 4 12 5 9 14 15 In order tree Search cost depth of element Cost of rotations 1 per rotation Replacement policy Shuchi Chawla Carnegie Mellon University How good is a reordering algorithm Compare against the best offline algorithm Dynamic competitive ratio Best offline algorithm that cannot change state of the list tree static Static competitive ratio Shuchi Chawla Carnegie Mellon University Known results List update Dynamic ratio Albers et al 95 Teia 93 u b 1 6 l b 1 5 Trees Splay trees Sleator Tarjan 85 static ratio 3 No known result on dynamic ratio Classic Machine Learning results Experts analysis LW 94 static ratio 1 Computationally inefficient Recent new result Kalai Vempala 01 Efficient alg for Strong Static Optimality for trees Shuchi Chawla Carnegie Mellon University Our results List Update 1 static ratio efficient variant of Experts We call this Strong static optimality Combining strong static optimality and dynamic optimality to get best of both Search trees Constant Dynamic ratio for trees Given free rotations ignoring computation time Shuchi Chawla Carnegie Mellon University Revisiting Experts Algorithm Littlestone Warmuth 94 N expert algorithms We want to be 1 wrt the best algorithm Weighted Majority algorithm Assign weights to each expert by how well it performs Pick probabilistically according to weights Cost incurred 1 m ln N 1 Applying this to list update



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Static Optimality and Dynamic Search Optimality in Lists and Trees and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Static Optimality and Dynamic Search Optimality in Lists and Trees and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?