特集記事—楕円体法：調査

1979年2月、L. G. Khachiyanによるメモは、線形計画法のための楕円体法が多項式時間で実装できることを示しました。この結果は大きな興奮を呼び起こし、多くの技術論文を刺激しました。通常、これほど最近の研究についての調査は必要ありませんが、現在の状況は明らかに例外的です。Khachiyanの結果に関する情報は異常に早く広まりましたが、その重要性の理解はそれに比べて遅れています。一般的に、楕円体法の正確な性質やKhachiyanの多項式性に関する結果の実用的意義、実装、線形計画法の領域外の問題への潜在的適用、以前の研究との関係など、様々な点が十分に理解されていません。私たちの目的は、楕円体法の調査、歴史的先行研究、最近の発展、現在の研究の文脈において、これらの重要な問題を明確にする手助けをすることです。