Hardness of discrete geometric area minimization problem? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T17:04:53Z http://mathoverflow.net/feeds/question/46051 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/46051/hardness-of-discrete-geometric-area-minimization-problem Hardness of discrete geometric area minimization problem? Mohammad Al-Turkistany 2010-11-14T15:43:25Z 2010-11-16T00:25:04Z <p>This question was originally posted on: <a href="http://cstheory.stackexchange.com/questions/2844/hardness-of-geometric-area-minimization-problem" rel="nofollow">cstheory.stackexchange</a> <a href="http://cstheory.stackexchange.com/questions/2844/hardness-of-geometric-area-minimization-problem" rel="nofollow"></a></p> <p>Given $xyz=C$ where $x, y,$ and $z$ are integer variables and $C$ is integer constant. Assume all integers are encoded in binary.</p> <blockquote> <p>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?</p> </blockquote> <p><strong>Motivation</strong>: I'm interested in the following generalized problem:</p> <p><strong>Input</strong>: integers $C$ and $K$</p> <p><strong>Problem</strong>: Find integers $x$, $y$, and $z$ such that $xyz\ge C$ and $xy+xz+yz\le K$</p> http://mathoverflow.net/questions/46051/hardness-of-discrete-geometric-area-minimization-problem/46101#46101 Answer by Aaron Meyerowitz for Hardness of discrete geometric area minimization problem? Aaron Meyerowitz 2010-11-15T06:24:42Z 2010-11-16T00:25:04Z <p>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 <code>$K \ge 3C^{2/3}+6C^{1/3}+3$</code>. Actually you can do slightly better that by allowing $x \le y \le z \le x+1$. </p> <p>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$</p> <p><strong>later</strong> 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.</p> <p>[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]</p>