7
$\begingroup$

Given $AX\leq B$ where $A\in\Bbb Z^{m\times n}$,$B\in\Bbb Z^m$ finding $X\in\Bbb Z^n$ where $m\geq n$ is the integer programming problem. If $A$ is totally unimodular then the problem is solvable in polynomial time ($(mn)^c$ arithmetic operations on $(mn)^c$ sized words suffices).

Supposing we have the promise that the number of feasible solutions is polynomial then under what conditions can the problem be solved in polynomial time using Kannan's and Barnivok's algorithm (other than total unimodularity)?

$\endgroup$
  • $\begingroup$ There is a new paper to appear in STOC 2017 which gives a polynomial time algorithm when the matrix A is bimodular. That is, the subdeterminant values are at most 2. This is a generalization of totally unimodular case. I don't think it is based on using specifically Kannan and Barvinok's algorithm. I could be wrong. $\endgroup$ – Chandra Chekuri Mar 16 '17 at 19:49
  • 1
    $\begingroup$ The promise that the number of solutions is polynomial is a very weak promise. Indeed, even the promise that there will be either 0 or 1 solutions is still pretty weak. A polynomial-time algorithm for (ILP with the promise that there are either 0 or 1 feasible solutions) would yield a polynomial-time algorithm for Unique-SAT, which would in turn (by Valiant and Vazirani) would yield a randomized algorithm with polynomial expected running time for SAT. See also cstheory.stackexchange.com/q/25263/5038. $\endgroup$ – D.W. Mar 16 '17 at 20:48
  • $\begingroup$ @ChandraChekuri yes Kannan's and I believe Barvinok's algorithm has nothing to do with Unimodularity. I just mentioned do not use unimodularity because I did not want the case of total unimodularity discussed in solutions. It is unlikely that Kannan's algorithm or Barnivok's algorithm runs uniformly in $n^{O(n)}$ time for all inputs. For which inputs do the algorithms run in poly time? $\endgroup$ – Turbo Mar 16 '17 at 22:01
  • $\begingroup$ @D.W. That is why I said 'under which conditions'. $\endgroup$ – Turbo Mar 16 '17 at 22:03
  • 1
    $\begingroup$ Ok so you want to know when these two specific algorithms run in polynomial time? Why? Can you provide references for Kannan's and Barvinok's algorithms? (I know Kannan's IP algorithm, and Barvinok's lattice point counting algorithm. Do you mean the adaptation of Barvinok's that solves the IP rather than the counting problem?) More importantly, can you provide a reference for the fact that Kannan's or Barvinok's algorithm runs in polynomial time when the constraint matrix is TU? $\endgroup$ – Sasho Nikolov Mar 17 '17 at 1:40

Your Answer

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

Browse other questions tagged or ask your own question.