Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

Integer linear optimization, that is the problem of optimizing a linear functional over the integer points of a polyhedron, is NP-hard. However, when we fix the number of variables, it can be solved in polynomial time using the algorithm of Lenstra (1983). More strongly, Khachiyan and Porkolab (2000) showed that convex polynomial functions can be minimized over the integer points of convex semialgebraic sets in polynomial time, when the number of variables is fixed. The situation is different when we consider arbitrary (not necessarily convex) objective functions over the integer points of a polytope. Even when the dimension is fixed >= 2 and the degree is bounded <= 4, the optimization problem is still NP-hard. We prove the existence of a fully polynomial-time approximation scheme (FPTAS) for the maximization problem where the objective function is non-negative on the feasible region, when the dimension is fixed. This is the strongest possible result, unless P=NP. We then extend the FPTAS to the case of mixed-integer polynomial optimization, where some of the variables are integers and some are reals. math.OC/0410111, math.OC/0505677 This is joint work with J. A. De Loera, R. Hemmecke, and R. Weismantel.