A geometer’s view of the simplex algorithm for linear optimization

Speaker: 

Jesus de Loera

Institution: 

UC Davis

Time: 

Thursday, May 3, 2018 - 3:00pm to 4:00pm

Host: 

Location: 

RH 306

Linear programs (LPs) are, without any doubt, at the core of both the theory and the practice of mondern applied and computational Optimization (e.g., in discrete optimization LPs are used in practical computations using branch-and-bound, and in approximation algorithms, e.g., in rounding schemes). At the same time  Dantzig’s Simplex method is one of the most famous algorithms to solve LPs and SIAM elected it as one of the top 10 most influential algorithms of the 20th Century.

But despite its key importance, many simple easy-to-state mathematical properties of the Simplex method and its geometry remain unknown. The geometry of the simplex method is very much the convex-combinatorial geometry of polyhedra (e.g., cubes, simplices, etc). Perhaps the most famous geometric-combinatorial challenge is to determine a worst-case upper bound for the graph diameter of polyhedra.  Although a lot of progress has been made, today even for the most elementary textbook linear programs we remain ignorant as to what the exact diameter upper bounds are. In this talk, I will discuss this  geometric problem and present the key ideas for proving that the diameter of graphs of all network-flow polytopes satisfy the Hirsch linear bound. This is joint work with S. Borgwardt (Univ of Colorado) and E. Finhold (Fraunhofer Institut).

Braids, Polynomials and Hilbert's 13th Problem

Speaker: 

Jesse Wolfson

Institution: 

UC Irvine

Time: 

Thursday, March 1, 2018 - 4:00pm to 5:00pm

Location: 

RH 306

There are still completely open fundamental questions about polynomials in one variable. One example is Hilbert's 13th Problem, a conjecture going back long before Hilbert.  Indeed, the invention of algebraic topology grew out of an effort to understand how the roots of a polynomial depend on the coefficients. The goal of this talk is to explain part of the circle of ideas surrounding these questions. 

Along the way, we will encounter some beautiful classical objects - the space of monic, degree d square-free polynomials, algebraic functions, lines on cubic surfaces, level structures on Jacobians, braid groups, Galois groups, and configuration spaces - all intimately related to each other, all with mysteries still to reveal.

On the Erdos-Szekeres convex polygon problem

Speaker: 

Andrew Suk

Institution: 

UCSD

Time: 

Thursday, December 7, 2017 - 4:00pm to 5:00pm

Host: 

Location: 

RH 306

The classic 1935 paper of Erdos and Szekeres entitled "A combinatorial problem in geometry" was a starting point of a very rich discipline within combinatorics: Ramsey theory.  In that paper, Erdos and Szekeres studied the following geometric problem.  For every integer n ≥ 3, determine the smallest integer ES(n) such that any set of ES(n) points in the plane in general position contains n members in convex position, that is, n points that form the vertex set of a convex polygon.  Their main result showed that ES(n) ≤ {2n  - 4 \choose n-2} + 1 = 4^{n -o(n)}.  In 1960, they showed that ES(n) ≥ 2^{n-2} + 1 and conjectured this to be optimal.  In this talk, we will sketch a proof showing that ES(n) =2^{n +o(n)}.

Pages

Subscribe to RSS - Colloquium