25 citations · 78 across the 26 of their papers we have counts for
Showing 2009Show all
2 papers · 1 filter
cs.DS2009
The Knapsack Problem with Neighbour Constraints
Glencora Borradaile, Brent Heeringa, Gordon Wilfong
We study a constrained version of the knapsack problem in which dependencies between items are given by the adjacencies of a graph. In the 1-neighbour knapsack problem, an item can…
cs.DM2009★ 1 cited
Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs
Glencora Borradaile, Erik D. Demaine, Siamak Tazari
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-conne…