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.

Planar induced subgraphs of sparse graphs
Glencora Borradaile, David Eppstein and Pingan Zhu
* To appear: Graph Drawing 2014
[ arXiv ]

Density decompositions of networks
Theresa Migler, Glencora Borradaile and Gordon Wilfong
* preprint, 2014
[ arXiv ] [ accompanying source code ]

Covering nearly surface-embedded graphs with a fixed number of balls
Glencora Borradaile and Erin Wolf Chambers
* Discrete & Computational Geometry, pp. 979-996, volume 54, issue 4, 2014.
[ arXiv ]

A polynomial-time approximation scheme for Euclidean Steiner forest.
Glencora Borradaile, Philip Klein and Claire Mathieu.
* To appear: Transactions on Algorithms.
* Foundations of Computer Science (FOCS), 2008.
[ arXiv ]

Algorithms for Optimization Problems in Planar Graphs
Glencora Borradaile, Philp Klein, Dániel Marx, and Claire Mathieu.
* Dagstuhl Reports, pp. 35–57, volume 3, number 10, 2014.
[ doi ]

Min st-cut oracle for planar graphs with near-linear preprocessing time.
Glencora Borradaile, Piotr Sankowski and Christian Wulff-Nilsen.
* To appear in Transactions on Algorithms.
* Foundations of Computer Science (FOCS), 2010.
[ arXiv ]

Maximum st-flow in directed planar graphs via shortest paths.
Glencora Borradaile and Anna Harutyunyan.
* International Workshop on Combinatorial Algorithms (IWOCA) 2013.
[ arXiv ]

Boundary-to-boundary flows in planar graphs.
Glencora Borradaile and Anna Harutyunyan.
* International Workshop on Combinatorial Algorithms (IWOCA) 2013.
[ arXiv ]

Egalitarian Graph Orientations
Glencora Borradaile, Jennifer Iglesias, Theresa Migler, Antonio Ochoa, Gordon Wilfong, Lisa Zhang
[ arXiv ]

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.
* To appear in 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 ]

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 ]

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 ]

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 ]

Planarity Testing
* Entry in the Encyclopedia of Algorithms, edited by Ming-Yang Kao. 2008.
pdf ]

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 listed above ]

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 ]

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