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
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,
Theoretical Computer Science, to appear
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=FPT.
Cover-Decomposition and Polychromatic Numbers with Béla Bollobás, Thomas Rothvoß, Alex Scott
SIAM Journal on Discrete Mathematics, 2013 | slides
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
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.
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(n2) 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
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,
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.