tag:blogger.com,1999:blog-786333285568106173.post2691085692111906325..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: Binary Search Trees (III): OnlineMihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-786333285568106173.post-10760129808107670262012-06-06T13:16:44.932-04:002012-06-06T13:16:44.932-04:00Hi mihai, i have read your paper about the geometr...Hi mihai, i have read your paper about the geometric view of BST and see how the offline algo greedyfuture becomes online in the geometric view. however my concern is the initial configuration of the tree. it seems that greedyASS executes query base on the initial configuration set by greedyfuture. for example, greedyfuture will always arrange its initial tree such that the first query will be for the root and greedyASS take advantage of this. but this would mean that greedyASS makes some assumption of future query and might not be totaly online? i hope you can answer this mihai. thanks.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-90690493853290054442011-08-29T21:54:33.548-04:002011-08-29T21:54:33.548-04:00Wilber 1 and 2 are lower bounds on OPT, i.e. (\for...Wilber 1 and 2 are lower bounds on OPT, i.e. (\forall X) OPT(X) >= max ( Wilber1(X), Wilber2(X)).<br /><br />The point is that OPT is very hard to understand (maybe even NP-hard), whereas Wilber1&2 have simple Mathematical descriptions and there are linear-time algorithms to compute them.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-57432184403224923862011-08-29T13:07:13.044-04:002011-08-29T13:07:13.044-04:00Thank you for your time, I will continue reading m...Thank you for your time, I will continue reading more about this topic. And I also find the geometric interpretation of BST execution interesting though I cannot say I totally grasp everything. Just one last question, where does the Wilbur I and II bound fit in the picture?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-41698585548744163782011-08-29T12:41:41.625-04:002011-08-29T12:41:41.625-04:00We only want to determine competitivness asymptoti...We only want to determine competitivness asymptotically. So if OPT(X) could be approximated up to a constant, there is no problem.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-46933726501326772612011-08-29T12:30:12.740-04:002011-08-29T12:30:12.740-04:00If that is so, then how can is it possible to know...If that is so, then how can is it possible to know the competitive ratio/competitiveness of a given tree? Because I have read something about competitive ratio (c) that states that c(A) = (\forall X) max{costA(X)/costOPT(X)}. If costOPT(X) cannot easily be computed then how can I come up with the competitiveness of A?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-52833903396995518862011-08-29T12:24:41.503-04:002011-08-29T12:24:41.503-04:00If that is so, then how can is it possible to know...If that is so, then how can is it possible to know the competitive ratio/competitiveness of a given tree? Because I have read something about competitive ratio (c) that states that c(A) = (\forall X) max{costA(X)/costOPT(X)}. If costOPT(X) cannot easily be computed then how can I come up with the competitiveness of A?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-32609910588391681172011-08-29T12:16:25.847-04:002011-08-29T12:16:25.847-04:00Consider two simple examples:
1. If X is random, O...Consider two simple examples:<br />1. If X is random, OPT(X) = |X|lg n.<br />2. If X= (1,2,3, ..., n), OPT(X) = O(n).<br /><br />This shows that OPT(.) is a nontrivial function.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-67948534859467046872011-08-29T12:14:09.597-04:002011-08-29T12:14:09.597-04:00In fact, computing OPT(X) for a given X might easi...In fact, computing OPT(X) for a given X might easily be NP-hard (though I am not aware of a proof, there have been efforts to show this).Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-37357736513868757212011-08-29T12:12:28.901-04:002011-08-29T12:12:28.901-04:00Thank you for your immediate response on my questi...Thank you for your immediate response on my question, though I still find things a little confusing. So it means that there is no single value or function that would represent OPTcost(X)?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-29711197943279388472011-08-29T11:46:57.891-04:002011-08-29T11:46:57.891-04:00Actually, no. The ultimate goal is to show that fo...Actually, no. The ultimate goal is to show that for any access sequence X, the cost of splay trees on X is O(OPT on X). For some X, OPT(X) = |X|*lg n, or course, and no tree can achieve o(lg n) in the worst case (a tree has branching factor 2 and must reach an arbitrary key in a set of n keys).<br /><br />Now if we cannot prove that (\forall X) SPLAYcost(X) \le O(1)* OPTcost(X), we might want to replace the O(1) with some other small function. O(lg n) is trivial here since OPT must have cost at least 1 per access, and splay trees do achieve an O(lg n) upper bound (as do many mane other trees). But the gap between O(lgn) and the conjectured O(1) is open.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-76395405525937593892011-08-29T09:20:48.653-04:002011-08-29T09:20:48.653-04:00I know this post is quite old but I hope someone c...I know this post is quite old but I hope someone can help me on this one. I am trying to teach myself about this Online Binary Search topic and I have read a few papers on this topic and I am familiar with the fundamental concept about BST but it is my first time to focus on topics like competitive analysis and online algorithms. I am a little lost on what does it mean by <i>"nobody has shown any o(lg n) bound" </i> in your post about Splay trees? My best guess on this is that it means that nobody has shown that there is an offline BST with an OPT(X) = o(lg n)? I hope someone can help me understand the problem. Thanks.Anonymousnoreply@blogger.com