23 citations · 42 across the 17 of their papers we have counts for
4 papers · 1 filter
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…
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…
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…
Hypergraphic LP Relaxations for Steiner Trees
Deeparnab Chakrabarty, Jochen Koenemann, David Pritchard
We investigate hypergraphic LP relaxations for the Steiner tree problem, primarily the partition LP relaxation introduced by Koenemann et al. [Math. Programming, 2009]. Specificall…