When: July 8, 2015, 12:00 PM
Location: 3rd Floor Orchard View Room , Discovery Building
Contact: 608-316-4676, email@example.com
An FPTAS for minimizing some quadratic polynomials over integer points in polyhedra
Although integer linear programming is an NP-Hard problem,Lenstra showed that in fixed dimension the problem can be solved in polynomial time. On the other hand, the problem of minimizing a quartic polynomial objective function over the integer points in polyhedra is NP-Hard even in dimension 2. The complexity of minimizing quadratic and cubic polynomials in fixed dimension remains an open question. As a step in this direction, we will present an FPTAS for minimizing some quadratic polynomials in fixed dimension.
Since optimization spans every discipline, the subject of each WID-DOW (Wisconsin Institute for Discovery- Doing Optimization at WISCONSIN) seminar may include such diverse topics as optimizing traffic flow or power storage or improving a bioenergy source. The WID-DOW seminar speakers are UW faculty and visiting professors that discuss an optimization application or how optimization impacts their research.
Speaker: Robert Hildebrand, Post-doc, Swiss Federal Institute of Technology, Zurich, Switzerland