23 citations · 42 across the 17 of their papers we have counts for
Showing 2010 · cs.DMShow all
3 papers · 2 filters
cs.DM2010★ 1 cited
Integrality Gap of the Hypergraphic Relaxation of Steiner Trees: a short proof of a 1.55 upper bound
Deeparnab Chakrabarty, Jochen Koenemann, David Pritchard
Recently Byrka, Grandoni, Rothvoss and Sanita (at STOC 2010) gave a 1.39-approximation for the Steiner tree problem, using a hypergraph-based linear programming relaxation. They al…
cs.DM2010★ 3 cited
An LP with Integrality Gap 1+epsilon for Multidimensional Knapsack
David Pritchard
In this note we study packing or covering integer programs with at most k constraints, which are also known as k-dimensional knapsack problems. For any integer k > 0 and real epsil…
cs.DM2010★ 2 cited
k-Edge-Connectivity: Approximation and LP Relaxation
David Pritchard
In the k-edge-connected spanning subgraph problem we are given a graph (V, E) and costs for each edge, and want to find a minimum-cost subset F of E such that (V, F) is k-edge-conn…