Glencora Borradaile






         Assistant Professor, School of Electrical Engineering and Computer Science, Oregon State University

Publications

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 ]

© 2013 Glencora Borradaile   Powered by WordPress MU    Hosted by blogs.oregonstate.edu