1
$\begingroup$

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$

$\endgroup$
6
  • 1
    $\begingroup$ It's not clear to me that you have to solve the first problem in order to solve the second problem. $\endgroup$ Nov 14, 2010 at 15:53
  • $\begingroup$ It think the first problem is a special case of the second problem. Am I right? $\endgroup$ Nov 14, 2010 at 16:18
  • $\begingroup$ Actually $x=y=-1$ and $z=\max(C, (K+1)/2)$ solve the second problem. $\endgroup$ Nov 14, 2010 at 19:23
  • $\begingroup$ @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. $\endgroup$ Nov 14, 2010 at 19:31
  • $\begingroup$ @Qiaochu, Is exhaustive search avoidable in either case? Are you aware of any subexponential-time algorithms? $\endgroup$ Nov 14, 2010 at 20:37

1 Answer 1

2
$\begingroup$

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]

$\endgroup$
2
  • $\begingroup$ Thanks Aaron, Does your answer suggest that exhaustive search ($2^{\Omega (n)}$−time) is unavoidable? $\endgroup$ Nov 16, 2010 at 12:23
  • $\begingroup$ 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$ . $\endgroup$ Nov 17, 2010 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.