« 2(.)0 seconds | Main | I'm a frayed knot. »

January 04, 2006


Does Koltun prove a strongly polynomial linear feasiblity algorithm? Or is he just sketching out an approach?


He's really just sketching a promising variant of the simplex algorithm. Simplex (in its simplest form) can be described as a guided walk along the edges of the feasible polyhedron. Vladlen's algorithm uses a different graph—the arrangement of the constraint hyperplanes—which provably has only polynomial diameter. Polytope graphs are believed to have small diameter [http://www.math.ethz.ch/~feichtne/ATDM/semi04winter/node11.html], but but the lack of proof is commonly cited as a bottleneck in finding a strongly-polynomial simplex algorithm. Vladlen's result removes that bottleneck.

Ok. So what happened with Koltun? Did he just give up on this strongly polynomial simplex pivot-scheme? Or did he want to claim credit for the arrangement idea and is trolling for collaborators to finish the job? Or does he want two papers out of this little fest?

The comments to this entry are closed.