Статья: Dynamic Optimality—Almost
In this paper, an O(lg lg n)-competitive online binary search tree is given which improves upon the best previous competitive ratio of O(lg n). This was the first major progress on Sleator and Tarjans dynamic optimality conjecture of 1985 that O(1)-competitive binary search trees exist. Indeed Mihai could formulate the O(1)-competitive conjecture as an approximation factor of some algorithm and we worked together for some time to prove the conjecture (that so far we could not:)). This was my first research experience with Mihai. Since then we always have talked about research (but we never had a joint paper). - источник
Mihai Patrascu, aged 29, passed away on Tuesday June 5, 2012, after a 1.5 year battle with brain cancer. Mihai's carreer was short but explosive, full of rich and beautiful ideas as witnessed, e.g., in his 19 STOC/FOCS papers.
Комментариев нет:
Отправить комментарий