TItle: A perfect graph, a sparse, symmetric matrix and a homogeneous cone walk into a bar … together??
| Speaker: | Levent Tuncel |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract: The talk title above sounds like the beginning of a corny joke; however, in this talk, we will indeed utilize results from a very large number of research areas. Many of these research areas are directly within Combinatorics and Optimization and some are from other areas covered in the rest of the Faculty of Mathematics. By building on results from convex optimization and analysis, graph theory, data structures and algorithms, sparse matrix computation and theory, abstract algebra, we show how to perform fundamental linear algebra operations in an efficient way for many families of algorithms for a nice class of convex optimization problems subsuming semidefinite programming problems. As a by product of our approach, we derive new primal-dual interior-point algorithms with polynomial-time iteration complexity and solve two open problems: one from 1998, the other from 2012.
This talk is based on joint work with Lieven Vandenberghe.