1
$\begingroup$

We know that integer programming with bounded dimension or fixed number of variables can be solved in polynomial time by Lenstra's result(from results of the LLL algorithm). After heavy foraging i still wasnt able to answer the following 2 questions,

1) What is the exact complexity of this poly-time algorithm?

2) Are there any practical(real world) applications of integer programming in a bounded dimension?

Any input would be useful. Thanks

$\endgroup$
0
$\begingroup$

@1) As far as I am aware, the runtime of Lenstra's algorithm depends on the problem you are trying to solve: For example, for the "Cutting Stock Problem" (CSP) the dimension-reduction-step can exploit the special structure of CSP and thereby yields a run time inferior to the naive/generic implementation.

@2) Lenstra's algorithm may be used to compute an $(OPT + 1)$-solution to the CSP, see "An $OPT + 1$ algorithm for the cutting stock problem with a constant number of object lengths" by K. Jansen and R. Solis-Oba.

As CSP is only a more compact way of formulating the "Bin Packing Problem", the algorithm can be used to find a nearly-optimal packing of objects into bins of a certain capacity. The number of different object types is thereby the dimension $d$ of the problem (for example a postal service only allows packets of $d$ diffenent heights) and is responsible for the exponential term of the run time. The actual number of objects only influences the run time polynomially.

$\endgroup$

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.