Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

An exciting area of applied mathematics is discrete optimization. In recent years algebraic geometry, number theory, and commutative algebra have shown their potential to solve challenging problems in discrete optimization. But, until now, algebraic methods were always considered ``guilty'' of bad computational complexity (e.g., notorious bad complexity for computing Grobner bases). This talk hopes to show algebraic tools can compete (and win!) against more standard tools in discrete optimization when comparing their running times. Moreover, we argue this is the right way to treat non-linear integer programs. We present a new algebraic algorithm to solve {\em integer convex maximization} problems of the form $$\max\, \{c(w_1 x,\dots,w_d x):\ Ax=b,\ x\in\N^n\}\ ,$$ where $c$ denotes a convex function, and $w_i x$ denotes a linear functional. This algorithm works for arbitrary input data $A,c,w$, but we show that, under the assumption that $d$ is fixed, our algorithm runs in polynomial time for several important classes of matrices $A$. As corollary, we show several polynomially-solvable classes of problems with varying number of variables; including various multi-way transportation problems, packing problems, and partitioning problems. We conclude with a short discussion of how non-linear integer optimization has benefited from tools from algebraic geometry. This a talk surveying results obtained in joint work with various co-authors.