カーマーカーのアルゴリズム
行列 A {\displaystyle A} 、ベクトル b {\displaystyle b} に対し、以下の正準形式(英語版)な線形計画問題を考える。
maximize cx
subject to Ax ≤ b.
すなわち、
条件 Ax ≤ b の下で、
cx を最大にするベクトル x を求める。
このアルゴリズムはその時点での最適化実行可能方向 (feasible direction toward optimality) を求め、0 < γ ≤ 1 の範囲で縮小する。
カーマーカーのアルゴリズムは複雑である。アフィン・スケーリング法と呼ばれる簡略化されたバージョンが、カーマーカーとは別の人物により提案、解析されている。このアルゴリズムは以下のように簡潔に示される。ただし、アフィン・スケーリング・アルゴリズムは実用上効率が良いが、多項式時間アルゴリズムではない。
"←"は「代入」を示す記号である。例えば、"α ← β"はαにβを代入することを示す。
"return"はアルゴリズムを停止させ、戻り値を出力する。