Approximation Algorithms for Constrained Knapsack Problems (2009)
Borradaile, Glencora, Heeringa, Brent, Wilfong, Gordon
We study constrained versions of the knapsack problem in which dependencies between items are given by a graph. In one version, an item can be selected only if one of its neighbours is also selected....
Borradaile, Glencora, Demaine, Erik D., Tazari, Siamak
We present the first polynomial-time approximation schemes (PTASes) for the following subset-connectivity problems in edge-weighted graphs of bounded genus: Steiner tree, low-connectivity...
Borradaile, Glencora, Demaine, Erik D., Tazari, Siamak
We present the first polynomial-time approximation schemes (PTASes) for the following subset-connectivity problems in edge-weighted graphs of bounded genus: Steiner tree, low-connectivity...
Borradaile, Glencora, Demaine, Erik D., Tazari, Siamak
We present the first polynomial-time approximation schemes (PTASes) for the following subset-connectivity problems in edge-weighted graphs of bounded genus: Steiner tree, low-connectivity...
Borradaile, Glencora, Demaine, Erik D., Tazari, Siamak
We present the first polynomial-time approximation schemes (PTASes) for the following subset-connectivity problems in edge-weighted graphs of bounded genus: Steiner tree, low-connectivity...
Glencora Borradaile, Philip N. Klein, Claire Mathieu
Steiner tree in planar graphs: An O(n log n)
Glencora Borradaile, Robert Tarjan Reader, Sheila Bonde
By restricting the input to a problem, it often becomes possible to design more accurate or more efficient algorithms to solve that problem. In this thesis we restrict our attention to planar graphs...
Glencora Borradaile, Philip N. Klein
Abstract. We give an algorithm that, for any ɛ>0, any undirected planar graph G,andanysetS of nodes of G, computes a (1+ɛ)-optimal Steiner tree in G that spans the nodes of S. The algorithm...
A polynomial-time approximation scheme for Steiner tree in planar graphs (2007)
Glencora Borradaile, Claire Kenyon-mathieu, Philip Klein
We give an O(n log n) approximation scheme for Steiner tree in planar graphs. 1
An O(n log n) Approximation Scheme for Steiner Tree in Planar Graphs (2007)
Glencora Borradaile, Philip N. Klein, Claire Mathieu
We give an O(n log n) approximation scheme for the Steiner tree problem in planar graphs. 1
A polynomial-time approximation scheme for Steiner tree in planar graphs (2007)
Glencora Borradaile, Claire Kenyon-mathieu, Philip Klein
We give an O(n log n) approximation scheme for Steiner tree in planar graphs. 1
Safe and tight linear estimators for global optimization (2003)
Glencora Borradaile, Pascal Van Hentenryck
Abstract. Global optimization problems are often approached by branch and bound algorithms which use linear relaxations of the nonlinear constraints computed from the current variable bounds. This...
Safe and tight linear estimators for global optimization (2003)
Glencora Borradaile, Pascal Van Hentenryck
Abstract. Global optimization problems are often approached by branch and bound algorithms which use linear relaxations of the nonlinear constraints computed from the current variable bounds. This...
Safe and tight linear estimators for global optimization (2003)
Glencora Borradaile, Pascal Van Hentenryck
Abstract. Global optimization problems are often approached by branch and bound algorithms which use linear relaxations of the nonlinear constraints computed from the current variable bounds. This...
Safe and tight linear estimators for global optimization (2003)
Glencora Borradaile, Pascal Van Hentenryck
Abstract. Global optimization problems are often approached by branch and bound algorithms which use linear relaxations of the nonlinear constraints computed from the current variable bounds. This...
Safe and Tight Linear Estimators (2003)
For Global Optimization, Glencora Borradaile, Pascal Van Hentenryck
Global optimization problems are often approached by branch and bound algorithms which use linear relaxations of the nonlinear constraints computed from the current variable bounds. This paper...