  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\dots\ 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 that the primal-dual algorithm of Williamson et al.
achieves an approximation ratio of 16 for a class of functions that generalizes
the notion of an uncrossable function. There exist instances that can be
handled by our methods where none of the optimal dual solutions has a laminar
support.
  We present three applications of our main result.
  (1) A 16-approximation algorithm for augmenting a family of small cuts of a
graph $G$.
  (2) A $16 \cdot {\lceil k/u_{min} \rceil}$-approximation algorithm for the
Cap-$k$-ECSS problem which is as follows: Given an undirected graph $G = (V,E)$
with edge costs $c \in \mathbb{Q}_{\geq 0}^E$ and edge capacities $u \in
\mathbb{Z}_{\geq 0}^E$, find a minimum-cost subset of the edges $F\subseteq E$
such that the capacity of any cut in $(V,F)$ is at least $k$; we use $u_{min}$
to denote the minimum capacity of an edge in $E$.
  (3) An $O(1)$-approximation algorithm for the model of $(p,2)$-Flexible Graph
Connectivity.
