Glencora’s research interests are, most broadly, algorithms for discrete optimization problems. Her main focus has been in planar graph algorithms: approximation algorithms for network design problems and fast, exact algorithms for network flow problems. Since at OSU, she has begun working with in-house researchers in machine learning, programming languages and electrical engineering.
Publications and manuscripts are organized by topic below: planar graph network flow algorithms, planar graph approximation algorithms, computational geometry and other. Her dissertation is available at the bottom of the page.
Planar graph network flow algorithms
Connectivity Oracles for Planar Graphs
Glencora Borradaile, Seth Pettie, and Christian Wulff-Nilsen.
Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2012.
[ arXiv ]
Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
Glencora Borradaile, Philip Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen.
Foundations of Computer Science (FOCS), 2011.
[ arXiv ]
Min st-cut oracle for planar graphs with near-linear preprocessing time.
Glencora Borradaile, Piotr Sankowski and Christian Wulff-Nilsen.
Foundations of Computer Science (FOCS), 2010.
[ arXiv ]
Multiple source, single sink maximum flow in a planar graph
Glencora Borradaile and Christian Wulff-Nilsen.
Manuscript, 2010.
[ arXiv ]
An O(n log n) algorithm for maximum st-flow in a directed planar graph.
Glencora Borradaile and Philip Klein.
Journal of the ACM, 56(2), 2009.
Symposium on Discrete Algorithms (SODA), 2006.
[ pdf, full version ]
Planar graph approximation algorithms
The two-edge connectivity survivable network problem in planar graphs.
Glencora Borradaile and Philip Klein.
Int’l Colloq. on Automata, Languages and Programming (ICALP), 2008.
[ pdf ]
A polynomial-time approximation scheme for Steiner tree in planar graphs.
Glencora Borradaile, Claire Mathieu, and Philip Klein.
ACM Transactions on Algorithms special issue for SODA 2007, 5(3), 2009.
Symposium on Discrete Algorithms (SODA), 2007.
[ pdf, full version ]
Steiner tree in planar graphs: An O(n log n) approximation scheme with singly-exponential dependence on epsilon.
Glencora Borradaile, Philip Klein and Claire Mathieu.
Workshop of Algorithms and Data Structures (WADS), 2007.
[ incorporated into journal version above ]
Computational geometry
Polynomial-time approximation schemes for connectivity problems in bounded-genus graphs.
Glencora Borradaile, Erik Demaine and Siamak Tazari.
Algorithmica, to appear.
Int’l Symp. on Theoretical Aspects of Computer Science (STACS), 2009.
[ arxiv ]
Randomly removing g handles at once.
Glencora Borradaile, James Lee and Anastasios Sidiropoulos.
Computational Geometry: Theory and Applications special issue for SoCG 2009, volume 43, 2010.
Symposium on Computational Geometry (SoCG), 2009.
[ arXiv ]
A polynomial-time approximation scheme for Euclidean Steiner forest.
Glencora Borradaile, Philip Klein and Claire Mathieu.
Foundations of Computer Science (FOCS), 2008.
[ pdf ]
Other
Batch Active Learning via Coordinating Matching
Javad Azimi, Alan Fern, Xiaoli Fern, Glencora Borradaile, and Brent Heeringa.
International Conference on Machine Learning (ICML), 2012.
[ to appear ]
Approximation algorithms for constrained knapsack problems
Glencora Borradaile, Brent Heeringa and Gordon Wilfong.
Journal of Discrete Algorithms special issue for IWOCA 2011, 2012.
International Workshop on Combinatorial Algorithms (IWOCA), 2011.
[ arXiv ][ journal doi ]
Planarity Testing
Entry in the Encyclopedia of Algorithms, edited by Ming-Yang Kao. 2008.
[ pdf ]
Safe and tight linear estimators for global optimization.
Glencora Borradaile and Pascal Van Hentenryck.
Mathematical Programming, 102(3), 2005.
[ pdf ]
Dissertation
Exploiting Planarity for Network Flow and Connectivity Problems
Glencora Borradaile.
Brown University. December 2007.
[ pdf ]