[Lowerbounds, Upperbounds]

I have a Slashdot backlog… I am still on May 22. So it wasn’t until this noon that I learned about the passing away of George Dantzig, the inventor of the Simplex method for solving LPs. Salute.

This reminds of a discussion I had with one of our faculty candidates last semester. Vladlen Koltun gave a fabulous job talk here and the first half of it was devoted to his work on strongly polynomial time linear programming. His magic weapon seems to be arrangement polytopes. The key idea is that linear programming on any polytope can be reduced, in polynomial time of course, to linear programming on an arrangement polytope with provably polynomial diameter. My notes say the diameter is $n * d$, where $d$ is the number of variables (dimension) and $n$ is the number of half-spaces (”faces”).

The diameter of any given polytope is important for Simplex, which navigates on extreme points. This is one major reason why the Hirsch conjecture attracts a lot of attention. The conjecture states that the diameter of any polytope is bounded by $n - d$. (I know how to check that on a “hypercube” for $d$ being 2 and 3. :P) The fear is that there may exist a “worst-case” polytope with super-polynomial diameter that will ruin Simplex.

But using this reduction idea as told by Koltun, the diameter may no longer be an obstacle and instead we may choose to focus our energy on navigating on an arrangement polytope. At this point let me end the summary by noting that he showed, together with Umesh Vazirani, that linear programming is still not easy even when reduced to arrangement polytopes. I don’t know if they have any newer developments since then.

Back to our discussion after his talk. Several years ago I hit upon a result which I have dug up back when I was studying the subject of smoothed analysis:

Carl W. Lee, Regular Triangulations of Convex Polytopes, DIMACS Technical Report 90-16, 1990.

In this paper, Lee showed that every $d$-dimensional polytope can “patched” into a $(d+1)$ dimensional polytope in which the original polytope is a facet of the new polytope and the new polytope has $2(n-d)$ diameter. It’s not quite Hirsch, but a linear diameter seems too good already.

Lee’s construction is pretty simple: add a new dimension and add a new point at coordinate $(0, \ldots,0,1)$, i.e., it is the only point that is not lying on the 0-plane of the new dimension. So you first get a pyramid. The degeneracy at the apex is handled by a careful but simple perturbation. More precisely, starting with the linear program:

$\max c \cdot x$
$a_i \cdot x \leq b_i, 1 \leq i \leq n$

We transform it into

$\max c \cdot x + 0x_{d+1}$
$a_i \cdot x + (b_i - \epsilon_i)x_{d+1} \leq b_i, 1 \leq i \leq n$
$x_{d+1} \geq 0$

where the $\epsilon_i$ are indeterminates with lexicographic order $0$ < $\epsilon_n$ << $\cdots$ << $\epsilon_1$ << $1$. (Apparently ASCIIMathML doesn't support \ll yet.) Check that the apex is indeed at $(0, \ldots, 0, 1)$. Because the $\epsilon_i$ are very small, we know that $(x, 0)$ is optimal for the new program iff $x$ is optimal for the original.

Not surprisingly, we are not done yet. It's true that in principle the new program can be solved in a linear number of pivots, but the hard question remains: which sequence of pivots do you want?

Now how Lee's method meshes with tools from smoothed analysis seems to be a long story. My day dreaming is that we could control the apex perturbation more carefully. Then the apex can be used as a polynomial time oracle: You start at an extreme point in the original polytope, take the airplane to go to the apex, compute, then jump down with a parachute along a carefully chosen edge to end up at another extreme point that is expected to be closer to the optimal.

I hope one day I will come back to write more. "Time is always against us. Please, take a seat there."

As an aside, from this Slashdot post I also learned about The Unsolvable Math Problem urban legend in which Dantzig unknowingly solved two major open problems as homework questions. Hehe.