\(\ell _1\)-sparsity Approximation Bounds for Packing Integer Programs

We consider approximation algorithms for packing integer programs (PIPs) of the form \(\max \{\langle c, x\rangle : Ax \le b, x \in \{0,1\}^n\}\) where c, A, and b are nonnegative. We let \(W = \min _{i,j} b_i / A_{i,j}\) denote the width of A which is at least 1. Previous work by Bansal et al. [1] obtained an \(\varOmega (\frac{1}{\varDelta _0^{1/\lfloor W \rfloor }})\)-approximation ratio where \(\varDelta _0\) is the maximum number of nonzeroes in any column of A (in other words the \(\ell _0\)-column sparsity of A). They raised the question of obtaining approximation ratios based on the \(\ell _1\)-column sparsity of A (denoted by \(\varDelta _1\)) which can be much smaller than \(\varDelta _0\). Motivated by recent work on covering integer programs (CIPs) [4, 7] we show that simple algorithms based on randomized rounding followed by alteration, similar to those of Bansal et al. [1] (but with a twist), yield approximation ratios for PIPs based on \(\varDelta _1\). First, following an integrality gap example from [1], we observe that the case of \(W=1\) is as hard as maximum independent set even when \(\varDelta _1 \le 2\). In sharp contrast to this negative result, as soon as width is strictly larger than one, we obtain positive results via the natural LP relaxation. For PIPs with width \(W = 1 + \epsilon \) where \(\epsilon \in (0,1]\), we obtain an \(\varOmega (\epsilon ^2/\varDelta _1)\)-approximation. In the large width regime, when \(W \ge 2\), we obtain an \(\varOmega ((\frac{1}{1 + \varDelta _1/W})^{1/(W-1)})\)-approximation. We also obtain a \((1-\epsilon )\)-approximation when \(W = \varOmega (\frac{\log (\varDelta _1/\epsilon )}{\epsilon ^2})\).

1. 1.

   We can allow the variables to have general integer upper bounds instead of restricting them to be boolean. As observed in [1], one can reduce this more general case to the \(\{0,1\}\) case without too much loss in the approximation.

Authors and Affiliations

1. University of Illinois at Urbana-Champaign, Urbana, IL, USA

   Chandra Chekuri, Kent Quanrud & Manuel R. Torres

Corresponding author

Correspondence to Manuel R. Torres .

Editors and Affiliations

1. École Polytechnique de Montréal, Montreal, QC, Canada

   Andrea Lodi

2. University of Michigan, Ann Arbor, MI, USA

   Viswanath Nagarajan

Appendix

A Chernoff Bounds and Useful Inequalities

The following standard Chernoff bound is used to obtain a more convenient Chernoff bound in Theorem 7. The proof of Theorem 7 follows directly from choosing \(\delta \) such that \((1 + \delta )\mu = W - \beta \) and applying Theorem 6.

Theorem 6

([12]). Let \(X_1,\ldots , X_n\) be independent random variables where \(X_i\) is defined on \(\{0, \beta _i\}\), where \(0 < \beta _i \le \beta \le 1\) for some \(\beta \). Let \(X = \sum _i X_i\) and denote \(\mathbb {E}[X]\) as \(\mu \). Then for any \(\delta > 0\),

Theorem 7

Let \(X_1,\ldots , X_n \in [0,\beta ]\) be independent random variables for some \(0 < \beta \le 1\). Suppose \(\mu = \mathbb {E}[\sum _i X_i] \le \alpha W\) for some \(0< \alpha < 1\) and \(W \ge 1\) where \((1 - \alpha )W > \beta \). Then

Lemma 7

Let \(x \in (0,1]\). Then \((1/e^{1/e})^{1/x} \le x\).

Lemma 8

Let \(y \ge 2\) and \(x \in (0, 1]\). Then \(x/y \ge (1/e^{2/e})^{y/2x}\).

B Skipped Proofs

1.1 B.1 Proof of Theorem 1

Proof

Let \(G = (V,E)\) be an undirected graph without self-loops and let \(n = \left| V\right| \). Let \(A \in [0,1]^{n \times n}\) be indexed by V. For all \(v \in V\), let \(A_{v,v} = 1\). For all \(uv \in E\), let \(A_{u,v} = A_{v,u} = 1/n\). For all the remaining entries in A that have not yet been defined, set these entries to 0. Consider the following PIP:

Let S be the set of all feasible integral solutions of (1) and \(\mathcal {I}\) be the set of independent sets of G. Define \(g : S \rightarrow \mathcal {I}\) where \(g(x) = \{v : x_v = 1\}\). To show g is surjective, consider a set \(I \in \mathcal {I}\). Let y be the characteristic vector of I. That is, \(y_v\) is 1 if \(v \in I\) and 0 otherwise. Consider the row in A corresponding to an arbitrary vertex u where \(y_u = 1\). For all \(v \in V\) such that v is a neighbor to u, \(y_v = 0\) as I is an independent set. Thus, as the nonzero entries in A of the row corresponding to u are, by construction, the neighbors of u, it follows that the constraint corresponding to u is satisfied in (1). As u is an arbitrary vertex, it follows that y is a feasible integral solution to (1) and as \(I = \{v : y_v = 1\}\), \(g(y) = I\).

Define \(h : S \rightarrow \mathbb {N}_0\) such that \(h(x) = \left| g(x)\right| \). It is clear that \(\max _{x \in S} h(x)\) is equal to the optimal value of (1). Let \(I_{max}\) be a maximum independent set of G. As g is surjective, there exists \(z \in S\) such that \(g(z) = I_{max}\). Thus, \(\max _{x\in S} h(x) \ge \left| I_{max}\right| \). As \(\max _{x \in S} h(x)\) is equal to the optimum value of (1), it follows that a \(\beta \)-approximation for PIPs implies a \(\beta \)-approximation for maximum independent set.

Furthermore, we note that for this PIP, \(\varDelta _1 \le 2\), thus concluding the proof.

1.2 B.2 Proof of Lemma 3

Proof

The proof proceeds similarly to the proof of Lemma 2. Since \(\alpha _1 < 1/2\), everything up to and including the application of the Chernoff bound there applies. This gives that for each \(i\in [m]\) and \(j \in [n]\),

By choice of \(\alpha _1\), we have

We prove the final inequality in two parts. First, note that \(\frac{W - A_{i,j}}{A_{i,j}} \ge W - 1\) since \(A_{i,j} \le 1\). Thus,

Second, we see that

for \(A_{i,j} \le 1\), where the first inequality holds because \(W \ge 2\) and the second inequality holds by Lemma 8.

Reprints and permissions

© 2019 Springer Nature Switzerland AG

Policies and ethics