On largest volume simplices and sub-determinants

Introduction

Many techniques in convex geometry begin with approximating a geometric shape by a simpler one. The maximum volume ellipsoid, or John ellipsoid (see, e.g., ), for example, is a prominent such simplification with many applications in discrete and continuous optimization.

Simplices are, next to ellipsoids, among the most primitive convex sets. We are interested here in the problem of approximating a given $V$-polytope by a contained simplex of largest volume. More precisely, we investigate the approximability and hardness of the following problem.

We assume here, without loss of generality, that the convex hull of the points $a_{1},\dots,a_{n}$ is full-dimensional. As is the case for ellipsoids, the largest volume simplex in a convex body has attracted a lot of attention in the computer science and optimization literature, see, e.g., .

where $A$ is the matrix with columns $v_{1}-v_{0},v_{2}-v_{0},\dots,v_{d}-v_{0}$. Thus MVS can be reduced to $n$ instances of the problem of finding the largest absolute value of a $d\times d$ subdeterminant of a $d\times(n-1)$ matrix. This motivates the second problem that is central to our study.

Here a basis of a $d\times n$ matrix $A$ is a maximal subset of the column indices $B\subseteq\{1,\dots,n\}$ such that the corresponding columns are linearly independent, and $A_{B}$ is the matrix consisting of the columns indexed by $B$. Khachiyan has shown that there exists a $((1+\varepsilon)\cdot d)^{(d-1)/2}$ approximation algorithm for MSD, and thus also for MVS, with running time polynomial in $n,d$ and $1/\varepsilon$.

We show that there exists an algorithm for MVS, with running time polynomial in $n,d$ and $1/\varepsilon$, that computes a simplex $\Sigma$ with

We show that there exists a constant $c>1$ such that MVS cannot be approximated within a factor of $c^{d}$, unless $P=NP$. This improves the previous best $1.09$-inapproximability of Packer .

Our hardness result (ii) holds for instances with $n=\Theta(d)$. A recent sampling technique immediately yields a $\bar{c}\,^{d}$-approximation for such instances (for another constant $\bar{c}$), showing that the hardness is essentially tight in this case.

These results (i), (ii) and (iii) also hold for MSD.

The literature on topics related to MVS and MSD is extensive. In order to put our results in perspective, we provide an overview of a selection of related papers.

Variants where the dimension of the solution can be restricted, e.g. finding a maximum volume $j$-dimensional simplex, have been considered for MVS and MSD .

Hardness of approximation

Packer has shown that MVS is inapproximable within a constant factor smaller than $1.09$. This implies the same hardness for MSD, which was shown earlier to be NP-hard by Papadimitriou .

In both cases, the authors show that there exist a constant $c>1$ and a function $j(d)$ such that it is NP-hard to approximate the respective problem with factor less than $c^{j(d)}$. Here, $j(d)$ is linear in $d$, but with constant dependence strictly less than one, thus these results do not cover the case $j=d$.

Subdeterminants in optimization and combinatorics

The subdeterminant lower bound for hereditary discrepancy is $\max_{k}\sqrt[k]{\Delta_{k}}$. Recently Matousek has shown that the subdeterminant bound is tight up to a polynomial factor in $\log d$ and $\log n$. In a recent series of papers by Nikolov et al. it was shown how to approximate the hereditary discrepancy, and thus the subdeterminant bound $\max_{k}\sqrt[k]{\Delta_{k}}$, within a polynomial factor in $\log d$ and $\log n$. Our result provides a $O(\log d)$-approximation to $\sqrt[d]{\Delta_{d}}$. It is an interesting problem whether a polynomial time approximation algorithm for the subdeterminant bound with a guarantee that is polynomial in $\log d$ exists.

A tight analysis of Khachiyan’s algorithm

We now come to the main algorithmic result of our paper and show the following theorem. Recall that $A_{B}$ is the matrix corresponding to the columns of $A$ indexed by $B$. We denote the set of bases of $A$ by $\mathscr{B}$.

The algorithm runs in time polynomial in $n,d$, and $1/\varepsilon$. Thus MSD and MVS can be approximated within the factor above.

The largest $d\times d$ subdeterminant of $A$, in absolute value, corresponds to the largest volume simplex in $\mathscr{A}$ with one vertex being the origin. The algorithm begins by rounding the polytope $\mathscr{A}$.

Khachiyan showed that, if $\mathcal{K}$ is a symmetric $V$-polytope that is explicitly given by its vertices, then it is possible to compute an ellipsoid $\mathscr{E}$ such that $\mathscr{E}\subseteq\mathcal{K}\subseteq\sqrt{(1+\varepsilon)d}\ \mathscr{E}$ in time polynomial in the number of vertices of $\mathcal{K}$, $d$ and $1/\varepsilon$. This applies to the polytope $\mathscr{A}$.

