# Computing Minima of the Projection of a Binary Cube

The problem is as follows: I want to compute the minima (with respect to the canonical partial order on vectors "$\leq$") of the linear projection of the extreme points of an $n$-dimensional $\{0,1\}$-cube into the plane. Thus, I am given a $2\times n$-matrix $C$ with integer entries which encodes my projection. Let's call it the cube projection problem.

Note that the result of the projection is a set of isolated points and that these points do not lie in convex position in general.

Is it possible to compute these points in an output-sensitive way? Is this a (well-)known problem? What are problems which might be related to this one?

EDIT NOTE: W.l.o.g. we can assume that each column of $C$ consists of a negative and a positive value. Assume that both values of column $i$ are non-negative (non-positive), then $Cx \leq Cx'$ for every $x\in\{0,1\}^n$ with $x_i = 0$ ($=1$) and $x'_j := x_j$ for $j\neq i$ and $x'_i = 1$ ($=0$).

The problem is related to the knapsack problem in the following sense: For a knapsack instance \begin{equation} \max\ c_1^Tx\\ \text{s.t.}\ c_2^Tx \leq W\\ x\in \{0,1\}^n, \end{equation}

an optimal knapsack value is the negation of the first component of one of the vectors in

$$\mathcal{Y}:=\min\{\begin{pmatrix}-c_1^T\\c_2^T\end{pmatrix}x \mid x \in \{0,1\}^n\} \subseteq \mathbb{Z}^2.$$

This is well-known and used by the Nemhauser-Ullmann algorithm, cf. . Though, output-sensitivity of the Nemhauser-Ullmann algorithm for the cube projection problem is open, as far as I known.

An interesting question which arises in this knapsack context is: Is there an $\mathbf{NP}$-hard set of knapsack instances with $\mathcal{Y}$ of polynomial size? If there is then the cube projection problem cannot be output-sensitively solved unless $\mathbf{P}=\mathbf{NP}$.

The relation to the Nemhauser-Ullmann algorithm also shows that the problem can be solved in pseudo-polynomial time.

EDIT NOTE2: To prove that the cube projection problem cannot be solved in ouput-polynomial time, we can prove that the following decision problem is hard:

Given $C$ and a subset $M\subseteq \min \{ Cx \mid x\in\{0,1\}^n\}$. Decide if $M=\min \{ Cx \mid x\in\{0,1\}^n\}$.

Lawler, Lenstra and Rinnooy Kan proved in  (for the case of finding maximal independent sets) that if the cube projection problem can be solved in output-polynomial time then the above decision problem can be solved in polynomial time. This technique is often used to prove the hardness of an enumeration problem.

### References

 Kellerer, H., Pferschy, U., and Pisinger, D. Knapsack Problems. Springer Berlin Heidelberg New York, 2004.

 Lawler, E. L., Lenstra, J. K., and Rinnooy Kan, A. H. G. Generating all maximal independent sets: $\mathbf{NP}$-hardness and polynomial-time algorithms. SIAM Journal on Computing 9, 3 (1980), 558–565.