A Knapsack Intersection Hierarchy Applied to All-or-Nothing Flow in Trees

The all-or-nothing flow problem [10] is defined for a multiflow problem whose input is a supply graph $G$ and demand graph $H$. $G$ and $H$ may also be endowed with edge capacities $u_{e}:e\in E(G)$ and demands $d(f):f\in E(H)$. We call $E(H)$ the requests and a subset $R$ of requests is routable if there is a (fractional) multiflow which routes the requests in $R$ using $G$’s capacity. The problem is “all-or-nothing” in the sense that if $f\in R$, then we must route the whole $d(f)$ units of demand. An instance is said to satisfy the no-bottleneck-assumption (NBA) if $d(f)\leq u_{e}$ for every request $f$ and supply edge $e$. ANF-Tree is the special case of all-or-nothing flow where the supply graph $G$ is a tree.

When the NBA holds, there is a polylog approximation in general graphs [9] and a $48$-approximation in trees [10]. Without the NBA, however, the natural LP has a super-constant integrality gap. The first theoretical progress for the non-NBA setting was a quasi-PTAS when the supply graph is a path [2]. A sequence of papers has ultimately yielded a constant-factor approximation (and integrality gap) for paths, the best of which is an $O(1+\frac{1}{1+e}+\epsilon)$-approximation [15], and an LP with integrality gap $7+\epsilon$ [3]. For trees, however, the strongest result is an $O(\log^{2}n)$-approximation [5, 14, 1]. It remains an open question whether ANF-Tree has an $O(1)$-approximation (or even an $O(\log n)$-approximation), and whether ANF-Path has a PTAS.

For trees we use the following notation. An instance ${\mathcal{I}}=(T,R)$ of ANF-Tree consists of an undirected capacitated tree $T=(V,E,u)$ and a set of requests $R$, defined as follows. $V$ is the set of vertices and each edge $e\in E$ has some positive capacity $u_{e}$. Each request $r\in R$ imposes some non-negative demand $d_{r}$ on all edges along the unique simple path $P_{r}$ between $s_{r}\in V$ and $t_{r}\in V$. A request may also have a profit $w_{r}$. We assume that $s_{r}\neq t_{r}$ for all $r\in R$. For each edge $e$, let $R_{e}=\{r\in R:e\in P_{r}\}$. We denote $k=|R|$ and $m=|E|$. A subset $S\subseteq R$ of requests is feasible or routable if, for each edge $e\in E$, the total demand of all requests $r\in S\cap R_{e}$ is at most the capacity $u_{e}$. The goal is to select a feasible subset $S\subseteq R$ which maximizes the profit $\sum_{r\in S}w_{r}$. We formalize this with the following IP.

The natural LP relaxation ANF-LP is defined by replacing $x\in\{0,1\}^{k}$ with $x\in[0,1]^{k}$; ANF-Path is defined similarly.

One approach for strengthening ANF-LP is to add rank constraints [5, 14]. For $S\subseteq R$ its rank is defined as $\operatorname{rank}(S):=\max\{|T|:T\subseteq S\text{ and }T\text{ is feasible}\}$, and the rank constraint is then $\sum_{i\in S}x_{i}\leq\operatorname{rank}(S)$. Adding all such inequalities to ANF-LP defines the Rank-LP. We denote by $P_{\operatorname{rank}}$ the polytope obtained from adding all rank constraints to an ANF-Tree relaxation $P$. Rank-LP is NP-Hard to separate, but it can be $O(1)$-approximated [5, 14].

We summarize the known results for these general ANF-Tree formulations.

In the rest of the paper, $P$ refers to the feasible region of ANF-LP and hence $P_{\operatorname{rank}}$ refers to same for Rank-LP. The first result shows the general dependence of the integrality gap for $P^{t}$ on $k$ and $t$; this is similar to the Sherali-Adams hierarchy [5] (although the proofs are not similar). The upper bound part is proved in Lemma 1, and the lower bound is proved in Lemma 5 - see Section 3

