We introduce and study a directed analogue of the weighted Tree Augmentation Problem (WTAP). In the weighted Directed Tree Augmentation Problem (WDTAP), we are given an oriented tree \(T = (V,A)\) and a set of directed links \(L \subseteq V \times V\) with positive costs. The goal is to select a minimum cost set of links which enters each fundamental dicut of \(T\) (cuts with one leaving and no entering tree arc). WDTAP captures the problem of covering a cross-free set family with directed links. It can also be used to solve weighted multi 2-TAP, in which we must cover the edges of an undirected tree at least twice. WDTAP can be approximated to within a factor of 2 using standard techniques. We provide an improved (\(1.75 + \varepsilon\))-approximation algorithm for WDTAP in the case where the links have bounded costs, a setting that has received significant attention forWTAP. To obtain this result, we discover a class of instances, called “willows”, for which the natural set covering LP is an integral formulation. We further introduce the notion of “visibly \(k\)-wide” instances which can be solved exactly using dynamic programming. Finally, we show how to leverage these tractable cases to obtain an improved approximation ratio via an elaborate structural analysis of the tree.

We consider connectivity augmentation problems in the Steiner setting, where the goal is to augment the edge-connectivity between a specified subset of terminal nodes. In the Steiner Augmentation of a Graph problem ($k$-SAG), we are given a $k$-edge-connected subgraph $H$ of a graph $G$. The goal is to augment $H$ by including links from $G$ of minimum cost so that the edge-connectivity between nodes of $H$ increases by 1. This is a generalization of the Weighted Connectivity Augmentation Problem, in which only links between pairs of nodes in $H$ are available for the augmentation. In the Steiner Connectivity Augmentation Problem ($k$-SCAP), we are given a Steiner $k$-edge-connected graph connecting terminals $R$, and we seek to add links of minimum cost to create a Steiner $(k+1)$-edge-connected graph for $R$. Note that $k$-SAG is a special case of $k$-SCAP. The results of Ravi, Zhang and Zlatin for the Steiner Tree Augmentation problem yield a $(1.5+\varepsilon)$-approximation for $1$-SCAP and for $k$-SAG when $k$ is odd (SODA'23). In this work, we give a $(1 + \ln{2} +\varepsilon)$-approximation for the Steiner Ring Augmentation Problem (SRAP). This yields a polynomial time algorithm with approximation ratio $(1 + \ln{2} + \varepsilon)$ for $2$-SCAP. We obtain an improved approximation guarantee for SRAP when the ring consists of only terminals, yielding a $(1.5+\varepsilon)$-approximation for $k$-SAG for any $k$.

Online resource allocation is a rich and var-ied field. One of the most well-known problems in this area is online bipartite matching, introduced in 1990 by Karp, Vazirani, and Vazirani. Since then, many variants have been studied, including AdWords, the generalized assignment problem (GAP), and online submodular welfare maximization. In this paper, we introduce a generalization of GAP which we call the submodular assignment problem (SAP). This generalization captures many online assignment problems, including all classical online bipartite matching problems as well as broader online combinatorial optimization problems such as online arboricity, flow scheduling, and laminar restricted allocations. We present a fractional algorithm for online SAP that is$(1-1/e)$-competitive. Additionally, we study several integral special cases of the problem. In particular, we provide a$(1\ -1/e-\varepsilon){-}$competitive integral algorithm under a small-bids assumption, and a$(1\ -1/e)$-competitive integral algorithm for online submodular welfare maximization where the utility functions are given by rank functions of matroids. The key new ingredient for our results is the construction and structural analysis of a “water level” vector for polymatroids, which allows us to generalize the classic water-filling paradigm used in online matching problems. This construction reveals connections to submodular utility allocation markets and principal partition sequences of matroids.

In the Steiner Tree Augmentation Problem (STAP), we are given a graph G = (V,E), a set of terminals R ⊆ V, and a Steiner tree T spanning R. The edges L: = E\E(T) are called links and have non-negative costs. The goal is to augment T by adding a minimum cost set of links, so that there are 2 edge-disjoint paths between each pair of vertices in R. This problem is a special case of the Survivable Network Design Problem, which can be approximated to within a factor of 2 using iterative rounding [13]. We give the first polynomial time algorithm for STAP with approximation ratio better than 2. In particular, we achieve an approximation ratio of (1.5 + ε). To do this, we employ the Local Search approach of [24] for the Tree Augmentation Problem and generalize their main decomposition theorem from links (of size two) to hyper-links. We also consider the Node-Weighted Steiner Tree Augmentation Problem (NW-STAP) in which the non-terminal nodes have non-negative costs. We seek a cheapest subset S ⊆ V\R so that G[R ∪ S] is 2-edge-connected. Using a result of Nutov [18], there exists an O(log |R|)-approximation for this problem. We provide an O(log2(|R|))-approximation algorithm for NW-STAP using a greedy algorithm leveraging the spider decomposition of optimal solutions.

Abstract. Let [Formula: see text] be a digraph. A dicut is a cut [Formula: see text] for some nonempty proper vertex subset [Formula: see text] such that [Formula: see text], a dijoin is an arc subset that intersects every dicut at least once, and more generally a [Formula: see text]- dijoin is an arc subset that intersects every dicut at least [Formula: see text] times. Our first result is that [Formula: see text] can be partitioned into a dijoin and a [Formula: see text]-dijoin where [Formula: see text] denotes the smallest size of a dicut. Woodall conjectured the stronger statement that [Formula: see text] can be partitioned into [Formula: see text] dijoins. Let [Formula: see text], and suppose every dicut has weight at least [Formula: see text], for some integer [Formula: see text]. Let [Formula: see text], where each [Formula: see text] is the integer in [Formula: see text] equal to [Formula: see text] mod [Formula: see text]. We prove the following results: If [Formula: see text], then there is an equitable [Formula: see text]-weighted packing of dijoins of size [Formula: see text]. If [Formula: see text], then there is a [Formula: see text]-weighted packing of dijoins of size [Formula: see text]. If [Formula: see text], [Formula: see text], and [Formula: see text], then [Formula: see text] can be partitioned into three dijoins. Each result is best possible: (i) does not hold for [Formula: see text] even if [Formula: see text], (ii) does not hold for [Formula: see text], and (iii) does not hold for general [Formula: see text].