holds. From there, the algorithm proceeds in a greedy fashion, see Figure 1.

Note that $v_{1},\dots,v_{d}$ correspond to the Gram-Schmidt orthogonalization of the vectors returned by the greedy procedure. Thus, after rounding, the absolute value of the determinant induced by the chosen vectors is $\|v_{1}\|\dots\|v_{d}\|$.

We now review Khachiyan’s analysis showing that his algorithm is a factor $((1+\varepsilon)d)^{(d-1)/2}$ approximation algorithm for MSD. Let us denote the Euclidean lengths of the picked vectors $v_{i}$ by $\rho_{i}=\lVert v_{i}\rVert$ for $i=1,\dots,d$, and define $\Delta_{\max}=\max_{B\in\mathscr{B}}|\det(A_{B})|$. The claimed bound follows from the following two facts:

There is a polynomial-time $((1+\varepsilon)d)^{(d-1)/2}$-approximation algorithm for problems MSD and MVS.

2 Improving the analysis

We will now show that the approximation factor can in fact be bounded by $(e\ln((1+\varepsilon)d))^{d/2}$. To do so, we significantly tighten the upper bound (i) presented in the analysis above. Key to this improvement is the following observation.

Each $v_{i}$ is on a principal axis of $\mathscr{E}$.

None of the vectors $v_{i}$ is contained in the interior of $\mathscr{E}$.

There exists $\alpha>0$ such that each $a_{i}$ is contained in $\alpha\cdot\mathscr{E}$.

The theorem follows from the existence of an ellipsoid $\mathscr{E}$ satisfying the conditions of Lemma 3 with $\alpha=\sqrt{e\ln((1+\varepsilon)d)}$.

The vectors $v_{1},\dots,v_{d}$ are pairwise orthogonal due to the projection in Step 2. Recall that determinants are invariant under rotation and note that the algorithm’s execution is also invariant under rotation. Therefore, by suitably rotating the input, we can assume without loss of generality that $v_{1},\dots,v_{d}$ are the vectors $\rho_{1}\cdot e_{1},\dots,\rho_{d}\cdot e_{d}$, where $e_{i}$ is the $i$-th unit vector.

Next, let us group the elements of the decreasing sequence $\rho_{1},\dots,\rho_{n}$ as follows. Let $G_{j}$ be the set of indices $i$ such that $\frac{\rho_{1}}{\exp((j-1)/2)}\geq\rho_{i}>\frac{\rho_{1}}{\exp(j/2)}$. Let $t$ denote the number of such groups. Since $\rho_{1}/\rho_{d}\leq\sqrt{(1+\varepsilon)d}$, we have $t\leq\log_{\exp(1/2)}\sqrt{(1+\varepsilon)d}=\ln((1+\varepsilon)d)$. Assume that all groups $G_{j}$ are non-empty (discarding empty groups will decrease the number of groups and subsequently yield an improved analysis). Let $r_{j}$ be the largest element of $G_{j}$ and note that $r_{j}/\rho_{i}\leq\sqrt{e}$ for all $\rho_{i}\in G_{j}$.

We are done once we have shown that the ellipsoid $\mathscr{E}$, together with $\alpha=\sqrt{e\ln((1+\varepsilon)d)}$, satisfies the conditions (a)–(c) from Lemma 3.

3 Tightness of the analysis

We now provide a family of instances of increasing dimension where Khachiyan’s algorithm achieves a ratio of $(\alpha\ln(d))^{d/2}$, where $\alpha\geq 0.748$ tends to $1$ as $d$ grows. Thus, we basically match the upper bound on the approximation ratio given in the previous section.

Let $d\geqslant 4$ be a power of two. The instances are matrices with $d$ rows of the form

Here, $D$ is a $d\times d$ diagonal matrix of the form

Thus the polytope that is generated by the columns of the matrix (1) and their negatives is “round”, in the sense that it contains the unit ball and it is contained in the unit ball scaled by $\sqrt{d}$. We will show below that Khachiyan’s algorithm will output a solution of value at most $c\cdot|\det D|$. This implies the claim, as

Then using $x-1\geq\ln(x)$, we deduce that the approximation ratio is

Let $w$ be any column vector of $\frac{\sqrt{c^{2}-1}}{c}DH$. The squared norm of the projection of $w$ into the orthogonal complement of the first $i$ column vectors of $D$ (where $i\in\{0,\dots,d-1\}$) is

The last term is the squared norm of the $(i+1)$-th column vector of $D$. Thus Khachiyan’s algorithm outputs the first $d-1$ columns of $D$, and in the last step a column of norm at most $c$ from $E$. The determinant of the column vector selected by Khachiyan’s algorithm is then at most $c\times|\det D|$, as claimed above.

