Vera Traub

The single-source unsplittable flow (SSUF) problem asks to send flow from a common source to terminals with unrelated demands, each terminal being served through a single path. The classical SSUF objective is to minimize the violation of some given arc capacities. A seminal result of Dinitz, Garg, and Goemans showed that, whenever a fractional flow exists respecting the capacities, then there is an unsplittable one violating the capacities by at most the maximum demand. Goemans conjectured a natural cost version of the same result, where the unsplittable flow is required to be no more expensive than the fractional one. Intriguingly, there are arguably no non-trivial graph classes for which it is known to hold. We show that a slight weakening of it holds for planar graphs, by exploiting a connection to a highly structured discrepancy problem. Moreover, our techniques extend to simultaneous upper and lower bounds on the flow values. This affirmatively answers a conjecture of Morell and Skutella for planar SSUF. Finally, we show that our approach can be extended to general (non-planar) graphs with a capacity violation that depends on the genus.

The Steiner Tree problem asks for the cheapest way of connecting a given subset of the vertices in an undirected graph. One of the most prominent linear programming relaxations for Steiner Tree is the Bidirected Cut Relaxation (BCR). Determining the integrality gap of this relaxation is a long-standing open question. For several decades, the best known upper bound was 2, which is achievable by standard techniques. Only very recently, Byrka, Grandoni, and Traub [FOCS 2024] showed that the integrality gap of BCR is strictly below 2. We prove that the integrality gap of BCR is at most 1.898, improving significantly on the previous bound of 1.9988. For the important special case where a terminal minimum spanning tree is an optimal Steiner tree, we show that the integrality gap is at most 12/7, by providing a tight analysis of the dual-growth procedure by Byrka et al. To obtain the general bound of 1.898 on the integrality gap, we generalize their dual growth procedure to a broad class of moat-growing algorithms. Moreover, we prove that no such moat-growing algorithm yields dual solutions certifying an integrality gap below 12/7. Finally, we observe an interesting connection to the Hypergraphic Relaxation.

Finding a smallest subgraph that is k-edge-connected, or augmenting a k-edge-connected graph with a smallest subset of given candidate edges to become (k+1)-edge-connected, are among the most fundamental Network Design problems. They are both APX-hard in general graphs. However, this hardness does not carry over to the planar setting, which is not well understood, except for very small values of k. One main obstacle in using standard decomposition techniques for planar graphs, like Baker's technique and extensions thereof, is that connectivity requirements are global (rather than local) properties that are not captured by existing frameworks. We present a novel, and arguably clean, decomposition technique for such classical connectivity problems on planar graphs. This technique immediately implies PTASs for the problems of finding a smallest k-edge-connected or k-vertex-connected spanning subgraph of a planar graph for arbitrary k. By leveraging structural results for minimally k-edge-connected graphs, we further obtain a PTAS for planar k-connectivity augmentation for any constant k. We complement this with an NP-hardness result, showing that our results are essentially optimal.

A famous conjecture of Goemans on single-source unsplittable flows states that one can turn any fractional flow into an unsplittable one of no higher cost, while increasing the load on any arc by at most the maximum demand. Despite extensive work on the topic, only limited progress has been made. Recently, Morell and Skutella suggested an alternative conjecture, stating that one can turn any fractional flow into an unsplittable one without changing the load on any arc by more than the maximum demand. We show that their conjecture implies Goemans' conjecture (with a violation of twice the maximum demand). To this end, we generalize a technique of Linhares and Swamy, used to obtain a low-cost chain-constrained spanning tree from an algorithm without cost guarantees. Whereas Linhares and Swamy's proof relies on Langrangian duality, we provide a very simple elementary proof of a generalized version, which we hope to be of independent interest. Moreover, we show how this technique can also be used in the context of the weighted ring loading problem, showing that cost-unaware approximation algorithms can be transformed into approximation algorithms with additional cost guarantees.

In Asymmetric A Priori TSP (with independent activation probabilities) we are given an instance of the Asymmetric Traveling Salesman Problem together with an activation probability for each vertex. The task is to compute a tour that minimizes the expected length after short-cutting to the randomly sampled set of active vertices. We prove a polynomial lower bound on the adaptivity gap for Asymmetric A Priori TSP. Moreover, we show that a poly-logarithmic approximation ratio, and hence an approximation ratio below the adaptivity gap, can be achieved by a randomized algorithm with quasi-polynomial running time. To achieve this, we provide a series of polynomial-time reductions. First we reduce to a novel generalization of the Asymmetric Traveling Salesman Problem, called Hop-ATSP. Next, we use directed low-diameter decompositions to obtain structured instances, for which we then provide a reduction to a covering problem. Eventually, we obtain a polynomial-time reduction of Asymmetric A Priori TSP to a problem of finding a path in an acyclic digraph minimizing a particular objective function, for which we give an O(log n)-approximation algorithm in quasi-polynomial time.