# Hardness of discrete geometric area minimization problem?

This question was originally posted on: cstheory.stackexchange

Given $xyz=C$ where $x, y,$ and $z$ are integer variables and $C$ is integer constant. Assume all integers are encoded in binary.

What is the complexity of finding $x, y, z$ such that $xy+xz+yz$ has minimum value? Is there any subexponential algorithm that solves this problem? Does the problem become easier when integers are encoded in unary?

Motivation: I'm interested in the following generalized problem:

Input: integers $C$ and $K$

Problem: Find integers $x$, $y$, and $z$ such that $xyz\ge C$ and $xy+xz+yz\le K$

-
It's not clear to me that you have to solve the first problem in order to solve the second problem. – Qiaochu Yuan Nov 14 '10 at 15:53
It think the first problem is a special case of the second problem. Am I right? – Mohammad Al-Turkistany Nov 14 '10 at 16:18
Actually $x=y=-1$ and $z=\max(C, (K+1)/2)$ solve the second problem. – Pietro Majer Nov 14 '10 at 19:23
@Mohammad: No. The first problem comes from a naive algorithm to solve the second, which is to test all possible values of xyz. But one could imagine a cleverer algorithm which only tests "good" candidates for xyz, e.g. ones with lots of prime factors. @Pietro: I am pretty sure x, y, z are supposed to be positive, since the word "geometric" is in the title. – Qiaochu Yuan Nov 14 '10 at 19:31
@Qiaochu, Is exhaustive search avoidable in either case? Are you aware of any subexponential-time algorithms? – Mohammad Al-Turkistany Nov 14 '10 at 20:37

For positive real values of $x,y,z,C,K$ the problem has an easy solution $x=y=z=\sqrt[3]{C}$ with $K=3C^{2/3}$ (If $K$ is any smaller there is no solution). In the integer case, if C is a perfect cube then the same can be obtained. And in any case, restricting to $x,y,z$ equal integers still gives a solution provided that $K \ge 3C^{2/3}+6C^{1/3}+3$. Actually you can do slightly better that by allowing $x \le y \le z \le x+1$.
That does leave some pairs $K,C$ still unexplained.It might be worth studying which integer triples $x_0,y_0,z_0$ are such that no other $x_1,y_1,z_1$ has $x_1y_1z_1\ge x_0y_0z_0$ and $x_1y_1+x_1z_1+y_1z_1 \le x_0y_0+x_0z_0+y_0z_0$
later I can't say too much, but I'd start with the real triple $[C^{1/3},C^{1/3},C^{1/3}]$ then round up and down to integers and try small variations. I don't think you'd go too far from there. Here are all the best triples from [15,15,15] to [16,16,16] so if you want C between 3375 and 4096 you'd pick one of these.
Thanks Aaron, Does your answer suggest that exhaustive search ($2^{\Omega (n)}$−time) is unavoidable? – Mohammad Al-Turkistany Nov 16 '10 at 12:23
No, it suggests that one rather simple search strategy (only vaugely specified) might be pretty efficient, but not how efficient. One thing is: given C and K , compute $a=\sqrt[3]{C}$ rounded up and $b=\sqrt{K/3}$ rounded down. if a≤b then use a,a,a or b,b,b or anything in between. If $a\gt b+1$, impossible (I think) If a=b+1 you have some work to do but maybe there are a limited number of possibilites. Perhaps x<y<z with y within 1 (or 2?) of either x,z or (x+z)/2 (at least for large C,K). Consider the similar problem of finding x,y with $xy\ge D$ but $x+y \le L$ . – Aaron Meyerowitz Nov 17 '10 at 17:48