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

David Pritchard's papers and talks

• 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 J. Disc. Math., 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
  Preliminary version at 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.
• Characterizing and Recognizing Generalized Polymatroids with András Frank, Tamás Király, Júlia Pap
  Egres Technical Report, 2012 and submitted to a journal
  
  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.
• On Approximating String Selection Problems with Outliers with Christina Boucher, Gad M. Landau, Avivit Levy, Oren Weimann
  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 J. Disc. Math., 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 d₁ > d₂ > … denote the set of all distances between pairs of vertices, and let m_i be the number of pairs of vertices at distance d_i from one another. Erdős, Lovász, and Vesztergombi conjectured that Σ_{i ≤ k} m_i ≤ 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} m_i ≤ (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 m₃ ≤ 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|²/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 A, 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 c_e 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.
• Practical Advice for Small Group Learning in Undergraduate Mathematics
  Poster for 2008 Waterloo Graduate Student Research Conference; part of Certificate in University Teaching Program This poster was one of the activities forming part of the Certificate in University Teaching I obtained at the University of Waterloo. The poster is about how to use group activities most effectively in mathematics. The sections discuss pedagogy, motivation, caveats, concrete examples for a game theory course, and student quotes from the literature.
• Nearest Neighbor Network Traversal
  arXiv report based on chapter in my Master's thesis | slides A mobile agent in a network wants to visit every node of an n-node network, using a small number of steps. We investigate the performance of the following "nearest neighbor" heuristic: always go to the nearest unvisited node. If the network graph never changes, then from (Rosenkrantz, Stearns and Lewis, 1977) and (Hurkens and Woeginger, 2004) it follows that Θ(n log n) steps are necessary and sufficient in the worst case. We give a simpler proof of the upper bound and an example that improves the best known lower bound. We investigate how the performance of this heuristic changes when it is distributively implemented in a network. Even if network edges are allow to fail over time, we show that the nearest neighbor strategy never runs for more than O(n²) iterations. We also show that any strategy can be forced to take at least n(n-1)/2 steps before all nodes are visited, if the edges of the network are deleted in an adversarial way.
• Efficient Divide-and-Conquer Implementations Of Symmetric FSAs
  Special issue of Journal of Cellular Automata, 2010 | Talk at Automata 2007 | slides | audio A deterministic finite-state automaton (FSA) is an abstract sequential machine that reads the symbols comprising an input word one at a time. An FSA is symmetric if its output is independent of the order in which the input symbols are read, i.e., if the output is invariant under permutations of the input. We show how to convert a symmetric FSA A into an automaton-like divide-and-conquer process whose intermediate results are no larger than the size of A's memory. In comparison, a similar result for general FSA's has been long known via functional composition, but entails an exponential increase in memory size. The new result has applications to parallel processing and symmetric FSA networks.
• Symmetric Network Computation with Santosh Vempala
  SPAA 2006 | slides | Java demo We introduce a simple new model of distributed computation, finite-state symmetric graph automata (FSSGA) which captures the qualitative properties common to fault-tolerant distributed algorithms. Roughly speaking, the computation evolves homogeneously in the entire network, with each node acting symmetrically and with limited resources. As a building block, we demonstrate the equivalence of two automaton models for computing symmetric multi-input functions. We give FSSGA algorithms for several well-known problems.
• An Optimal Distributed Bridge-Finding Algorithm
  Best Poster, PODC 2006 | writeup | slides We give an O(Diameter)-time distributed algorithm to compute all of the bridges (a.k.a. cut edges) and 2-edge-connected components, which works in the "congestion" model where nodes initially have no knowledge of the graph topology, and messages are limited to logarithmic size. We show that this algorithm is universally optimal, meaning that no correct algorithm can be faster by more than a constant factor on any graph.
• Robust Network Computation
  M. Eng Thesis, MIT, supervisor Santosh Vempala, August 2005 The main part not appearing elsewhere is Chapter 6, which discusses the following situation. What if every node of the graph stores a value, and then repeatedly takes the average of its neighbours' values? This computes a discrete harmonic function, given some "boundary" points with fixed values. We give some properties and interpretations of this process, and applications to distributed computing.