When: April 29, 2015, 12:30 PM
Location: 3rd Floor Orchard View Room , Discovery Building
Contact: 608-316-4401, firstname.lastname@example.org
On the Existence of Compact Epsilon-Approximated Formulations for Knapsack in the Original Space
We show that there exists a family of Knapsack polytopes such that for each P in the family and each epsilon>0, any epsilon-approximated formulation of P in the original space R^n requires a number of inequalities that is super-polynomial in n. This answers a question by Bienstock and McClosky (2012). We also prove that, for any down-monotone polytope and any fixed epsilon > 0, an epsilon approximated formulation in the original space can be obtained with inequalities using at most O(log n) different coefficients. Joint work with Yuri Faenza.
SILO is a lecture series with speakers from the UW faculty, graduate students or invited researchers that discuss mathematical related topics. The seminars are organized by WID’s Optimization research group.
SILO’s purpose is to provide a forum that helps connect and recruit mathematically-minded graduate students. SILO is a lunch-and-listen format, where speakers present interesting math topics while the audience eats lunch.
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: Laura Sanita, Assistant Professor, Combinatorics & Optimization Department, University of Waterloo, Ontario, Canada