Tag Archives: Linear programming

Projections to the TSP Polytope

Posted on December 7, 2011 by Gil Kalai

Michael Ben Or told me about the following great paper Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf. The paper solves an old conjecture … Continue reading →

Posted in Computer Science and Optimization, Convex polytopes | Tagged , , , | 2 Comments

IPAM remote blogging: The Many Facets of Linear Programming

Posted on January 20, 2011 by Gil Kalai

The many facets of Linear Programming Here is an extremely nice paper by Michael Todd from 2001. It gives useful background for many lectures and it can serve as a good base point to examine last decade’s progress. Background post for … Continue reading →

Posted in Computer Science and Optimization | Tagged , | Leave a comment

Günter Ziegler: 1000$ from Beverly Hills for a Math Problem. (IPAM remote blogging.)

Posted on January 20, 2011 by Gil Kalai

Scanned letter by Zadeh. (c) Günter M. Ziegler left-to-right: David Avis, Norman Zadeh,  Oliver Friedmann, and Russ Caflish (IPAM director). Photo courtesy Eddie Kim. Update: The slides for Friedmann’s talk are now available. The conference schedule page contains now the slides for … Continue reading →

Posted in Computer Science and Optimization, Conferences, Guest blogger | Tagged | 4 Comments

Subexponential Lower Bound for Randomized Pivot Rules!

Posted on November 9, 2010 by Gil Kalai

Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick have managed to prove subexponential lower bounds of the form for the following two basic randomized pivot rules for the simplex algorithm! This is the first result of its kind and deciding … Continue reading →

Posted in Computer Science and Optimization, Convex polytopes, Games | Tagged , | 11 Comments

The Polynomial Hirsch Conjecture: A proposal for Polymath3

Posted on July 17, 2009 by Gil Kalai

This post is continued here.  Eddie Kim and Francisco Santos have just uploaded a survey article on the Hirsch Conjecture. The Hirsch conjecture: The graph of a d-polytope with n vertices  facets has diameter at most n-d. We devoted several … Continue reading →

Posted in Convex polytopes, Open discussion, Open problems | Tagged , , , | 43 Comments

A Diameter problem (7): The Best Known Bound

Posted on December 1, 2008 by Gil Kalai

  Our Diameter problem for families of sets Consider a family of subsets of size d of the set N={1,2,…,n}. Associate to a graph as follows: The vertices of  are simply the sets in . Two vertices and are adjacent if . … Continue reading →

Posted in Combinatorics, Convex polytopes | Tagged , | 1 Comment

A Diameter Problem (6): Abstract Objective Functions

Posted on November 4, 2008 by Gil Kalai

George Dantzig and Leonid Khachyan In this part we will not progress on the diameter problem that we discussed in the earlier posts but will rather describe a closely related problem for directed graphs associated with ordered families of sets. The role models for … Continue reading →

Posted in Combinatorics, Convex polytopes, Open problems | Tagged , | 7 Comments

Diameter Problem (3)

Posted on September 7, 2008 by Gil Kalai

3. What we will do in this post and and in future posts We will now try all sorts of ideas to give good upper bounds for the abstract diameter problem that we described. As we explained, such bounds apply … Continue reading →

Posted in Combinatorics, Convex polytopes, Open problems | Tagged , , | 1 Comment