Let G=(V,E) be a supply graph and H=(V,F) a demand graph defined on the same set of vertices. An assignment of capacities to the edges of G and demands to the edges of H is said to satisfy the cut condition if for any cut in the graph, the total demand crossing the cut is no more than the total capacity crossing it. The pair (G,H) is called cut-sufficient if for any assignment of capacities and demands that satisfy the cut condition, there is a multiflow routing the demands defined on $H$ within the network with capacities defined on G.

Imprecise points are points in R2 whose exact location is unknown. For each point, we only know it is contained in a region of R2, which is called the uncertainty region of the point. The research we present in this video focuses on the problem of finding the minimum perimeter convex hull of a set of imprecise points, where each uncertainty region is closed, convex, and the regions may intersect. We first present and animate our theoretical findings: as each point moves inside its uncertainty region, the perimeter of the resulting convex hull is a convex function on the position of the points; as a consequence, any local minimum of the perimeter is a global minimum. We then show the possible positions of imprecise points inside their uncertainty region. Finally, we demonstrate an algorithm for finding the minimum perimeter convex hull of a set of imprecise points.

We present an implementation of a reverse-search algorithm of Fukuda for computing Minkowski sums of polytopes efficiently. The algorithm allows summing any number of polytopes in any dimension, and is complete in the sense that it does not assume general position. Its running time depends linearly on the size of the output. To the best of our knowledge, this is the only existing implementation that can efficiently compute Minkowski sums in higher dimensions. The implementation uses the exact arithmetic GMP, which ensures robustness of the program and exactness of the results. We furthermore present a parallel version of our implementation to demonstrate the simplicity and efficiency of performing the reverse search in parallel. The results of the performance tests show a near-linear acceleration of our parallel implementation.

Consider a routing problem instance consisting of a demand graph H = (V, E(H)) and a supply graph G = (V, E(G)). If the pair obeys the cut condition, then the flow-cut gap for this instance is the minimum value C such that there exists a feasible multiflow for H if each edge of G is given capacity C. It is well-known that the flow-cut gap may be greater than 1 even in the case where G is the (series-parallel) graph K2, 3. In this paper we are primarily interested in the “integer” flow-cut gap. What is the minimum value C such that there exists a feasible integer valued multiflow for H if each edge of G is given capacity C? We formulate a conjecture that states that the integer flow-cut gap is quantitatively related to the fractional flow-cut gap. In particular this strengthens the well-known conjecture that the flow-cut gap in planar and minor-free graphs is O(1) [12] to suggest that the integer flow-cut gap is O(1). We give several technical tools and results on non-trivial special classes of graphs to give evidence for the conjecture and further explore the “primal” method for understanding flow-cut gaps; this is in contrast to and orthogonal to the highly successful metric embeddings approach. Our results include the following: Let G be obtained by series-parallel operations starting from an edge st, and consider orienting all edges in G in the direction from s to t. A demand is compliant if its endpoints are joined by a directed path in the resulting oriented graph. We show that if the cut condition holds for a compliant instance and G + H is Eulerian, then an integral routing of H exists. This result includes, as a special case, routing on a ring, but is not a special case of the Okamura-Seymour theorem. Using the above result, we show that the integer flow-cut gap in series-parallel graphs is 5. The integer flow-cut gap in k-Outerplanar graphs is cO(k) for some fixed constant c. A simple proof that the flow-cut gap is O(log k*) where k* is the size of a node-cover in H; this was previously shown by Günlük via a more intricate proof [11].

We present a tight bound on the exact maximum complexity of Minkowski sums of convex polyhedra in R 3. In particular, we prove that the maximum number of facets of the Minkowski sum of two convex polyhedra with m and n facets respectively is bounded from above by f(m, n) = 4mn−9m−9n+26. Given two positive integers m and n, we describe how to construct two convex polyhedra with m and n facets respectively, such that the number of facets of their Minkowski sum is exactly f(m, n). We generalize the construction to yield a lower bound on the maximum complexity of Minkowski sums of many convex polyhedra in R 3. That is, given k positive integers m1, m2,..., mk, we describe how to construct k convex polyhedra with corresponding number of facets, such that the number of facets of their Minkowski sum is P 1≤i