Allan Borodin

Professor, Department of Computer Science, University of Toronto.

Research Interests:

Computational Complexity
Analysis of Algorithms: We consider the approximation ratio that can be achieved by greedy and greedy-like schedulling algorithms as formalized by ``priority algorithms'' for scheduling problems (co-authored with Morten Nielsen and Charles Rackoff) and facility location/set cover (co-authored with Spyros Angelopoulos) problems. In a recent paper (co-authored with Yuli Ye), we consider irrevocable and revocable priority algorithms for the subset-sum problem.
Online Computation: Information on the text by Allan Borodin and Ran El-Yaniv.
Network Routing: A paper concerning network stability preserving transformations (co-authored with Rafi Ostrovsky and Yuval Rabani).
Information Retrieval: A study of the use of hyperlinks for ranking occurs in this paper co-authored with Gareth Robers, Jeff Rosenthal and Panayiotis Tsaparas.

Teaching:

CSC2401 Introduction to Computational Complexity:
SCI199 : Great Ideas in Computing :

Birthday Workshop:

Here are the pictures taken by Amos Fiat.
Pictures from my Birthday Seminar.

Mailing Address

Department of Computer Science
University of Toronto
Sandford Fleming Building
10 Kings College Road
Toronto, ON, M5S 3G4
Canada
email: bor..at..cs.toronto.edu