Skip to main content
4 votes

Under what conditions does an Integer Programming problem run in polynomial time?

The way I think about Kannan's algorithm (or, for that matter, any of the several "Lenstra-type" algorithms which present similar bounds as the original Lenstra algo from 1983) is that it's designed ...
kbala's user avatar
  • 141
4 votes
Accepted

What does the basis of the null space of the constraint matrix of a flow problem look like?

An illustrated example right-away Not to immediately bore you with lengthy preliminary remarks, let me begin with an illustration which, in a sense, already is an answer in itself. Here is an example ...
Peter Heinig's user avatar
  • 6,031
4 votes

Examples of matrices with all subdeterminants bounded away from $0$

For any distinct integers $x_1,\ldots,x_m$ you can take the matrix whose $i$-th row $(1 \leq i \leq m)$ is $(1,x_i,x_i^2,\ldots,x_i^{n-1})$. Each $n \times n$ submatrix is Vandermonde with distinct ...
Noam D. Elkies's user avatar
3 votes
Accepted

Is this totally unimodular family?

I don't see that your example matrix $M$ is TU. Taking the first three columns of rows 1, 4 and 7 gives the submatrix $$\begin{pmatrix}1&1&0\\ 1&0&1\\ 0&1&1\end{pmatrix}$$ ...
Thomas Kalinowski's user avatar
1 vote

Examples of matrices with all subdeterminants bounded away from $0$

Yes. Allow me to transpose your set-up, for reasons of my own dyslexia, and instead consider an $m \times n$ matrix $M$ with $m < n$. This matrix will have block decomposition $M = \big( D \, \big| ...
Jeanne Scott's user avatar
  • 1,847

Only top scored, non community-wiki answers of a minimum length are eligible