内点法で新しい結果

arXiv をチェックしていたら、内点法の新しい結果が出ていて、なんと infeasible interior-point method のオーダーが低くなっている。

内点法や線形計画問題の理論的な性質は 2000 年頃までの研究でほとんどなされており、それ以降はソフトウェア開発などが中心で理論的な前進はあまりない状況だった。
理論的な論文に関しても、「今までと同じオーダーの解析ができました」が主流であったが、今回の論文は違うようだ。

非常に面白そうなので、あとで読んでみることにしよう。