1. We can do integer programming in polynomial time using
the Graver basis, and hence, by the ellipsoid method, can also
separate over the integer hull in polynomial time. Can we do it
directly using the Graver basis without the ellipsoid method ?
2. (Related to 1): Can we find extended formulations
for the integer hull in terms of the Graver basis ?
3. (More specific than 2): Can we find extended formulations for
n-fold systems or lxmxn table problems with l,m fixed ?
4. Rather general: extend the class of objective functions that
can be optimized using the Graver basis or suitable stronger objects
or suitable oracles (steps in that direction are
5. Rather general: recently Hemmecke-Koeppe-Weismantel found an extension of
n-fold systems to n-fold 4-block systems. Find other and more general
extensions where the problem can still be solved in polynomial time.
6. Recently we show
that n-fold systems can be solved in polynomial time even for systems
defined over bimatrices A with VARIABLE entries
but fixed dimensions r,s,t. The running time is polynomial in the
unary encoding of A. Is the problem NP-hard if r,s,t, are still
fixed but the entries of A are encoded in binary ?
7. Rather general: the main recent result
shows that n-fold integer programs and hence multiway table problems
can be solved in cubic time and hence are
That is, roughly speaking, with the input being n and the margins,
and the parameters being m_1,...,m_k, deciding if there is a nonnegative
integer m_1x ...xm_kxn table with the given margins, can be solved in
time which is a polynomial in the input of degree independent of
the parameters. Since this is a result of quite different flavor than
common in parameterized complexity theory, there is hope that
it can be used to show the fixed-parameter tractability
of problems whose fixed-parameter complexity is open.
8. Are the n-fold 4-block systems of 5 also
fixed-parameter tractable or are they fixed-parameter hard ?
9. Is the Graver walk over 3x3xn tables, and more generally,
lxmxn tables with l,m fixed, rapidly mixing ?
10. Recently we show here that projections into R^d of lxmxn tables with given line sums by binary matrices have at most t(d;l,m) vertices independent of the table length n and of the line sums. Determine t(d;l,m) and in particular t(d;3,3) and even t(2;3,3), or at least obtain good bounds.