Hardness

We now consider the hardness of approximating MVS and MSD. As mentioned in Section 1.1, the best inapproximability result was due to Packer , who proved that MVS cannot be approximated with a factor better than $1.09$, unless $P=NP$. In this section we provide a drastic improvement showing that it is NP-hard to approximate MVS and MSD with a factor $c^{d}$, where $c>1$ is an explicit constant. In particular, we show that the result holds for instances where $n=\Theta(d)$. We will also conclude that the hardness result is best possible for such instances.

Our argument is based on the connection between MSD and the following problem.

Given a simple undirected graph, find a maximum family of vertex-disjoint odd cycles.

The overall strategy for proving hardness is the following. We first build on a hardness result by Berman and Karpinski on stable sets in $3$-regular graphs and show that OCP is NP-Hard to approximate with a factor ${\bar{c}}$, where $\bar{c}>1$ is an explicit constant. Our second step is to reduce OCP to MSD, using the construction seen above. Hence the constant inapproximability for OCP leads to a $c^{d}$-inapproximability for MSD. Last, we reduce MSD to MVS.

Let us remark that OCP is NP-hard even when restricted to planar graphs and, in that case, allows for constant factor approximations . Following the hardness for packing the maximum number of disjoint cycles by Friggstad and Salavatipour , we can deduce for OCP a constant hardness under P$\neq$NP and a hardness of $O\left(\log^{\frac{1}{2}-\varepsilon}n\right)$ unless $\text{NP}\subseteq\text{ZPTIME}\left(n^{\text{polylog}(n)}\right)$, where $n$ is the number of nodes of the graph. This result relies on the PCP-theorem. Our construction below yields a weaker hardness for OCP, but it does not rely on the PCP-theorem, it leads to an improved hardness result for the vertex-disjoint triangle packing problem, and it is much simpler to use for constructing a hardness for MSD subsequently. In particular, it enables us to easily calculate the explicit constants in the hardness for MSD.

On the positive side, Kawarabayashi and Reed showed that for general graphs OCP can be approximated within a factor of $\sqrt{n}$.

We now describe our inapproximability result for OCP. We require a result of Berman and Karpinski for maximum stable set on 3-regular graphs. Given a system of $2n$ linear equations modulo 2 with 3 variables per equation, Håstad showed that it is NP-hard to distinguish between instances where there exists a solution satisfying $(1-\varepsilon)2n$ equations and instances where no solution satisfies more than $(1+\varepsilon)n$ equations, for any arbitrarily small $\varepsilon>0$. Building on this result, Berman and Karpinski gave a polynomial time construction of a 3-regular graph on $176n$ vertices that translates $n$ satisfied equations to a maximum stable set of size at most $97n$ and $2n$ satisfied equations to a maximum stable set of size at least $98n$. Thus, it is NP-Hard to detect if a $3$-regular graph on $176n$ vertices has a stable set of size at least $(1-\varepsilon)98n$, or at most $(1+\varepsilon)97n$, for each $\varepsilon>0$.

Let $G=(V,E)$ be the graph constructed in . Intuitively, we would like to construct a new graph $H$ such that every vertex in $G$ corresponds to a triangle in $H$ and that a stable set in $G$ also corresponds to a packing of triangles in $H$. A first candidate for such a graph $H$ would be the line graph of $G$ (recall that $G$ is $3$-regular), but in the line graph we might also create triangles that do not correspond to vertices in $G$.

We solve this issue by slightly changing $G$. Subdivide every edge in $G$ twice, i.e., substitute an edge $\{u,v\}$ by a path $P_{uv}=u,p_{1},p_{2},v$. Let $G^{\prime}$ be the obtained graph. Since $G$ has $176n$ vertices, hence $\frac{3}{2}176n=264n$ edges, $G^{\prime}$ has $176n+2\cdot 264n=704n$ vertices and $3\cdot 264n=792n$ edges. Note that $G^{\prime}$ is triangle-free.

We now prove that every subdivision of an edge in $G$ augments the stable sets by exactly one vertex. Consider a stable set $S$ in $G$. By choosing $p_{2}$ when $u\in S$ or $p_{1}$ otherwise we obtain an induced stable set in $G^{\prime}$ of size $|S|+264n$. Conversely, let $S^{\prime}$ be a stable set in $G^{\prime}$. Modify $S^{\prime}$ such that for each $P_{uv}$ not both $u$ and $v$ are in $S^{\prime}$: if both are in $S^{\prime}$, then the stable set $S^{\prime}\setminus\{v\}\cup\{p_{2}\}$ has the same cardinality and only includes one of $\{u,v\}$. Then we can obtain a stable set in $G$ of size at most $|S^{\prime}|-264n$. In particular, a stable set of size $97n$ (resp., $98n$) in $G$ translates into a stable set of size $97n+264n=361n$ (resp., $362n$) in $G^{\prime}$.

