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. Her Ph.D. dissertation is available at the bottom of the page.
Near-linear-time deterministic plane Steiner spanners and TSP approximation for well-spaced point sets
Glencora Borradaile and David Eppstein.
* Canadian Conference on Computational Geometry (CCCG), 2012.
* Invited to Computational Geometry: Theory and Applications special issue for CCCG 2012.
[ arXiv ]
Connectivity oracles for planar graphs
Glencora Borradaile, Seth Pettie, and Christian Wulff-Nilsen.
* Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2012.
[ arXiv ]
Planted-model evaluation of algorithms for identifying differences between spreadsheets
Anna Harutyunyan, Glencora Borradaile, Christopher Chambers and Christopher Scaffidi.
* IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC), 2012.
[ pdf ]
Batch active learning via coordinating matching
Javad Azimi, Alan Fern, Xiaoli Fern, Glencora Borradaile, and Brent Heeringa.
* International Conference on Machine Learning (ICML), 2012.
[ arXiv ]
Egalitarian Graph Orientations
Glencora Borradaile, Jennifer Iglesias, Theresa Migler, Antonio Ochoa, Gordon Wilfong, Lisa Zhang
* To appear in Discrete Applied Mathematics, 2013.
[ arXiv ]
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 ]
Polynomial-time approximation schemes for connectivity problems in bounded-genus graphs.
Glencora Borradaile, Erik Demaine and Siamak Tazari.
* Algorithmica, 2012.
* Int’l Symp. on Theoretical Aspects of Computer Science (STACS), 2009.
[ 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 ]
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 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 ]
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 ]
A polynomial-time approximation scheme for Euclidean Steiner forest.
Glencora Borradaile, Philip Klein and Claire Mathieu.
* Foundations of Computer Science (FOCS), 2008.
[ arXiv, full version, in journal submission ]
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.
[ arXiv, full version, in journal submission ]
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 ]
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 ]
Exploiting Planarity for Network Flow and Connectivity Problems
Glencora Borradaile.
Dissertation, Brown University, December 2007.
[ pdf ]