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,
On Feb 23, 6:30 pm, rge11x <rge...@netscape.net> wrote:
> Hello
> 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
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...)
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)).
|
