Ehrhart polynomials of matroid polytopes and polymatroids (2007)
De Loera, Jesús A., Haws, David C., Köppe, Matthias
We investigate properties of Ehrhart polynomials for matroid polytopes, independence matroid polytopes, and polymatroids. In the first half of the paper we prove that for fixed rank their Ehrhart...
Graphs of Transportation Polytopes (2007)
De Loera, Jesús A., Kim, Edward D., Onn, Shmuel, Santos, Francisco
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...
Pareto Optima of Multicriteria Integer Linear Programs (2007)
De Loera, Jesús A., Hemmecke, Raymond, Köppe, Matthias
We settle the computational complexity of fundamental questions related to multicriteria integer linear programs, when the dimensions of the strategy space and of the outcome space are considered...
De Loera, Jesús A., Hemmecke, Raymond, Köppe, Matthias, Weismantel, Robert
We show the existence of a fully polynomial-time approximation scheme (FPTAS) for the problem of maximizing a non-negative polynomial over mixed-integer sets in convex polytopes, when the number of...
N-Fold Integer Programming (2006)
De Loera, Jesús A., Hemmecke, Raymond, Onn, Shmuel, Weismantel, Robert
In this article we study a broad class of integer programming problems in variable dimension. We show that these so-termed {\em n-fold integer programming problems} are polynomial time solvable. Our...
FPTAS for mixed-integer polynomial optimization with a fixed number of variables (2005)
De Loera, Jesús A., Hemmecke, Raymond, Köppe, Matthias, Weismantel, Robert
We show the existence of an FPTAS for the problem of maximizing a non-negative polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed.
On the Computation of Clebsch-Gordan Coefficients and the Dilation Effect (2005)
De Loera, Jesús A., McAllister, Tyrrell B.
We investigate the problem of computing tensor product multiplicities for complex semisimple Lie algebras. Even though computing these numbers is #P-hard in general, we show that if the rank of the...
Integer Polynomial Optimization in Fixed Dimension (2004)
De Loera, Jesús A., Hemmecke, Raymond, Köppe, Matthias, Weismantel, Robert
We classify, according to their computational complexity, integer optimization problems whose constraints and objective functions are polynomials with integer coefficients and the number of variables...
Vertices of Gelfand-Tsetlin Polytopes (2003)
De Loera, Jesús A., McAllister, Tyrrell B.
This paper is a study of the polyhedral geometry of Gelfand-Tsetlin patterns arising in the representation theory $\mathfrak{gl}_n \C$ and algebraic combinatorics. We present a combinatorial...
Extremal properties for dissections of convex 3-polytopes (2000)
De Loera, Jesús A., Santos, Francisco, Takeuchi, Fumihiko
A dissection of a convex d-polytope is a partition of the polytope into d-simplices whose vertices are among the vertices of the polytope. Triangulations are dissections that have the additional...
The Complexity of Finding Small Triangulations of Convex 3-Polytopes (2000)
Below, Alexander, De Loera, Jesús A., Richter-Gebert, Jürgen
The problem of finding a triangulation of a convex three-dimensional polytope with few tetrahedra is proved to be NP-hard. We discuss other related complexity results.