Isn't this similar to the "integer linear programming" problem (integer version of linear programming problem) ? It looks like you may be able to reduce this to some sort of knapsack problem. Of course, there's always the issue of how to represent the "reals" in this problem. At 06:42 AM 9/16/2008, Christian Boyer wrote:
Let f(x , x , ..., x ) = k x + k x + ... + k x 1 2 n 1 1 2 2 n n
where k , k , ..., k are n REAL constants 1 2 n
and x , x , ..., x are n INTEGERS (positive or negative) 1 2 n
If we try to have the best possible approximations of
f(x , x , ... x ) = 0 1 2 n
do you know good algorithms giving best values of (x , x , ..., x )? 1 2 n
When n = 2, a good algorithm is to compute the continued fraction of k / k 2 1 At each step of the algorithm, the continued fraction will give more and more excellent (x , x ). 1 2
But which algorithm(s) for n > 2?
Christian.