4
$\begingroup$

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. [1]. 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 [2] (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

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

[2] 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.