Hardness of discrete geometric area minimization problem?

2010-11-14T15:43:25Z

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$

Answer by Aaron Meyerowitz for Hardness of discrete geometric area minimization problem?

2010-11-15T06:24:42Z

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]

Hardness of discrete geometric area minimization problem? - MathOverflow

Hardness of discrete geometric area minimization problem?

Answer by Aaron Meyerowitz for Hardness of discrete geometric area minimization problem?