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 paper co-authored with Yuli Ye, we consider irrevocable and revocable priority algorithms for the subset-sum problem. The study of local ratio algorithms (as initiated by Bar-Yehuda and Even) led us to formalize aspects of this method by (priority) stack algorithms in a paper co-authored with Daviod Cashman and Avner Magen. On the positive side, local ratio algorithms motivate sequential k-independent graphs in a paper with Yuli Ye.
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 Roberts, Jeff Rosenthal and Panayiotis Tsaparas.
Algorithmic Mechanism Design: With Brendan Lucier, we explore the power and limitations of greedy-like algorithms for comnitaorial auction problems. While we show the limitation of greedy algorithms for truthful auctions , we also show that monotone greedy algorithms can be inplemented so as to have good price of anarchy .

Teaching:

CSC375 : Enriched Algorithm Design and Analysis .
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