N-fold integer programming in cubic time

Details N-fold integer programming in cubic time N-fold integer programming in cubic time

2011-01-17

arxiv.org/abs/1101.3267v1

Mathematics

Optimization and Control

Scientific paper

N-fold integer programming is a fundamental problem with a variety of natural applications in operations research and statistics. Moreover, it is universal and provides a new, variable-dimension, parametrization of all of integer programming. The fastest algorithm for $n$-fold integer programming predating the present article runs in time $O\left(n^{g(A)}L\right)$ with $L$ the binary length of the numerical part of the input and $g(A)$ the so-called Graver complexity of the bimatrix $A$ defining the system. In this article we provide a drastic improvement and establish an algorithm which runs in time $O\left(n^3 L\right)$ having cubic dependency on $n$ regardless of the bimatrix $A$. Our algorithm can be extended to separable convex piecewise affine objectives as well, and also to systems defined by bimatrices with variable entries. Moreover, it can be used to define a hierarchy of approximations for any integer programming problem.

Affiliated with

Also associated with

No associations

Rating

N-fold integer programming in cubic time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with N-fold integer programming in cubic time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and N-fold integer programming in cubic time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-286580