You can go back to my homepage or to math circles and software.

### David Pritchard's papers and talks

• Characterizing and Recognizing Generalized Polymatroids with András Frank, Tamás Király, Júlia Pap
Mathematical Programming, to appear
Egres Technical Report, 2012
Generalized polymatroids are a family of polyhedra with several nice properties and applications. One property of generalized polymatroids used widely in existing literature is "total dual laminarity;" we make this notion explicit and show that only generalized polymatroids have this property. Using this we give a polynomial-time algorithm to check whether a given linear program defines a generalized polymatroid, and whether it is integral if so. Additionally, whereas it is known that the intersection of two integral generalized polymatroids is integral, we show that no larger class of polyhedra satisfies this property.
• CS Circles: An In-Browser Python Course for Beginners with Troy Vasiga
SIGCSE 2013 | slides
Earlier talk CS Circles: Learning Python in One Browser Window with Graeme Kemkes
(2012 AMS-MAA Joint Math Meetings and CSTA) We developed a website for first-time programmers to learn Python in an easy and fun manner. Each webpage contains instructions intermingled with many types of exercises. Anyone can use it for free; in its first year, 4000 people completed 90000 exercises on the site. It is a project of Centre for Education in Mathematics and Computing at the University of Waterloo. Visit it at: http://cscircles.cemc.uwaterloo.ca
• Hypergraphic LP Relaxations for Steiner Trees with Deeparnab Chakrabarty, Jochen Könemann
SIAM Journal on Discrete Mathematics, 2013
IPCO 2010 | slides
Prehistoric version: Uncrossing Partitions, Report CORR 2007-11, University of Waterloo | poster
We show that several hypergraphic LP relaxations for the Steiner tree problem are equivalent, using new uncrossing techniques and structural properties. Most surprisingly, in the well-studied case where no Steiner-Steiner edges exist, we show they are also equivalent to the graph-based bidirected cut relaxation. We also obtain a 1.74-approximation algorithm when the full components arrive "online."
• Multicommodity Flow in Trees: Packing via Covering and Iterated Relaxation with Jochen Könemann and Ojas Parekh
Algorithmica, 2012
WAOA 2008 | slides
We consider the max-weight integral multicommodity flow problem in trees. In this problem we are given an edge, arc, or vertex-capacitated tree and weighted pairs of terminals, and the objective is to find a max-weight integral flow between terminal pairs subject to the capacities. This problem is APX-hard and a 4-approximation for the edge- and arc-capacitated versions is known. Some special cases are exactly solvable in polynomial time, including when the graph is a path or a star. We show that all three versions of this problems fit in a common framework: first, prove a counting lemma in order to use the iterated LP relaxation method; second, solve a covering problem to reduce the resulting infeasible solution back to feasibility without losing much weight. The result of the framework is a 1 + O(1/μ)-approximation algorithm where μ denotes the minimum capacity, for all three versions. A complementary hardness result shows this is asymptotically best possible. For the covering analogue of multicommodity flow, we also show a 1 + Θ(1/μ) approximability threshold with a similar framework. When the tree is a spider (i.e. only one vertex has degree greater than 2), we give a polynomial-time exact algorithm and a polyhedral description of the convex hull of all feasible solutions. This holds more generally for instances we call root-or-radial.
• On Approximating String Selection Problems with Outliers with Christina Boucher, Gad M. Landau, Avivit Levy, Oren Weimann
Theoretical Computer Science, to appear
CPM 2012
We look at several problems related to Closest String, but with the ability to classify some strings as outliers. One main result is about Close to Most Strings: given a set S of same-length strings, and a parameter d, find a string within Hamming ditance d of the maximum number of inputs. We show this problem has no polynomial-time approximation scheme (PTAS) unless NP has randomized polynomial-time algorithms, fixing a decade-old error. The Most Strings with Few Bad Columns problem is to find a maximum-size subset of input strings so that the number of non-identical positions is at most k; we show it has no PTAS unless P=NP. We also observe Closest to k Strings has no EPTAS unless W[1]=FPT.
• Cover-Decomposition and Polychromatic Numbers with Béla Bollobás, Thomas Rothvoß, Alex Scott
SIAM Journal on Discrete Mathematics, 2013 | slides
ESA 2011
As the minimum degree of a graph grows, so does the number of edge-disjoint edge covers. Many papers in geometry investigate the same phenomenon in geometric hypergraphs. In this paper, we analyze the abstract problem without regard to geometry. For example, fixing the maximum hyperedge size, we get a near-tight bound on the minimum number of disjoint edge covers as a function of degree. To accomplish this, we link iterated LP relaxation to cover-decomposition via discrepancy theory. Our results encompass two other families: hypergraphs corresponding to path covers of trees, and hypergraphs with bounded VC-dimension.
• Fast Computation of Small Cuts via Cycle Space Sampling with Ramakrishna Thurimella
ACM Transactions on Algorithms, 2011 | slides
ICALP 2008, Fast Distributed Computation of Cuts Via Random Circulations (preliminary version)
In distributed computing, the nodes of a graph are computers, and they communicate using logarithmic-size messages on the edges. They start with no information but their neighbours' names, and want to quickly compute properties of their unknown topology. We give an O(Diameter)-time algorithm to find all 2-edge cuts. This is simpler and faster than previous results, and even optimal on all graphs. The approach is based on uniformly sampling at random from the cycle space. It gives a simple sequential O(|E|)-time algorithm, as well as efficient parallel algorithms.
• Counting Large Distances in Convex Polygons with Filip Morić
Chapter in Thirty Essays on Geometric Graph Theory (J. Pach, ed.), 2013
Abstract at Eurocomb 2011 | slides | Java code In a convex n-gon, let d1 > d2 > … denote the set of all distances between pairs of vertices, and let mi be the number of pairs of vertices at distance di from one another. Erdős, Lovász, and Vesztergombi conjectured that Σi ≤ k mi ≤ kn. Using a new computational approach, we prove their conjecture when k ≤ 4 and n is large; we also make some progress for arbitrary k by proving that Σi ≤ k mi ≤ (2k-1)n. Our main approach revolves around a few known facts about distances, together with a computer program that searches all small configurations of distances generated by two disjoint intervals. We thereby obtain other new bounds such as m3 ≤ 3n/2 for large n.
• Diameter Bounds for Planar Graphs with Radoslav Fulek, Filip Morić
Discrete Mathematics, 2011 | Sage calculations 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 inverse degree, and that this ratio is tight. To develop a crucial surgery method, we begin by proving the simpler related upper bounds (4(|V|-1)/|E|)/3 and 4|V|2/3|E| on the diameter (for connected planar graphs), which are also tight.
• Approximability of Sparse Integer Programs with Deeparnab Chakrabarty
Special issue of Algorithmica, 2011
ESA 2009 | slides
We investigate nonnegative integer programs of the form Ax ≥ b (covering) or Ax ≤ b (packing), which arise in theory and practice. Can good approximation algorithms be obtained if we limit the number of nonzero entries per row or column of A? We initiate this study. Of the 4 combinations, two were already solved. We close one, giving a k-approximation for k-row-sparse covering problems. We also give the first approximation algorithm for k-column-sparse packing problems.
• Integrality Gap of the Hypergraphic Relaxation of Steiner Trees with Deeparnab Chakrabarty, Jochen Könemann
Operations Research Letters, 2010
The breakthrough 2010 paper of Byrka et al used randomized iterated LP rounding to get a 1.39-approximation for the Steiner tree problem. As a bonus, those authors also re-analyzed the complex Robins-Zelikovsky algorithm to prove a 1.55 integrality gap. Here, we give a simpler proof of the 1.55 integrality gap, using a simple algorithm that fits in the framework of Byrka et al.
• k-Edge-Connectivity: Approximation and LP Relaxation
WAOA 2010 | slides 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 F ⊆ E such that (V, F) is k-edge-connected. We show there is a constant ε > 0 so that for all k > 1, finding a (1 + ε)-approximation for k-ECSS is NP-hard, establishing a gap between the unit-cost and general-cost versions. Next, we consider the multi-subgraph cousin of k-ECSS, in which we purchase a multi-subset F of E, with unlimited parallel copies available at the same cost as the original edge. We conjecture that a (1 + O(1/k))-approximation algorithm exists, and we describe an approach based on graph decompositions applied to its natural linear programming (LP) relaxation. The LP is essentially equivalent to the Held-Karp LP for TSP and the undirected LP for Steiner tree. We give a family of extreme points for the LP which are more complex than those previously known.
• Linear Programming Tools and Approximation Algorithms for Combinatorial Optimization
Ph.D. Thesis, University of Waterloo, supervisor Jochen Könemann, December 2009 Most of my thesis appeared in other papers, but readers interested in hypergraphic Steiner tree LPs may want to check out the following additional results that we did not try to publish: §3.5 (computing extreme points), §3.6 (equivalent "gainless tree" formulation), §4.4 (equivalent "restricted bidirected cut" formulation) §4.6 & 4.8 (special classes of graphs), §4.7 & 4.9 (polyhedral properties) and §5.6 (a weird formulation with integrality gap ≤1+ln(2)).
• A Partition-Based Relaxation for Steiner Trees with Jochen Könemann, Kunlun Tan
Mathematical Programming, 2011 The Steiner tree problem is a classical NP-hard optimization problem with a wide range of practical applications. In an instance of this problem, we are given an undirected graph G = (V, E), a set of terminals R⊆V, and non-negative costs ce for all edges e∈E. Any tree that contains all terminals is called a Steiner tree; the goal is to find a minimum-cost Steiner tree. The vertices V\R are called Steiner vertices. The best approximation algorithm known for the Steiner tree problem is a greedy algorithm due to Robins and Zelikovsky (SIAM J Discrete Math 19(1):122–134, 2005); it achieves a performance guarantee of 1+(ln 3)/2 ∼ 1.55. The best known linear programming (LP)-based algorithm, on the other hand, is due to Goemans and Bertsimas (Math Program 60:145–166, 1993) and achieves an approximation ratio of 2-2/|R|. In this paper we establish a link between greedy and LP-based approaches by showing that Robins and Zelikovsky's algorithm can be viewed as an iterated primal-dual algorithm with respect to a novel LP relaxation. The LP used in the first iteration is stronger than the well-known bidirected cut relaxation. An instance is b-quasi-bipartite if each connected component of G\R has at most b vertices. We show that the Robins-Zelikovsky algorithm has an approximation ratio better than 1+(ln 3)/2 for such instances, and we prove that the integrality gap of our LP is between 7/8 and (b+1)/(2b+1).
• An LP with Integrality Gap 1+ε for Multidimensional Knapsack
arXiv report based on chapter in my PhD thesis 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 ε > 0, we observe there is a polynomial-sized LP for the k-dimensional knapsack problem with integrality gap at most 1+ε. The variables may be unbounded or have arbitrary upper bounds. In the packing case, we can also remove the dependence of the LP on the cost-function, yielding a polyhedral approximation of the integer hull. This generalizes a recent result of Bienstock on the classical knapsack problem.