We now focus on the Friggstad-Gao instances (definition in Section 3). These instances established the $\Omega(\sqrt{\log k})$ ANF-Tree lower bound in Theorem 1.2; this is significant since it established a super-constant lower bound even when all rank constraints are added. Furthermore, these are single-sink instances, i.e., all requests share one common endpoint. We establish the following lower bounds for the knapsack hierarchy on the Friggstad-Gao instances.

Interestingly, the proof of this lower bound depends on an upper bound proof. Namely, we define a colouring problem for which we upper bound the chromatic number (see Section 4.2). We can also show that our analysis of $P^{t}_{\operatorname{rank}}$ on the Friggstad-Gao instances is tight in the following sense.

It remains an intriguing question whether this constant integrality gap of $O(1/c)$ holds for general tree instances, even in the single-sink scenario.

The use of hierarchies for integer programs dates back to the notion of Chvátal rank [6]. The Chvátal closure of a polyhedron $P$ is the polyhedron $P^{\prime}\subseteq P$ which is defined by the system of Chvátal-Gomory cutting planes obtainable from $P$. If we denote $P_{C}^{1}=P^{\prime}$ then the hierarchy is generated by $P_{C}^{t+1}=(P_{C}^{t})^{\prime}$. Chvátal proved that $P\supseteq P_{C}^{1}\supseteq\ldots\supseteq P_{C}^{n-1}\supseteq P_{C}^{n}=P_{I}.$ As discussed, it is NP-hard to separate over $P^{1}$ both in the Chvátal hierachy and the knapsack hierarchy considered in this paper. Other hierarchies have since been introduced and widely studied, such as the hierarchy defined by the split closure [8] and hierarchies introduced by Lovász-Schrijver [20], Sherali-Adams [24], Parillo [22], and Lasserre [19]. These other hierachies also have that the integer hull is obtained after $n$ rounds of the hierarchy, where $n$ is the number of variables. In that sense, the knapsack hierarchy is different since $P^{m}=P_{I}$ where $m$ is the number of constraints. For ANF-tree formulations, however the number of variables equals $k$, the number of requests. Moreover, for ANF-Tree instances one may show that $m\leq 4k$ (see Appendix A.3 in [14]). Hence the knapsack hierarchy is equal to the integer hull at level $O(k)$ for ANF-Tree.

We summarize the existing work on the effectiveness of classical hierarchies on ANF-Tree. Friggstad and Gao showed that the Lovász-Schrijver hierarchy is ineffective at reducing the integrality gap of ANF-Tree after 2 rounds and amounts to adding the rank one constraints [14]. Additionally, Chekuri, Ene, and Korula prove that after applying $t$ rounds of the Sherali-Adams hierarchy to ANF-LP, the integrality gap is $\Omega(k/t)$ [5], matching the result for our hierarchy. For the case of 0-1 knapsack, Karlin, Mathieu, and Nguyen show that $t^{2}$ rounds of Lasserre reduce the integrality gap to $t/(t-1)$ [17]. We are not aware of any work done on whether this would generalize to ANF-Tree.

In the remainder of the paper we introduce the well-known “bad gap instances” for ANF: in particular, the so-called staircase and Friggstad-Gao instances (in Section 3). We then prove our results (in Sections 2, 4 and 5), and discuss future work (in Section 6).

For $k\geq 1$, we define the staircase²²2In the literature, this instance is referred to as a staircase because of a common way of visualizing ANF-Path instances where the capacity is plotted above the vertices on the Y axis. ANF-Path instance $S^{k}=(T,R)$ as follows. Let $T$ be a path graph on $k+1$ vertices, that is, $V=\{1,\dots,k+1\}$ and $E=\{(1,2),(2,3),\dots,(k,k+1)\}$. We refer to vertex $1$ as the root or $r$. For each $i=1,\dots,k$, define $u_{(i,i+1)}=2^{i-1}$ and create a request $i$ with $s_{i}=i$, $t_{i}=r$, $d_{i}=2^{i-1}$, and $w_{i}=1$. See Fig. 1 for an illustration. These instances were first described by Chakrabarti, Chekuri, Gupta, and Kumar [4].

