# Flows With Geometric and Topological Constraints

December 2022

## Abstract

We describe several results on flow problems with geometric and topological constraints. More specifically, we present two near-linear time approximation schemes for the geometric transportation problem. The first one is a randomized algorithm running in near-linear time for arbitrary input, and the second one is a deterministic algorithm running in near-linear time if the input has a polynomially bounded spread. While these two algorithms solve the transportation problem with certain geometric constraints, in the rest of this dissertation we describe some new preliminary observations for computing maximum flows in planar embedded graphs as well as some new algorithms inspired by those observations. We first describe an algorithm that runs in nε−O(d) logO(d) n time and returns a (1 + ε)- approximation to the optimal transportation map for the geometric transportation problem, with high probability. This algorithm is the first one that runs in near-linear time for any input. It first reduces the problem into the problem of seeking a minimum cost flow of a sparse spanner with a (1 + O(ε))-distortion of the point-to-point distance, then computes a (1 + O(ε))-approximation to the minimum cost flow using Sherman’s preconditioning framework, and finally extracts a transportation map from the minimum cost flow without increasing the cost. The second algorithm for the geometric transportation problem we present is a deterministic (1 + O(ε))-approximation scheme running in nε−O(d)(log n + log2 Sp(P ) log log Sp(P )) log Sp(P ) time where Sp(P ) represents the spread of the point set P given by the input. It uses a spanner with a deterministic (1 + O(ε))- distortion by increasing the size of the spanner by a factor of at most 2d in comparison to the one we use in the first algorithm. We close by describing some new results for computing maximum flows in planar embedded graphs. We describe a novel way to analyze the number of times a dart u → v can enter the residual (u, t)-path when we compute maximum flows using leftmost pushes. Eisenstat and Klein describe a linear-time algorithm for a special case of the maximum st flow problem where the arc capacities are small integers. Our new observations show their algorithm could actually run in O(n2) time in the worst case and imply an easy fix to a faulty claim of theirs. Then we describe a new preflow-push lemma for computing maximum flows in the plane and ongoing work in designing new maximum flow algorithms using this lemma. Finally, we consider a special case of the multiple-source multiple-sink maximum flow problem in the plane where all sources and sinks are among the same face. We describe the first linear-time algorithm for this problem if all edges have small integer capacities. For the same problem, we also describe a simple algorithm that runs in O(n log n log k) time without the small integer capacity assumption.

Computer Science