We address long-standing open questions raised by Williamson, Goemans, Vazirani and Mihail pertaining to the design of approximation algorithms for problems in network design via the primal-dual method (Combinatorica 15(3):435-454, 1995). Williamson et al. prove an approximation guarantee of two for connectivity augmentation problems where the connectivity requirements can be specified by so-called uncrossable functions. They state: “Extending our algorithm to handle non-uncrossable functions remains a challenging open problem. The key feature of uncrossable functions is that there exists an optimal dual solution which is laminar. This property characterizes uncrossable functions... A larger open issue is to explore further the power of the primal-dual approach for obtaining approximation algorithms for other combinatorial optimization problems.” Our main result proves an O(1)-approximation guarantee via the primal-dual method for a class of functions that generalizes the notion of an uncrossable function. We mention that the support of every optimal dual solution could be non-laminar for instances that can be handled by our methods. We present two applications of our main result: 1. An O(1)-approximation algorithm for augmenting the family of near-minimum cuts of a graph. 2. An O(1)-approximation algorithm for the model of (p, 2)-Flexible Graph Connectivity. This is joint work with Joseph Cheriyan, Logan Grout and Sharat Ibrahimpur and has appeared at ICALP'23.

In the feedback vertex set (FVS) problem, the objective is to delete a minimum cost subset of vertices to make the graph acyclic. FVS is a fundamental NP-hard problem. Approximation algorithms for FVS have relied on the local ratio technique, which have subsequently led to primal-dual algorithms via LPs. While these algorithms achieve the best approximation factor possible, the lack of LP-based primal rounding algorithms for FVS with optimal approximation guarantees has been a barrier for resolving the approximability of the more general Subset-FVS problem.

In this talk, I will present some recent progress towards this goal of designing primal rounding algorithms for FVS. In particular, I will focus on the closely related pseudoforest deletion set (PFDS) problem, where the objective is to delete a minimum cost subset of vertices so that every connected component has at most one cycle. PFDS is also NP-hard and shares the same approximability and algorithmic status as FVS. I will present primal rounding algorithms for PFDS that achieve nearly the best approximation factor possible. The rounding algorithms are based on the iterative rounding framework, and rely on extreme point properties of the associated polyhedra. I will prove one of these extreme point properties by showing that the constraints conditionally exhibit a supermodularity property. This leads to conditional uncrossing, a new technique which may be of independent interest.

Graph sparsification has been an important topic with many structural and algorithmic consequences. Recently hypergraph sparsification has come to the fore and has seen exciting progress. In this paper we take a fresh perspective and show that they can be both be derived as corollaries of a general theorem on sparsifying matroids and monotone submodular functions.

Quotients of matroids and monotone submodular functions generalize $k$-cuts in graphs and hypergraphs. We show that a weighted ground set of a monotone submodular function $f$ can be sparsified while approximately preserving the weight of every quotient of $f$ with high probability in randomized polynomial time.

This theorem conceptually unifies cut sparsifiers for undirected graphs [BK15] with other interesting applications. One basic application is to reduce the number of elements in a matroid while preserving the weight of every quotient of the matroid. For hypergraphs, the theorem gives an alternative approach to the hypergraph cut sparsifiers obtained recently in [CKN20], that also preserves all $k$-cuts. Another application is to reduce the number of points in a set system while preserving the weight of the union of every collection of sets. We also present algorithms that sparsify hypergraphs and set systems in nearly linear time, and sparsify matroids in nearly linear time and queries in the rank oracle model.

Consider the problem of maximizing a monotone increasing, submodular function defined on a set of weighted items under an unknown knapsack capacity. We require that the knapsack capacity is larger or equal than the heaviest item. Assume that the items are packed one by one into the knapsack and that the knapsack capacity can only be accessed through an oracle that answers whether a currently packed knapsack is feasible or not. If an item is attempted to be added to the present solution and fits into the knapsack, it is packed irrevocably. If the addition of an item more than exhausts the residual capacity of the knapsack, the item is removed from further consideration. We analyze the performance of universal policies, thus nonadaptive packing according to a predetermined sequence. It is well known that Wolsey’s greedy algorithm (1982) solves the same problem with known knapsack capacity with an approximation factor of 0.357, where the approximation factor is the worst case ratio between the solution obtained by the algorithm and the optimal solution. We present an algorithm to compute universal policies that perform, for any unknown but fixed knapsack capacity, at least as good as Wolsey’s algorithm.