Some Open Problems and Research Directions


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 here and here).

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 here 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 here shows that n-fold integer programs and hence multiway table problems can be solved in cubic time and hence are FIXED-PARAMETER TRACTABLE. 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.