We consider a problem of optimizing convex functionals over matroid bases. It is richly expressive and captures certain quadratic assignment and clustering problems. While generally NP-hard, we show it is polynomial time solvable when a suitable parameter is restricted.

Multi-way tables with specified marginals arise in a variety of applications in statistics and operations research. We provide a comprehensive complexity classification of three fundamental computational problems on tables: existence, counting and entry-security. One major outcome of our work is that each of the following problems is intractable already for "slim" 3-tables, with constant and smallest possible number 3 of rows: (1) deciding existence of 3-tables with given consistent 2-marginals; (2) counting all 3-tables with given 2-marginals; (3) finding whether an integer value is attained in entry (i,j,k) by at least one of the 3-tables satisfying given (feasible) 2-marginals. This implies that a characterization of feasible marginals for such slim tables, sought by much recent research, is unlikely to exist. Another important consequence of our study is a systematic efficient way of embedding the set of 3-tables satisfying any given 1-marginals and entry upper bounds in a set of slim 3-tables satisfying suitable 2-marginals with no entry bounds. This provides a valuable tool for studying multi-index transportation problems and multi-index transportation polytopes.

We provide a polynomial time algorithm for computing the universal Gr\"obner basis of any polynomial ideal having a finite set of common zeros in fixed number of variables. One ingredient of our algorithm is an effective construction of the state polyhedron of any member of the Hilbert scheme Hilb^d_n of n-long d-variate ideals, enabled by introducing the Hilbert zonotope H^d_n and showing that it simultaneously refines all state polyhedra of ideals on Hilb^d_n.

This paper discusses properties of the graphs of 2-way and 3-way transportation polytopes, in particular, their possible numbers of vertices and their diameters. Our main results include a quadratic bound on the diameter of axial 3-way transportation polytopes and a catalogue of non-degenerate transportation polytopes of small sizes. The catalogue disproves five conjectures about these polyhedra stated in the monograph by Yemelichev et al. (1984). It also allowed us to discover some new results. For example, we prove that the number of vertices of an $m\times n$ transportation polytope is a multiple of the greatest common divisor of $m$ and $n$.