Bruce Shepherd

In a multicommodity flow problem, the goal is to route paths in a supply graph G to satisfy demands between vertices, represented by a demand graph H. This must be done simultaneously for all commodities, without exceeding edge capacities. To do this, there can be no cut where the requested demand exceeds the available capacity. This is called the cut condition. The Max-Flow Min-Cut Theorem states that for single-commodity flows, the cut condition guarantees that a feasible routing exists. This fails for general multicommodity flows.A supply-demand graph pair (G,H) is cut-sufficient if, for all capacity and demand weights, the cut condition implies feasibility. Many results are known for undirected cut-sufficiency. For instance, the cut-sufficient pairs with series-parallel supply graphs have a forbbiden-minor characterization. However, less is known about cut-sufficiency for directed multicommodity flows.We characterize cut-sufficiency for several classes of directed multicommodity flow problems. We consider pairs with roundtrip or two-path demands, where H is a 2-cycle and 2-path, respectively. We prove that the cut-sufficient pairs in these classes are characterized by one and two forbidden minors, respectively. We also consider pairs with two disjoint demands. For these, we give a forbidden-minor characterization of the pairs that are cut-sufficient for unit demands, and conjecture about their cut-sufficiency with arbitrary weights.Unlike the undirected case, for directed graphs the class of cut-sufficient pairs is not closed under taking minors. To solve this, we develop a theory of relevant minors, which restricts permitted contractions to restore the closure of cut-sufficiency. Our characterizations are in terms of forbidden relevant minors.As an application of our results, we show that recognizing cut-sufficiency is NP-hard for roundtrip demands. This contrasts with undirected two-commodity flows, for which supply-demand graph pairs are always cut-sufficient.We also provide a primal proof of the fact that any orientation of an undirected tree is cut-sufficient with any directed demand graph. This was previously known, but was proven via the dual method of metric embeddings. We prove trees are the only graphs with this property.

View record

Good approximations have been attained for the sparsest cut problem by rounding solutions to convex relaxations via low-distortion metric embeddings [5, 24]. Recently, Bryant and Tupper showed that this approach extends to the hypergraph setting by formulating a linear program whose solutions are diversities which are rounded via diversity embeddings into ?1 [31]. Diversities are a generalization of metric spaces in which the nonnegative function is defined on all subsets as opposed to only on pairs of elements. We show that this approach yields an O(logn)-approximation when either the supply or demands are given by a graph. This result improves upon Plotkin et al.’s O(log(kn)logn)-approximation [28], where k is the number of demands, in the setting where the supply is given by a graph and the demands are given by a hypergraph. Additionally, we provide an O(min{rG,rH}log(rH)logn)-approximation for when the supply and demands are given by hypergraphs whose hyperedges are bounded in cardinality by rG and rH respectively. To establish these results we provide an O(logn)-distortion ?1 embedding for the class of diversities known as diameter diversities. This improves upon Bryant and Tupper’s O((logn)^2)-distortion embedding [31]. The smallest known distortion with which an arbitrary diversity can be embedded into ?1 is O(n). We show that for any ε > 0 and any p > 0, there is a family of diversities which cannot be embedded into ?1 in polynomial time with distortion smaller than O(n^(1−ε)) based on querying the diversities on sets of cardinality at most O((logn)ˆp), unless P = NP. This disproves (an algorithmic refinement) of Bryant and Tupper’s conjecture that there exists an O(√n)-distortion ?1 embedding based off a diversity’s induced metric. In addition, we demonstrate via hypergraph cut sparsifiers that it is sufficient to develop a low-distortion embedding for diversities induced by sparse hypergraphs for the purpose of obtaining good approximations for the sparsest cut in hypergraphs.

View record

In this thesis, we study the Multidimensional Knapsack Problem (MKP) and two closely related special cases: the Unsplittable Flow Problem on Trees (UFPT), and the Unsplittable Flow Problem on Paths (UFPP). For these problems, when the natural integer programming formulation is relaxed to a linear program, the integrality gap is O(n). Previous work on UFPT and UFPP has established that the addition of rank constraints to the linear program can be effective in some cases at reducing the integrality gap. However, Friggstad and Gao proved that even with all rank constraints added, the integrality gap of UFPT is Ω(√(log n)). Faenza and Sanità showed that a formulation for these problems which approximates the integer hull arbitrarily well must either have exponentially many facets or be described as an extended formulation (i.e., described in a higher dimensional space). We are interested in polynomially sized formulations, so we focus our study on extended formulations. Our first contribution is a greedy algorithm which finds an optimal solution to the linear programming relaxation for the special case of UFPT where all requests share a common endpoint. We apply this to tighten the analysis of hard instances described in the literature. Following this, we describe two approximate extended formulations for MKP using disjunctive programming. The first is a formulation which improves upon the integrality gap of the linear relaxation using only a small number of extra variables and constraints. The second is a polyhedral (1 - ε)-approximate extended formulation for MKP for any 0
View record

We investigate the problem of designing (preferably optimal) online contention resolution schemes (OCRSs). They are a powerful framework for optimization under various combinatorial constraints such as matroids, matchings, knapsacks and their intersections. OCRSs immediately imply prophet inequalities in Bayesian online selection problem. They also have other important applications such as stochastic probing and oblivious posted price mechanisms.We present several novel OCRSs which improve the current state-of-the-art algorithms. We design an optimal 0.5-selectable OCRS over matroids with rank 2, and another optimal 0.5-selectable OCRS over transversal matroids. Previously the best result applicable to these types of matroids was a 0.25-selectable OCRS. Furthermore, we design a 1/(k+1)-selectable OCRS over matchings in k-partite hypergraphs.

View record

In this thesis we investigate the core, or the set of stable solutions, of a cooperative game without side payments. This "multicommodity flow" game was initiallyintroduced by Papadimitriou to model incentives in internet routing. He posed thequestions of whether such stable solutions exist and if we can find them. Markakisand Saberi showed both how to solve this game in the setting with side payments,and that such stable solutions always exist with or without side payments. Yamadaand Karasawa provide an algorithm for generating one core solution in the specialcase when the underlying transit graph is a path (as well as special cases of trees).We provide a new algorithm for generating more core elements and a method to testcore membership efficiently in this same special case. We empirically characterizethis larger set of solutions. The data suggests that stability does not necessarilyimpede efficiency, and that there is little trade-off between efficiency and fairness.

View record