decomposing rationals
rge11x
let x be any rational number, and also given an arbitrary interval [a,
b] that does not contain x. Is there a systematic way to find a set
of integers m1, m2, ..mK and corresponding rationals y1, y2,...yK all
in the interval [a, b] such that their linear combination is x,
x= m1.y1 + m2 . y2 + ....+ mK . yK
and the |m1| + |m2| + ...+ |mK| is minimum?
thank you
Tony
If [a,b] contains zero, then it's easy. Also if b < 0 we can work with
[-b,-a]. So we can assume 0 < a < b. Also we might as well assume x >
0.
Suppose y1 < y2, and m1 and m2 are both positive or both negative.
Then we can replace m1.y1 + m2.y2 with (m1+m2)y, where
y = (m1.y1 + m2.y2)/(m1 + m2) is a rational number in [y1,y2]. So we
need at most two terms, a positive and a negative: x = m1.y1 - m2.y2,
with m1 >= 0 and m2 >= 0.
Given m1 and m2, m1.y1 - m2.y2 has minimum m1.a - m2.b and maximum
m1.b - m2.a, so we need to find m1 and m2 such that m1.a - m2.b <= x
<= m1.b - m2.a; then we can let y1 = a+t and y2 = b-t where t varies
from 0 to b-a, and so m1.y1 - m2.y2 varies from <= x to >= x. This
gives y1 and y2 in [a,b] such that x = m1.y1 - m2.y2. If a and b are
rational, then y1 and y2 are also rational.
So it boils down to finding m1 and m2 such that m1.a - m2.b <= x <=
m1.b - m2.a, with m1 + m2 minimum.
(If a and b are not rational, we need strict inequality: m1.a - m2.b <
x < m1.b - m2.a. Then we can replace a and b with rational
approximations a' and b' so that the inequalities still hold.)
-- End of Part I -- (part II may or may not follow...)
Mike
On Feb 24, 8:30Êam, Tony <tempt...@freemail.hu> wrote:
> So it boils down to finding m1 and m2 such that m1.a - m2.b <= x <=
> m1.b - m2.a, with m1 + m2 minimum.
If a and b are rational,
this becomes an integer linear programming problem in two variables.
Such things are solvable in polynomial time.
I don't remember details.
I think that you can solve the linear relaxation
and plug away with Gomory fractional cuts.
> (If a and b are not rational, we need strict inequality: m1.a - m2.b <
> x < m1.b - m2.a. Then we can replace a and b with rational
> approximations a' and b' so that the inequalities still hold.)
Selecting the approximations could be tricky.
One possibility:
Select a'< a and b'> b.
Solve.
If min(y1, y2)< a, select the new a' in ((min(y1, y2)+a)/2, a).
Similarly for b.
Rinse and repeat as necessary.
An upper bound might be useful.
If a and b are rational.
Any rational in the range [0, b-a] can be represented with score up to
2.
Any rational in the range [0, b] can be represented with score up to
1+ceil(a/(b-a)).
x - b*(floor(x/b)) in [0, b].
An upper bound on the necessary score is floor(x/b)+1+ceil(a/(b-a)).