Now let $H$ be constructed as follows: starting from the line graph of $G^{\prime}$, for each $P_{uv}$ add two vertices and connect them as to obtain the graph $H_{uv}$ depicted in Figure 2. The number of vertices in $H$ is $792n+2\cdot 264n=1320n$ and the number of edges is $\frac{1}{2}(4\cdot 792n+2\cdot 2\cdot 264n)=2112n$, as every vertex belonging to the line graph of $G^{\prime}$ has degree four and the two additional vertices in each $H_{uv}$ have degree two.

As $G^{\prime}$ is triangle-free, there is a one-to-one correspondence between triangles in $H$ and vertices in $G^{\prime}$. Moreover, two vertices in $G^{\prime}$ are adjacent if and only if their corresponding triangles in $H$ have a common vertex. Thus a maximum stable set of size $361n$ (resp., $362n$) in $G^{\prime}$ translates into a maximum number of $361n$ (resp., $362n$) vertex-disjoint triangles in $H$. It is known that finding the maximum number of vertex-disjoint triangles in a graph is APX-hard . However, no explicit lower bound was known.

It is NP-hard to approximate the maximum number of vertex-disjoint triangles in a graph with a factor of $\left(\frac{362}{361}-\varepsilon\right)$ for arbitrarily small constant $\varepsilon>0$. The result holds even for graphs with maximum degree four.

Now, consider OCP in $H$, i.e., finding the maximum number of vertex-disjoint odd cycles. We prove that there is always an optimal solution consisting of triangles only. Assume the contrary, i.e., the optimal solution includes a cycle $C$ of length at least $5$. We distinguish three cases. First, $C$ does not contain any vertex other than those of type $x$ and $y$ (see Figure 2). Then, $C$ must be a triangle. Second, $C$ is fully contained in some $H_{uv}$. One easily checks that also in this case $C$ must be a triangle. Third, $C$ is not contained in any $H_{uv}$. Then $C$ has to pass through the node $z$ of some $H_{uv}$ and hence the solution does not include any triangle in such $H_{uv}$. Substitute $C$ by any of the two triangles in $H_{uv}$ to obtain another optimal solution to OCP. Hence there is an optimal solution to OCP in $H$ only containing triangles. Therefore we have the following hardness result.

It is NP-hard to approximate OCP with a factor of $\left(\frac{362}{361}-\varepsilon\right)$ for arbitrarily small constant $\varepsilon>0$. The result holds even for graphs with maximum degree four.

2 From OCP to MSD and MVS

Consider the node-edge incidence matrix $A$ of $H$: this is a $1320n\times 2112n$ matrix. From what was argued above, the maximum number of vertex-disjoint odd cycles of $361n$ (resp., $362n$) translates into subdeterminants of size $2^{361n}$ (resp., $2^{362n}$). This allows us to prove a hardness of $2^{n}$ when the dimension is $d=1320n$.

It is NP-hard to approximate MSD with a factor of $\left(2^{1/1320}-\varepsilon\right)^{d}$ for arbitrarily small constant $\varepsilon>0$. The hardness even holds when restricted to node-edge incidence matrices of graphs with maximum degree four.

where $\varepsilon^{\prime}=723\varepsilon$ and $\varepsilon^{\prime\prime}=2^{1/1320}\left(1-2^{-\frac{\varepsilon^{\prime}}{1320}}\right)>0$. ∎

We now derive a similar inapproximability result for MVS.

It is NP-hard to approximate MVS with a factor of $\left(2^{1/1320}-\varepsilon\right)^{d}$ for arbitrarily small constant $\varepsilon>0$.

where $S^{\prime}$ is the simplex among $S_{1},\dots,S_{d+1}$ of maximum volume. Note moreover that the submatrix $A^{\prime}$ associated to the non-zero vertices of $S^{\prime}$ is a feasible solution to the original MSD problem. We deduce

Hence, we can output $A^{\prime}$ and obtain the required approximation. ∎

For every $\varepsilon>0$, it is NP-Hard to approximate

the maximum number of vertex-disjoint triangles in a graph and OCP within a factor of $\left(\frac{285}{284}-\varepsilon\right)$;

MSD and MVS with a factor of $\left(2^{1/1012}-\varepsilon\right)^{d}$.

3 Tightness for instances with n=O​(d)𝑛𝑂𝑑n=O(d)

The claimed result then follows by repeated sampling and picking the largest basis.

If $n=O(d)$, then there exists a randomized algorithm for MSD with approximation ratio $\bar{c}^{d}$ for some constant $\bar{c}$ that depends on the constant in the $O$-notation.

References