Speaker: Mohit Tawarmalani
Date: Friday, April 7, 2006
Time: 1:30 to 3:00 pm
Place: 388 Posner Hall
Title: Convex Extensions and Convexification of Nonlinear Sets
Abstract
We develop a theoretical framework of convex extensions that enables building convex envelopes of many nonlinear functions. We then use the framework to analyze inclusion certificates (that guarantee inclusion of a point in the convex hull of a disjunction) and provide insights into various hierarchies of relaxations. We extend the notion of lifting locally valid inequalities to global validity to generate linear and nonlinear inequalities for continuous nonlinear programming. As a consequence, we develop valid inequalities for certain mixed-integer bilinear sets and a procedure for generating convex hulls for certain disjunctive nonlinear sets.
Speaker: Ryan Williams
Time: Wednesday 12-1pm
Place: NSH 1507
Title: Using Linear Algebra for Faster Solution of NP-hard Problems
Abstract:
We present a connection between two fundamental problems in computer science: the well-known problem of Matrix Multiplication, and the very general problem of 2-CSP (2-Constraint Satisfaction Problem) Optimization which encodes many important graph optimization problems. While Matrix Multiplication is well-known to be a polynomial time problem, 2-CSP Optimization is NP-Hard. Despite the stark computational differences between the two problems, we show that better Matrix Multiplication algorithms yield better 2-CSP Optimization algorithms, focusing on the case of MIN-BISECTION: given a graph on 2k nodes, partition the nodes into two parts of k nodes such that the number of edges straddling the two parts is minimized. Namely, we show that if multiplication of n by n matrices is possible in (n^3)/f(n) time for some function f, then a MIN-BISECTION of a graph with n nodes can be found in roughly (2^n)/f(2^{n/3}) time. In particular, the n^{2.376} matrix multiplication algorithm of Coppersmith and Winograd implies that MIN-BISECTION can be solved in 2^{.792n} time. Prior to our work, no improvement over brute-force search (2^n time) was known for solving 2-CSP Optimization exactly.
