Featured event

Abstract polyhedra

WID-DOW Seminar: Robert Hildebrand

Event Details

When: July 8, 2015, 12:00 PM

Location: 3rd Floor Orchard View Room , Discovery Building

Contact: 608-316-4676, hstampfli@wisc.edu

An FPTAS for minimizing some quadratic polynomials over integer points in polyhedra

Robert Hidebrand
Robert Hidebrand

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
http://www.ifor.math.ethz.ch/staff/hirobert