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 ...

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 ...

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 ...

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}$$
...

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| ...

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

#### Related Tags

total-unimodularity × 15matrices × 8

linear-programming × 8

linear-algebra × 7

integer-programming × 5

co.combinatorics × 4

computational-complexity × 2

oc.optimization-and-control × 2

matroid-theory × 2

reference-request × 1

graph-theory × 1

algorithms × 1

convex-geometry × 1

convex-polytopes × 1

abelian-varieties × 1

convex-optimization × 1

nonlinear-optimization × 1

quadratic-forms × 1

combinatorial-optimization × 1

positivity × 1

graph-minors × 1

network-theory × 1

operations-research × 1