Building Algorithmic Polytopes

Who and when?
Dr. David Bremner, Professor at the Faculty of Computer Science at the University of New Brunswick, Fredericton, Canada, is going to visit our University on Friday, December 12th. His talk will start at 4:30 pm in the Visual Computing Lab C 061.

Topic: Building Algorithmic Polytopes
Researchers have studied the the Matching Polytope (the convex hull of all characteristic vectors of all perfect matchings in a complete graph) for almost 50 years. Recent results have shown in a certain sense that no polynomial size inequality representation for this polytope exists. Motivated by this, we are studying alternate “natural” ways of representing problems like matching as linear programs. In this talk I will discuss ongoing work to develop a compiler from a simple ALGOL-like pseudocode to polynomial sized linear programs. These LPs can compute the output for any input (of a given size) to the corresponding algorithm by a trivial encoding of the input into the objective function. The talk will cover the structure of the inequalities needed a simulate a simple bit-oriented register machine supporting arithmetic and arrays, and a limited kind of integrality guarantee needed to solve these systems as linear, rather than integer linear programs. I’ll also give an overview of the current compiler implementation, and time permitting a demo.

Comments are closed.