Abstract. We investigate the following question: How close can two disjoint lattice polytopes contained in a fixed hypercube be? This question stems from various contexts where the minimal distance between such polytopes appears in complexity bounds of optimization algorithms. We provide nearly matching bounds on this distance and discuss its exact computation. We also give similar bounds for disjoint rational polytopes whose binary encoding length is prescribed.

The theory of $n$-fold integer programming has been recently emerging as an important tool in parameterized complexity. The input to an $n$-fold integer program (IP) consists of parameter $A$, dimension $n$, and numerical data of binary encoding length $L$. It was known for some time that such programs can be solved in polynomial time using $O(n^{g(A)}L)$ arithmetic operations where $g$ is an exponential function of the parameter. In 2013 it was shown that it can be solved in fixed-parameter tractable (FPT) time using $O(f(A)n^3L)$ arithmetic operations for a single-exponential function $f$. This, and a faster algorithm for a special case of combinatorial $n$-fold IP, have led to several very recent breakthroughs in the parameterized complexity of scheduling, stringology, and computational social choice. In 2015 it was shown that it can be solved in strongly polynomial time using $O(n^{g(A)})$ arithmetic operations. Here we establish a result which subsumes all three of the above results by showing that $n$-fold IP can be solved in strongly polynomial FPT time using $O(f(A)n^3)$ arithmetic operations. In fact, our results are much more general, briefly outlined as follows. - There is a strongly polynomial algorithm for ILP whenever a so-called Graver-best oracle is realizable for it. - Graver-best oracles for the large classes of multi-stage stochastic and tree-fold ILPs can be realized in FPT time. Together with the previous oracle algorithm, this newly shows two large classes of ILP to be strongly polynomial; in contrast, only few classes of ILP were previously known to be strongly polynomial. - We show that ILP is FPT parameterized by the largest coefficient $\|A\|_\infty$ and the primal or dual treedepth of $A$, and that this parameterization cannot be relaxed, signifying substantial progress in understanding the parameterized complexity of ILP.

We introduce and study the problem of optimizing arbitrary functions over degree sequences of hypergraphs and multihypergraphs. We show that over multihypergraphs the problem can be solved in polynomial time. For hypergraphs, we show that deciding whether a given sequence is the degree sequence of a 3-hypergraph is NP-complete, thereby solving a 30 year long open problem. This implies that optimization over hypergraphs is hard even for simple concave functions. In contrast, we show that for graphs, if the functions at vertices are the same, then the problem is polynomial time solvable. We also provide positive results for convex optimization over multihypergraphs and graphs and exploit connections to degree sequence polytopes and threshold graphs. We then elaborate on connections to the emerging theory of shifted combinatorial optimization.

Optimization over $l\times m\times n$ integer 3-way tables with given line-sums is NP-hard already for fixed $l=3$, but is polynomial time solvable with both $l,m$ fixed. In the huge version of the problem, the variable dimension $n$ is encoded in binary, with $t$ layer types. It was recently shown that the huge problem can be solved in polynomial time for fixed $t$, and the complexity of the problem for variable $t$ was raised as an open problem. Here we solve this problem and show that the huge table problem can be solved in polynomial time even when the number $t$ of types is variable. The complexity of the problem over 4-way tables with variable $t$ remains open, where all we know is that the associated decision problem is in NP intersect coNP. Our treatment goes through the more general class of huge $n$-fold integer programming problems. We show that huge integer programs over $n$-fold products of totally unimodular matrices can be solved in polynomial time even when the number $t$ of brick types is variable.

We consider optimizing a nonlinear objective function over a weighted independence system presented by a linear-optimization oracle. We provide an efficient algorithm that determines an r-best solution for nonlinear functions of the total weight of an independent set, where r depends only on certain Frobenius numbers of the individual weights and is independent of the size of the ground set. In contrast, we show that finding an optimal (0-best) solution requires exponential time.

We study the problem of optimizing nonlinear objective functions over matroids presented by oracles or explicitly. Such functions can be interpreted as the balancing of multicriteria optimization. We provide a combinatorial polynomial time algorithm for arbitrary oracle-presented matroids, that makes repeated use of matroid intersection and an algebraic algorithm for vectorial matroids. Our work is partly motivated by applications to minimum-aberration model-fitting in experimental design in statistics, which we discuss and demonstrate in detail.

Multiway 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 outcome of our work is that each of the following problems is intractable already for "slim" 3-tables, with constant number 3 of rows: (1) deciding existence of 3-tables with specified 2-marginals; (2) counting all 3-tables with specified 2-marginals; (3) deciding whether a specified value is attained in a specified entry by at least one of the 3-tables having the same 2-marginals as a given table. This implies that a characterization of feasible marginals for such slim tables, sought by much recent research, is unlikely to exist. Another 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. Remarkably, it enables us to automatically recover a famous example due to Vlach of a "real-feasible integer-infeasible" collection of 2-marginals for 3-tables of smallest possible size (3,4,6).

Abstract We consider the problem of coordinating robots moving on a network. Each robot is autonomous and needs to visit various sites of the network at various times. The sequence of destinations for each robot changes dynamically and unpredictably. Recently, Onn and Tennenholtz showed that the problem can be solved by introducing a social law on the network, which, once obeyed by all robots, enables each to move to any desired destination without collisions and regardless of the actions of other robots, needing neither central coordination nor mutual communication. This social law can be derived from a suitably defined routing of the graph underlying the network. Here, we study the complexity of routing. We provide an effective characterization of 2‐routable graphs, and by establishing a correspondence between hypergraph coloring and graph routing, we show that computing or approximating an optimal routing is generally hard. We also discuss routing in planar graphs, which often underlie robotic networks and show that the correspondence between coloring and routing together with the Four Color Theorem guarantee the existence of small and effectively computable routings in bipartite planar graphs of small radius. The complexity of routing arbitrary planar graphs remains open. © 2002 Wiley Periodicals, Inc.

We consider a problem of maximizing convex functionals over matroid bases. It is richly expressive and captures certain quadratic assignment and clustering problems. While generally intractable, we show that it is efficiently solvable when a suitable parameter is restricted.

The following integer analogue of a Radon partition in affine space $\mathcal{R}^d $ is studied: A partition $( S,T )$ of a set of integer points in $\mathcal{R}^d $ is an integral Radon partition if the convex hulls of S and T have an integer point in common. The Radon number $r( d )$ of an appropriate convexity space on the integer lattice $\mathcal{Z}^d $ is then the infimum over those natural numbers n such that any set of n points or more in $\mathcal{Z}^d $ has an integral Radon partition. An $\Omega ( 2^d )$ lower bound and an $O( d2^d )$ upper bound on $r( d )$ are given, $r( 2 ) = 6$ is proved, and the existence of integral Radon partitions, in lattice polytopes having a 1-skeleton with a large stable set of vertices, is established. The computational complexity of deciding if a given set of points in $\mathcal{Z}^d $ has an integral Radon partition is discussed, and it is shown that if d is fixed, then this problem is in P, while if d is part of the input, it is NP-complete.