Glencora Borradaile

Assistant Professor
Computer Science
  • Computer Science, Ph.D. December 2007
    Brown University Providence, Rhode Island
    Thesis: Exploiting planarity for network flow and connectivity problems.
    Advisor: Philip Klein.
  • Computer Science, M.Sc. May 2004
    Brown University Providence, Rhode Island
    Mathematical and constraint programming.
  • Applied Mathematics, B.Sc. (Honours) April 2002
    The University of Western Ontario London, Ontario
    With a concentration in theoretical physics and fluid mechanics.

Glencora Borradaile has a B.Sc. in Applied Mathematics from the University of Western Ontario (2002) and a Ph.D. in Computer Science from Brown University (2008). Before starting as faculty at Oregon State, she was a National Science and Engineering Research Council (NSERC) of Canada postdoctoral fellow in the Combinatorics and Optimization Department at the University of Waterloo.

Her research in algorithms started with traditional network flow and design problems in planar graphs. She still pursues these avenues, inspired by potential applications to problems in road networks, image processing and telecommunication networks. More generally she is interested in discrete optimization problems.

Research group: 
Research Interests: 

Research Areas
Theoretical computer science, algorithms, network algorithms, graph algorithms, discrete optimization, approximation algorithms

In Press
Borradaile, G., B. Heeringa, and G. Wilfong, "The knapsack problem with neighbour constraints", Journal of Discrete Algorithms, vol. 16, pp. 224 - 235, 10/2012. Abstract
Harutyunyan, A., G. Borradaile, C. Chambers, and C. Scaffidi, "Planted-model evaluation of algorithms for identifying differences between spreadsheets", 2012 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC), Innsbruck, Austria, IEEE, pp. 7 - 14, 10/2012. Abstract
Borradaile, G., and D. Eppstein, "Near-Linear-Time Deterministic Plane Steiner Spanners and TSP Approximation for Well-Spaced Point Sets", CoRR, vol. abs/1206.2254, Charlottetown, Prince Edward Island, Canada, 08/2012. Abstract
Azimi, J., A. Fern, X. Z. Fern, G. Borradaile, and B. Heeringa, "Batch Active Learning via Coordinated Matching", International Conference on Machine Learning (ICML), Edinburgh, Scotland, 07/2012. Abstract
Borradaile, G., S. Pettie, and C. Wulff-Nilsen, "Connectivity Oracles for Planar Graphs", Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), vol. abs/1204.4159, Helsinki, Finland, 07/2012. Abstract
Borradaile, G., P. N. Klein, S. Mozes, Y. Nussbaum, and C. Wulff-Nilsen, "Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time", 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), Palm Springs, CA, IEEE, pp. 170 - 179, 10.2011. Abstract
Borradaile, G., P. N. Klein, and C. Mathieu, "A Polynomial-Time Approximation Scheme for Steiner Tree in Planar Graphs", ACM Transactions on Algorithms, vol. 5, issue 3, pp. 1 - 31, 07/2009. Abstract
Borradaile, G., and P. N. Klein, "An O(n log n) Algorithm for Maximum St-Flow in a Directed Planar Graph", Journal of the ACM, vol. 56, issue 2, pp. 1 - 30, 04/2009. Abstract
Borradaile, G., E. D. Demaine, and S. Tazari, "Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs", 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), vol. 3, Dagstuhl, Germany, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 171–182, 02/2009. Abstract
Borradaile, G., P. N. Klein, and C. Mathieu, "A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest", 2008 IEEE 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Philadelphia, PA, IEEE, pp. 115 - 124, 10/2008. Abstract
Borradaile, G., and P. Van Hentenryck, "Safe and Tight Linear Estimators for Global Optimization", Mathematical Programming, vol. 102, issue 3, pp. 495 - 517, 01/2005. Abstract