Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$

share|improve this question
1  
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
show 1 more comment

1 Answer 1

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]

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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