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).

2 improved formatting

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$

1

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$