Conti-Traverso アルゴリズムは、その後改良されて、いわゆる Y は必要でなくなりました。興味があれば "Gröbner Bases and Convex Polytopes", Bernd Strumfels, 1996. を参照してください。なお、Conti-Traverso アルゴリズムも、その改良も、実際、計算機にかけると遅くて使い物になりません。理論面では面白いのですが。計算が早くなる改良を誰かやっていたら非常に興味があります。僕の観測範囲では残念ながら見つかりません。

ありがとうございます。
先日、 Conti-Traverso アルゴリズム の話を聞く機会があったのですが、そのときはYを使う代わりに初期解を与えていたと思います。
この改良はそういう改良でしょうか、それともYも初期解も不要なような改良でしょうか。

改良アルゴリズム(1994-1995 に様々な著者が発表した)において Y は不要ですが、初期解（というか実行解）は必要です。任意の実行解から最適解が求まります。"toric ideal" というキーワードが出てきたのなら、間違いなく Y 不要改良アルゴリズムを説明してます。Conti-Traverso の論文(1991)には "toric ideal" はでてきません。
しかし、2012 年に Conti-Traverso に光が当たるとは、素晴らしい懐古主義ですね。なにか新しいことがわかったのでしょうか…？何か新しいことがわかったのだとしたら、僕もそれで論文を書きたいです（フゥ）

Conti-Traverso の論文(1991) は、むしろ実行解が与えられていなくても解けるようYを導入して工夫しているように思えるので、「実行解が与えられていればYは不要」ということ自体は、あまり改良っぽく思えないです。
あと、Conti-Traverso の論文(1991) は toric ideal という言葉は使っておらず binomial ideal とだけしか言ってないですが、実際には常に toric ideal になってませんか……?

ちなみに、聞いたのは慶大の武田研 http://www.ae.keio.ac.jp/lab/soc/takeda/ の学生の発表でした。

Conti-Traverso アルゴリズムについて、僕は時間・空間計算量を調べていません（論文はあるのに）。歴史的経緯で後から出たアルゴリズムを「改良」と呼んでいました。ごめんなさい。variant が適切だったですね。
Conti-Traverso にでてくる ideal の消去イデアルを計算する（つまり Y を消去する）と toric ideal になります。その意味でさかいさんは正しいです。
慶応の武田研はノーマークでした。新規の結果やブレイクスルーを出してくださるよう期待しております。機会さえあれば、お話を聞きたいし、僕からもなにか話をしたい。
僕が学生だった頃は、日本だと東大今井研・(旧:東京理科大 現:目白大)平林研・同志社大渡邊研あたりが興味を持って調べてくれていましたが、現在は放置されている感があります。CREST 日比チームも Conti-Traverso アルゴリズムについてメンバー全員が知っていますが、公開されている文書を読む限り研究対象にはしていないみたいです。オワコンなのかなあ残念、と感じていたところに、さかいさんの G+ の記事が出たのでつい食いついてしまいました。

いえいえ、色々とありがとうございます。

池上さんの「数列と多項式の愛しい関係」で Cont-Traverso アルゴリズムを知ってから、だいぶ経ちますが、ようやく少し分かって来ました。
http://madscientist.jp/~ikegami/articles/IntroSequencePolynomial.html