In this section, we describe the family of Friggstad-Gao ANF-Tree instances, which were introduced in [14].

We define the tree $T_{FG}^{h}$ with height $h\geq 2$ as follows. There is a root vertex $r$ which has a single child $v_{1}$. Apart from $r$ and the leaves (which are in level $h$), all vertices have $2^{h-1}$ children. We denote the set of vertices with distance $\ell$ from $r$ by $level_{\ell}$, that is, $level_{0}=\{r\}$, $level_{1}=\{v_{1}\}$, and for $\ell\in[h]$, $|level_{\ell}|=2^{(h-1)(\ell-1)}$. For each edge $e=uv$ with $u\in level_{\ell-1}$ and $v\in level_{\ell}$, define $u_{e}=2^{h(h-\ell+1)}$. For all $\ell\geq 1$ and each vertex $v\in level_{\ell}$, create a request associated with $v$ with $s_{v}=v$, $t_{v}=r$, demand $d_{v}=2^{h(h-\ell+1)}-2^{h(h-\ell)}$, and profit $w_{v}=2^{-(h-1)(\ell-1)}$. See Fig. 2 for an example. This defines a single-sink instance since every request terminates at $r$. Moreover, since the profit of each request in any level is the inverse of the number of requests in that level, the total profit of requests in any level is exactly $1$. A simple calculation shows that the number of requests (and equivalently the number of edges) in levels $0$ through $\ell$ is

Thus, $h=\Theta(\sqrt{\log k})$ where $k=n(h)$ is the total number of requests/edges, and for any $\ell$ we have $\ell=\Theta\left(\frac{\log n(\ell)}{h}\right)$.

The following lemmas establish some fundamental properties of these instances. We use $T^{<v}$ to denote the requests in the subtree of $T$ rooted at $v$ with $v$ itself removed.

For path instances, it is known that the integrality gap of $P_{\operatorname{rank}}$ is $O(\log k)$ and it is conjectured to be $O(1)$ [5]. However, the ANF-LP has an integrality gap of $\Omega(k)$, which is evidenced by the staircase instances $S^{k}$ [4]. We now prove the upper bound from Theorem 1.3 by showing that the integrality gap of $P^{t}$ is $\Omega(k/t)$.

In this section, we prove Theorem 1.4, which gives a lower bound on the integrality gap of $P^{t}$ on instances $T:=T_{FG}^{h}$. Recall that Lemma 4 establishes $1/2\in P^{1}$ by proving that for each edge $e$, the $1/2$ vector can be written as a convex combination of (incidence vectors of) two sets, each of which is routable on $e$. We generalize this to any value of $t$ by showing that for $1/c\in P^{t}$ for sufficiently small $c$, and thus the integrality gap is $\Omega(\sqrt{\log k}/c)$.

Let $S\subseteq E(T)$. We call a set $X\subseteq R(T)$ $S$-routable if $\forall e\in S$, $\sum_{i\in X\cap R(e)}d_{i}\leq u_{e}$. Our key structural result gives a condition when we can express a vector $1/c$ as a convex combination of $S$-routable sets.

We cast this convex combination question as a question of colouring the set of all requests. For $S\subseteq E(T)$, we define the $S$-chromatic number, denoted by $\chi(S)$, to be the minimum value $c$ such that $R(T)$ can be partitioned into $c$ sets, each of which is $S$-routable. Given such a partition, the vector $1/c$ is trivially a convex combination of the indicator vectors of the $S$-routable sets in the partition. Thus, if we can show that $\chi(S)\leq c$ for every $|S|=t$, we have guaranteed that $1/c\in P^{t}$. Hence, the integrality gap established by Friggstad and Gao decreases by at most a factor of $c/2$ for $P^{t}$, since the result of Friggstad and Gao is associated with the feasible vector $1/2\in P^{0}$. In fact, the following holds even if we start with the stronger formulation $P_{\operatorname{rank}}$; we explain why at the end of this section.

Our proof of Proposition 1 is based on the following colouring result. The tree $T^{\prime}$ plays the role of a subtree essentially induced by the edges from some set $S$ with $|S|=t$.