In the worst case complexity analysis of all the polynomial algorithms in linear programming such as ellipsoid method and interior point method, there is an assumption that the input data must be integer. Using this assumption, then they bound the bitlength of input data by $L$. Now, the question is as follows:

Q: How can this assumption be met for a linear programming with rational data. In other words, does there exist a way to convert the LP with rational data to an integer one? To me, it seems as though there is a way since data integrality is an assumption for these algorithms.

  • 1
    $\begingroup$ This is an interesting question to which I don't have a good answer. Transforming a rational LP to an integer LP probably immensely increases the description length, but I suspect that repeating the standard complexity arguments with rational input data would preserve the standard bounds, except for different constants in the Landau symbols. $\endgroup$ Jul 25 '12 at 17:35

Why not multiply the data (i.e., the matrix $A$ and vector $b$ in the constraint $Ax \ge b$ and the vector $c$ in the objective function $c^Tx$) by the greatest common denominator of all entries? If you do so, you end up with a problem that has only integer constraints. Of course, you could do that for each individual constraint separately if you want to use smaller multipliers.

If all you want to do is estimate the bit size you need, then the bits you need to represent a fraction $\alpha/\beta$ in a matrix or vector entry is simply $bits(\alpha/\beta)=bits(\alpha)+bits(\beta^*)$ where $\beta^*\ge \beta$ is the smallest common multiplier, and this yields the same complexity bound for the linear program if you adjust the bit count for rational numbers. Of course, this yields the very same bound as you get if you just scale the entire problem by the largest common denominator $\beta^*$.

  • $\begingroup$ Wouldn't multiplying each constrain separately with smaller multipliers give a better bound (or one that is at least as good) since it is likely that process would lead to smaller integers? $\endgroup$ Jul 26 '12 at 6:25
  • $\begingroup$ Shouldn't be lcm instead of gcd? $\endgroup$
    – Star
    Jul 26 '12 at 8:29
  • $\begingroup$ @Star: Yes, of course. $\endgroup$ Jul 26 '12 at 14:46
  • $\begingroup$ @GodricSeer: Yes, that's what I meant by considering each individual constraint separately. $\endgroup$ Jul 26 '12 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.