23 citations · 42 across the 17 of their papers we have counts for
6 papers · 1 filter
Cover-Decomposition and Polychromatic Numbers
Béla Bollobás, David Pritchard, Thomas Rothvoß +1
A colouring of a hypergraph's vertices is polychromatic if every hyperedge contains at least one vertex of each colour; the polychromatic number is the maximum number of colours in…
Diameter Bounds for Planar Graphs
Radoslav Fulek, Filip Morić, David Pritchard
The inverse degree of a graph is the sum of the reciprocals of the degrees of its vertices. We prove that in any connected planar graph, the diameter is at most 5/2 times the inver…
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…
Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)
Prahladh Harsha, Moses Charikar, Matthew Andrews +14
These are the lecture notes for the DIMACS Tutorial "Limits of Approximation Algorithms: PCPs and Unique Games" held at the DIMACS Center, CoRE Building, Rutgers University on 20-2…