MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## 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 2010 at 15:53
It think the first problem is a special case of the second problem. Am I right? – Mohammad Al-Turkistany Nov 14 2010 at 16:18
Actually $x=y=-1$ and $z=\max(C, (K+1)/2)$ solve the second problem. – Pietro Majer Nov 14 2010 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 2010 at 19:31
@Qiaochu, Is exhaustive search avoidable in either case? Are you aware of any subexponential-time algorithms? – Mohammad Al-Turkistany Nov 14 2010 at 20:37
show 1 more comment

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.

[15, 15, 15, 3375, 675], [13, 13, 20, 3380, 689], [12, 15, 19, 3420, 693], [13, 14, 19, 3458, 695], [12, 17, 17, 3468, 697], [13, 15, 18, 3510, 699], [14, 14, 18, 3528, 700], [13, 16, 17, 3536, 701], [14, 15, 17, 3570, 703], [14, 16, 16, 3584, 704], [15, 15, 16, 3600, 705], [13, 14, 20, 3640, 722], [12, 16, 19, 3648, 724], [12, 17, 18, 3672, 726], [13, 15, 19, 3705, 727], [14, 14, 19, 3724, 728], [13, 16, 18, 3744, 730], [13, 17, 17, 3757, 731], [14, 15, 18, 3780, 732], [14, 16, 17, 3808, 734], [15, 15, 17, 3825, 735], [15, 16, 16, 3840, 736], [13, 15, 20, 3900, 755], [14, 14, 20, 3920, 756], [13, 16, 19, 3952, 759], [14, 15, 19, 3990, 761], [14, 16, 18, 4032, 764], [15, 15, 18, 4050, 765], [15, 16, 17, 4080, 767], [16, 16, 16, 4096, 768]

-
 Thanks Aaron, Does your answer suggest that exhaustive search ($2^{\Omega (n)}$−time) is unavoidable? – Mohammad Al-Turkistany Nov 16 2010 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