LP型の問題

アルゴリズムの研究において、LP 型の問題(一般化線形計画法とも呼ばれる) は、低次元線形計画法と特定の特性を共有し、同様のアルゴリズムで解決できる最適化問題です。LP 型の問題には、与えられた平面点の集合を含む最小の円を見つける問題など、それ自体は線形計画法ではない重要な最適化問題が数多く含まれています。これらの問題は、ランダム化アルゴリズムの組み合わせによって、問題を定義する要素の数に対して線形で、問題の次元に対して指数以下の時間で解決できます。

意味

LP 型問題は、Sharir & Welzl (1992) によって、要素の有限集合 $Sと、$ $S$ のサブセットを完全順序集合の値にマッピングする関数 $f$ が入力として与えられる問題として定義されました。関数は、次の 2 つの重要な特性を満たす必要があります。

単調性: すべての2つの集合 $A \subseteq B \subseteq S$ に対して、f ( A ) ≤ f ( B ) ≤ f ( S ) 。
局所性: すべての2つの集合 $A \subseteq B \subseteq S$ $とS$ のすべての要素 $x$ に対して、 $f$ $($ $A$ $) =$ $f$ $($ $B$ $) =$ $f$ $($ $A$ $\cup {$ $x$ $})$ である場合、 $f$ $($ $A$ $) =$ $f$ $($ $B$ $\cup {$ $x$ $})$ です。

LP 型問題の基底は、B のすべての適切な部分集合の f の値が B 自体よりも小さいという性質を持つ集合 B ⊆ S であり、LP $型$ 問題 $の$ 次元 $($ または $組み合わせ次元)$ は基底の最大濃度として定義されます。

最適化アルゴリズムは、関数 $f を$ 、それ自体が基底である集合、または基底に単一の要素を追加することによって形成される集合に対してのみ評価できるものと想定されます。あるいは、アルゴリズムは、基底 $B$ と要素 $xに対して$ $f$ $($ $B$ $) =$ $f$ $($ $B$ $\cup {$ $x$ $})$ であるかどうかを判定する違反テストと、(同じ入力で) B ∪ { x } の基底を見つける $基底$ $計算$ $という$ 2つの基本操作に制限される場合があります。アルゴリズムが実行するタスクは、これらの制限された評価または基本操作のみを使用して $f$ $($ $S$ $)を評価することです。$

例と応用

LP ボール

線形計画法は、最小化されるべき非負の線形目的関数とともに、 $n 個$ の線形不等式制約に従う $d 個$ の非負の実変数のシステムによって定義される。これは、制約のセットを $S$ とし、制約のサブセット $Aに対して$ $f$ $($ $A$ $)を$ $A$ によって定義されるより小さな線形計画法の最小目的関数値として定義することによって、LP型問題のフレームワークに配置できる。適切な一般位置仮定（複数の解点が同じ最適目的関数値を持つことを防ぐため）により、これは LP 型問題の単調性と局所性の要件を満たし、変数の数 $d$ に等しい組み合わせ次元を持つ。^[1]同様に、整数計画法（線形計画法と同様に線形制約の集合と線形目的関数から構成されるが、変数は整数値のみを取らなければならないという追加の制約がある）は、線形計画法と同じ一般的な位置仮定で、LP型問題の単調性と局所性の両方の特性を満たします。ベル（1977）とスカーフ（1977）の定理は、 $d$ 個の変数を持つ整数計画法の場合、組み合わせ次元は最大で $2$ $d$ であることを示しています。^[1]

計算幾何学における多くの自然な最適化問題はLP 型です。

最小円問題とは、平面上の $n$ 個の点の集合を包含する円の最小半径を求める問題である。この問題は単調性（点を追加しても円は大きくなるだけ）と局所性（集合 $Aの最小の円に$ $B$ と $x が$ 含まれる場合、同じ円に $B \cup {x$ } も含まれる）を満たしている。最小円は常に 3 つの点によって決定されるため、最小円問題は 2 次元ユークリッド幾何学を使用して定義されているにもかかわらず、組合せ次元が 3 である。^{[2]より一般的には、} $d$ 次元の点の最小の囲み球は、組合せ次元が $d + 1$ の LP 型の問題を形成する。最小円問題は、球の集合を囲む最小の球^[3]、球の集合のそれぞれに接するか囲む最小の球^[4] 、重み付き1 中心問題^[5]、または、ブレグマンダイバージェンス^[6]によって定義される距離を持つ空間などの非ユークリッド空間における同様の小さな囲み球問題に一般化できます。関連する最小の囲み楕円体を見つける問題も LP タイプの問題ですが、組み合わせ次元が $d (d + 3)/2$ と大きくなります。^[7]
$K 0 、 K 1 、... を$ $d$ 次元ユークリッド空間の $n 個の$ 凸集合の列とし、この列の共通交点を持つ最長の接頭辞を求めるとします。これは LP 型の問題として表現でき、 $f$ $($ $A$ $) = -$ $i$ となります。ここで、K _iはAの交差接頭辞に属さないAの最初のメンバーであり、そのようなメンバーが存在しない場合は $f$ $($ $A$ $) = -$ $n$ となります。このシステムの組み合わせ次元は $d$ $+ 1$ です。^[8]
3次元空間に軸が揃った長方形の箱の集合が与えられ、すべての箱を横切る正八分円空間に向かう直線を見つけたいとします。これは組み合わせ次元4のLP型問題として表現できます。^[9]
頂点の集合によって指定される 2 つの凸多面体間の最短距離を求める問題は、LP 型の問題として表現できます。この定式化では、集合 $S は$ 両方の多面体のすべての頂点の集合であり、関数値 $f (A)$ は 2 つの多面体の頂点の2 つの部分集合 $A$ の凸包間の最小距離の否定です。この問題の組み合わせ次元は、2 つの多面体が互いに素である場合は $d$ $+ 1$ 、空でない交差がある場合は $d$ $+ 2$ です。 ^[1]
$S = {f 0, f 1, ... } を$ 準凸関数の集合とする。すると、点ごとの最大値 $max i f i は$ それ自体が準凸となり、 $max i f i$ の最小値を求める問題は LP 型の問題となる。これは最大で $2 d + 1$ の組合せ次元を持つ。ここで $d$ は関数の領域の次元であるが、十分に滑らかな関数の場合、組合せ次元はより小さく、最大で $d + 1 と$ なる。他の多くの LP 型の問題も、このように準凸関数を使用して表現できる。たとえば、最小外接円問題は、関数 $f$ $i$ のそれぞれが与えられた点の 1 つからのユークリッド距離を測定する場合に $max i f i を$ ^{最小化する問題である。 [10]}

LP型問題は、アルゴリズムゲーム理論における特定のゲームの最適結果を決定したり、^[11]有限要素法メッシュの頂点配置を改善したり、 ^[12]施設配置問題を解決したり、 ^[13]特定の指数時間探索アルゴリズムの時間計算量を分析したり、^[14] 2次元画像から物体の3次元位置を再構築したりするためにも使用されてきました。^[15]

アルゴリズム

ザイデル

Seidel (1991) は、LP 型の問題フレームワークに適応できる低次元線形計画法のアルゴリズムを提示しました。Seidel のアルゴリズムは、入力として、最適基底に属することがわかっている要素の集合 $S$ と別の集合 $X$ (最初は空) を受け取ります。次に、残りの要素をランダムな順序で 1 つずつ検討し、それぞれに対して違反テストを実行し、結果に応じて、既知の基底要素のより大きな集合を使用して同じアルゴリズムを再帰的に呼び出します。これは、次の擬似コードで表現できます。

関数seidel( S , f , X ) は、 R  := 空集合
    B  := Xです。S
    のランダムな順列におけるxについて:
         f ( B ) ≠ f ( B ∪ { x } )
            の場合: B  := seidel( R , f , X ∪ { x })
         R  := R ∪ { x }
     B を返します。

$組み合わせ次元d$ の問題では、アルゴリズムの $i$ 回目の反復における違反テストは、 $x が残りの$ $d - | X |$ 基底要素の 1 つである場合にのみ失敗し、これは最大で $(d - | X |)/ i の$ 確率で発生します。この計算に基づくと、アルゴリズムによって実行される違反テストの全体的な予想数は $O(d! n)$ であり、 $nに対しては線形ですが、$ $d$ に対しては指数関数的よりも悪いことがわかります。

クラークソン

Clarkson (1995) は、ランダムサンプリング手法に基づく線形計画法に対して、再帰アルゴリズムと反復アルゴリズムという 2 つのアルゴリズムを定義し、再帰アルゴリズムから反復アルゴリズムを呼び出す 2 つの組み合わせを提案しています。再帰アルゴリズムは、入力サイズの平方根に近いサイズのランダムサンプルを繰り返し選択し、サンプリングされた問題を再帰的に解決し、違反テストを使用して、少なくとも 1 つの基本要素を含む残りの要素のサブセットを見つけます。

関数recursive( S , f )は、
    X  := 空集合
    で、繰り返し
        R  :=サイズ d√n
        のSのランダムなサブセット、 B := R ∪ X の基底、再帰的に計算される
        V  := { x | f ( B ) ≠ f ( B ∪ { x })}
         X  := X ∪ V、
    Vが空に
    なるまで、 B を返す

$各反復において、 V$ の期待サイズは $O(\sqrtn)$ であり^[16]、 $V$ が空でない場合は常に $Sの最終的な基底$ $の$ 少なくとも1つの新しい要素が含まれます。 $したがって$ 、アルゴリズムは最大で $d回の反復$ $を$ 実行し、各反復では $n回の違反テストを実行し、サイズ$ $O(d\sqrtn)$ の部分問題への1回の再帰呼び出しを行います。

$クラークソンの反復アルゴリズムは、 S$ の各要素に重みを割り当てます。最初はすべての要素が等しくなります。次に、 $S$ から $9$ $d$ $2$ 個の要素の集合 $R を$ ランダムに選択し、前のアルゴリズムと同様に集合 $B$ と $V を計算します。$ $V$ の合計重みが $S$ の合計重みの $2/(9$ $d$ $- 1)$ 倍以下である場合(一定の確率で発生します)、アルゴリズムは $V$ のすべての要素の重みを 2 倍にし、前と同様に、 $Vが空になるまでこのプロセスを繰り返します。各反復では、最適基底の重みは$ $S$ の合計重みよりも大きい割合で増加することが示され、このことから、アルゴリズムは $O(log$ $n$ $)$ 回の反復で終了する必要があることがわかります。

再帰アルゴリズムを使用して特定の問題を解決し、その再帰呼び出しを反復アルゴリズムに切り替え、反復アルゴリズムによる呼び出しを再びザイデルのアルゴリズムに切り替えることで、 $O(dn + d! d O(1) log n)$ 違反テストを使用して特定のLPタイプの問題を解決できます。

このアルゴリズムを線形計画に適用すると、双対単体法として解釈することができます。^[17]違反テストと基底計算プリミティブ以外の特定の追加計算プリミティブを使用すると、この方法を決定論的にすることができます。^[18]

マトウシェク、シャリル、ウェルツル

Matoušek、Sharir、Welzl (1996) は、他の LP タイプの問題では必ずしも保持されない、すべての基数が互いに同じ濃度を持つという線形計画法の追加特性を使用するアルゴリズムについて説明しています。LP タイプの問題にこの特性がない場合は、 $d 個$ の新しいダミー要素を追加し、関数 $f$ を変更して、古い値 $f$ $($ $A$ $)$ と数 $min($ $d$ $,|$ $A$ $|)の$ ペアを辞書式に並べたものを返すようにすることで、この特性を持たせることができます。

Matoušek、Sharir、Welzl (1996) は、 Sの要素を1 つずつ追加したり、要素のサンプルを検索したりするのではなく、要素を 1 つずつ削除するアルゴリズムを説明しています。各ステップで、最初はダミー要素のセットである基底 $C$ が維持されます。これは次の疑似コードで説明できます。

関数msw( S , f , C )は、 
    S = Cの場合 Cを返す、S \ C
    のランダムな要素 x を選択する、B = msw( S \ x , f , C )
     、 f ( B ) ≠ f(B ∪ {x})の場合B :  = basis( B ∪ { x })、
         B  := msw( S , f , B )、
     Bを返す

アルゴリズムの再帰呼び出しのほとんどでは、違反テストは成功し、if 文はスキップされます。しかし、わずかな確率で違反テストは失敗し、アルゴリズムは追加の基底計算を行い、その後追加の再帰呼び出しを行います。著者らが示すように、アルゴリズムの予想時間はnに対して線形で、 $d log n$ の平方根に対して指数関数的です。この方法を Clarkson の再帰および反復手順と組み合わせることで、これら 2 つの形式の時間依存性を互いに分離することができ、結果として、外側の再帰アルゴリズムで O( dn ) 違反テストを実行し、アルゴリズムの下位レベルでは $d log d$ の平方根に対して指数関数的な数値を実行するアルゴリズムが得られます。^[19]

バリエーション

外れ値による最適化

Matoušek (1995) は、集合 $S$ と目的関数 $f$ とともに数値 $k が$ 与えられる LP 型最適化問題のバリエーションを検討しています。タスクは、残りの集合に対する目的関数を可能な限り小さくするために、 $S$ から $k$ 個の要素を削除することです。たとえば、最小円問題に適用すると、与えられた平面点の集合のうち $k 個$ を除くすべてを含む最小の円が得られます。彼は、すべての非退化 LP 型問題 (つまり、すべての基数が個別の値を持つ問題) について、 S のサブセットによって定義された $O($ $k$ $d$ $)$ 個のLP 型問題の集合を解くことによって、この問題が $O($ $nk$ $d$ $)の$ $時間$ で解けることを示しています。

暗黙の問題

いくつかの幾何学的最適化問題は、LP 型の問題として表現されることがあります。LP 型の問題では、LP 型定式化の要素の数は、最適化問題の入力データ値の数よりも大幅に多くなります。例として、平面上の $n個の点の集合を考えます。各点は一定の速度で移動します。任意の時点で、このシステムの$ 直径は、2 つの点の間の最大距離です。直径が最小になる時間を見つける問題は、各点のペアごとに 1 つずつ、時間の関数としてペア間のユークリッド距離を測定する O(n 2) 個の準 $凸関数の点ごとの最大値を最小化する問題として定式化できます。したがって、これは O(n 2)$ 個の要素のセットで組み合わせ次元 2 の LP 型の問題として解くことができます $が、このセット$ は入力点の数よりも大幅に大きくなります。^[20]

Chan (2004) は、このような暗黙的に定義された LP タイプの問題を解くアルゴリズムについて説明しています。この問題では、各 LP タイプの要素は、ある定数 $kに対して$ $k$ 個の入力値タプルによって決定されます。彼のアプローチを適用するには、与えられた LP タイプの基底 $B$ と $n 個$ の入力値のセット $Sに対して、$ $B が$ $S$ によって決定される LP タイプの問題の基底であるかどうかを決定できる決定アルゴリズムが存在する必要があります。

Chan のアルゴリズムは次の手順を実行します。

入力値の数が何らかのしきい値を下回る場合、それが決定する LP タイプの要素のセットを見つけ、結果として生じる明示的な LP タイプの問題を解決します。
それ以外の場合は、入力値を $k$ より大きい適切な数の等しいサイズのサブセット $Siに分割します。$
$f が$ 暗黙的に定義された LP 型の問題を解くための目的関数である場合、サブセット $S$ $i$ $のコレクションをコレクションの和集合上のf$ の値にマッピングする関数 $gを定義します。次に、サブセット$ $S$ $i$ のコレクションと目的関数 $g$ 自体が、解くべき暗黙の問題と同じ次元の LP 型の問題を定義します。
$g$ によって定義された (明示的な) LP タイプの問題を、線形数の違反テストと多重対数数の基底評価を実行する Clarkson のアルゴリズムを使用して解きます。g の基底評価は $Chan$ のアルゴリズムへの再帰呼び出しによって実行され、違反テストは決定アルゴリズムへの呼び出しによって実行される場合があります。

$決定アルゴリズムには入力サイズn$ の関数として少なくとも多項式的に増加する時間 $O(T (n))がかかるという仮定のもと、Chanは、明示的なLP定式化に切り替えるしきい値とパーティション内のサブセットの数を、暗黙的なLPタイプの最適化アルゴリズムも時間$ $O($ $T$ $($ $n$ $))$ で実行されるように選択できることを示しています。

たとえば、移動する点の最小直径の場合、決定アルゴリズムは固定された時間における点の集合の直径を計算するだけでよく、この問題は回転ノギス技術を使用して $O(n log n)$ 時間で解決できます。したがって、直径が最小になる時間を見つけるための Chan のアルゴリズムも $O($ $n$ $log$ $n$ $)$ の時間がかかります。Chan はこの方法を使用して、 $d次元ユークリッド空間内の$ $n$ 個の点の集合から最大Tukey 深度の点を $O($ $n$ $d$ $- 1$ $+$ $n$ $log$ $n$ $)$ 時間で見つけます。同様の手法は、Braß、Heinrich-Litan、および Morin (2003) によって凸多角形上の一様分布の最大 Tukey 深度の点を見つけるために使用されました。

歴史と関連する問題

線形計画法のための線形時間アルゴリズムの発見と、多くの場合同じアルゴリズムが線形計画法ではない幾何最適化問題を解くのに使用できるという観察は、少なくとも Megiddo (1983、1984) にまで遡ります。Megiddo は、3 変数線形計画法と最小円問題の両方に線形期待時間アルゴリズムを与えました。しかし、Megiddo は線形計画法の一般化を、集合のシステムに関する抽象問題としてではなく凸最適化問題として、組み合わせ論的ではなく幾何学的に定式化しました。同様に、Dyer (1986) と Clarkson (Clarkson 1995 の 1988 年会議バージョン) は、彼らの方法が線形計画法だけでなく凸計画法にも適用できることを観察しました。Dyer (1992) は、最小包囲楕円体問題も、少数の非線形制約を追加することで凸最適化問題として定式化できることを示しました。低次元線形計画法および関連問題の時間境界を改善するためにランダム化を使用する方法は、Clarkson と Dyer & Frieze (1989) によって初めて導入されました。

局所性と単調性の公理を満たす関数による LP 型問題の定義は Sharir & Welzl (1992) によるものですが、同時期に他の著者らも線形計画の別の組合せ論的一般化を定式化しました。たとえば、Gärtner (1995) が開発したフレームワークでは、関数 $f は$ $S$ のサブセット上の全順序付けに置き換えられています。LP 型問題で同点を解消して全順序付けを作成することは可能ですが、組合せ次元の増加を犠牲にする必要があります。^[21] さらに、LP 型問題と同様に、Gärtner は要素のサブセットで計算を実行するための特定のプリミティブを定義していますが、彼の形式化には組合せ次元の類似物がありません。

Stickney & Watson (1978) によって定式化され、後に他の数人の著者によって研究された、線型計画問題と線型相補性問題のもう 1 つの抽象的な一般化は、ハイパーキューブのすべての面 (ハイパーキューブ全体を面として含む) が一意のシンク(出力エッジのない頂点) を持つという特性を持つハイパーキューブのエッジの向きに関するものです。このタイプの向きは、LP タイプの問題から、Sの部分集合をハイパーキューブの頂点と対応させ、対応する頂点が隣接している場合にのみ 2 つの部分集合が 1 つの要素だけ異なるようにし、隣接する集合 $A \subseteq Bの間のエッジを、$ $f$ $($ $A$ $) \neq$ $f$ $($ $B$ $)$ の場合は $B$ の方に、それ以外の場合は $A$ の方に向けることによって形成されます。結果として得られる方向は、有向非巡回グラフを形成するという追加の特性を持ち、これにより、ランダム化アルゴリズムは、 $n$ の平方根の指数関数的なステップ数でハイパーキューブ全体の一意のシンク（LP型問題の最適基底）を見つけることができることが示される。^[22]

最近開発された違反空間のフレームワークは、LP 型の問題を一般化します。つまり、すべての LP 型の問題は違反空間でモデル化できますが、その逆は必ずしも当てはまりません。違反空間は、LP 型の問題と同様に、集合を目的関数の値にマッピングする関数 $fによって定義されますが、$ $f$ の値は順序付けられていません。順序付けがないにもかかわらず、すべての集合 $S$ には、LP 型の問題に対する Clarkson のアルゴリズムのバリエーションによって見つけることができる、明確に定義された基底集合 (集合全体と同じ値を持つ最小集合) があります。実際、違反空間は、Clarkson のアルゴリズムで解決できるシステムを正確に特徴付けることが示されています。^[23]

注記

^ abc マトウシェク、シャリール、ヴェルツル (1996)。
^ 最小円問題は、Matoušek、Sharir、Welzl (1996) によって初めて LP 型の問題であると述べられましたが、Megiddo (1983) や Welzl (1991) など、低次元線形計画法のアイデアに基づいてこの問題のアルゴリズムを説明する論文がいくつか以前にありました。
^ フィッシャー＆ガートナー（2004年）。
^ ロフラーとヴァン・クレフェルト (2010)。
^ ダイアー（1986年）。
^ ニールセン＆ノック（2008年）。
^ マトウシェク、シャリール、ヴェルツル (1996);ヴェルツル (1991)。
^ チャン（2004年）。
^ アメンタ（1994年）。
^ アメンタ、ベルン、エップスタイン (1999);エップスタイン (2005)。
^ ハルマン（2007年）。
^ アメンタ、ベルン、エップスタイン (1999)。
^ プエルト、ロドリゲス＝チア、タミル (2010)。
^ エップスタイン（2006年）。
^ 李（2007年）。
^ $V$ のサイズの末尾の境界も知られています。Gärtner & Welzl (2001) を参照してください。
^ カライ（1992年）。
^ チャゼルとマトウシェク (1996)。
^ Matoušek、Sharir、Welzl (1996)。線形計画法の非常によく似た時間制限は、Kalai (1992) によっても与えられています。
^ この問題の LP 型定式化は Chan (2004) によって提示されましたが、それ以前には Gupta、Janardan、Smid (1996) によって他のアルゴリズム手法を使用して研究されていました。Chan はまた、暗黙的な LP 型アプローチで達成できる時間と一致する $O(n log n)$ 時間アルゴリズムに関する Clarkson の未発表の原稿を引用しています。
^ マトウシェク（2009年）。
^ サボー＆ウェルツル（2001）。
^ ガートナーら。 (2008);ブリーゼとガートナー (2011)。

参考文献

アメンタ、ニーナ(1994)、「ヘリー型定理と一般化線形計画法」(PDF)、離散および計算幾何学、12 (3): 241–261、doi : 10.1007/BF02574379、MR 1298910、S2CID 26667725。
アメンタ、ニーナ; バーン、マーシャル;エップスタイン、デイビッド(1999)、「メッシュスムージングのための最適なポイント配置」、アルゴリズムジャーナル、 30 ( 2): 302–322 、arXiv : cs.CG/9809081、doi:10.1006/jagm.1998.0984、MR 1671836 、S2CID 182728。
Bell, David E. (1977)、「整数格子に関する定理」(PDF)、応用数学研究、56 (2): 187–188、doi :10.1002/sapm1977562187、MR 0462617。
Braß, Peter; Heinrich-Litan, Laura; Morin, Pat (2003)、「凸多角形の面積の中心の計算」(PDF)、International Journal of Computational Geometry & Applications、13 (5): 439–445、doi :10.1142/S021819590300127X、MR 2012837。
Brise, Yves; Gärtner, Bernd (2011)、「違反空間に対するクラークソンのアルゴリズム」(PDF)、計算幾何学: 理論と応用、44 (2): 70–81、arXiv : 0906.4706、doi :10.1016/j.comgeo.2010.09.003、MR 2737285、S2CID 1233875。
Chan, Timothy M. (2004)、「最大 Tukey 深度のための最適なランダム化アルゴリズム」(PDF)、Proc. 15th ACM-SIAM Symp. Discrete Algorithms、pp. 423–429。
Chazelle, Bernard ; Matoušek, Jiří (1996)、「固定次元の最適化問題に対する線形時間決定論的アルゴリズムについて」(PDF)、Journal of Algorithms、21 (3): 579–597、doi :10.1006/jagm.1996.0060、MR 1417665、S2CID 2482481。
クラークソン、ケネス L. (1995)、「次元が小さい場合の線形および整数計画法のためのラスベガスアルゴリズム」(PDF)、Journal of the ACM、42 (2): 488–499、doi :10.1145/201019.201036、MR 1409744、S2CID 6953625。
ダイアー、マーティン E. (1986)、「多次元探索技術とユークリッド一中心問題へのその応用について」、SIAM Journal on Computing、15 (3): 725–738、doi :10.1137/0215052、MR 0850419。
Dyer, Martin E. (1992)、「凸プログラムのクラスと計算幾何学への応用」、Proc. 8th Symposium on Computational Geometry (SCG '92)、ベルリン、ドイツ、pp. 9–15、doi :10.1145/142675.142681、ISBN 0-89791-517-8、S2CID 7654513{{citation}}: CS1 メンテナンス: 場所が見つかりません発行者 (リンク)。
ダイアー、マーティン E.;フリーズ、アラン M. (1989)、「固定次元線形計画法のランダム化アルゴリズム」、数学プログラミング、(Ser. A)、44 (2): 203–212、doi :10.1007/BF01587088、MR 1003560、S2CID 206800147。
Eppstein, David (2005)、「Quasiconvex programming」、Goodman, Jacob E.、Pach, János、Welzl, Emo (編)、『Combinatorial and Computational Geometry』 、MSRI Publications、vol. 52、Cambridge Univ . Press、pp. 287–331、arXiv : cs.CG/0412046、MR 2178325。
エップスタイン、デイビッド（2006）、「バックトラッキングアルゴリズムのための多変量再帰方程式の準凸解析」、ACM Transactions on Algorithms、2（4）：492–509、arXiv：cs.DS / 0304018、doi：10.1145 / 1198513.1198515、MR 2284242、S2CID 9980061。
Fischer, Kaspar; Gärtner, Bernd (2004)、「ボールの最小の囲みボール: 組み合わせ構造とアルゴリズム」(PDF)、International Journal of Computational Geometry & Applications、14 (4–5): 341–378、doi :10.1142/S0218195904001500、MR 2087827。
Gärtner, Bernd (1995)、「抽象最適化問題に対する準指数アルゴリズム」(PDF)、SIAM Journal on Computing、24 (5): 1018–1035、doi :10.1137/S0097539793250287、MR 1350756。
ガートナー、ベルント; Matoušek, イジー;ラスト、L. Škovroň, P. (2008)、「違反者空間: 構造とアルゴリズム」、離散応用数学、156 (11): 2124–2141、arXiv : cs.DM/0606087、doi :10.1016/j.dam.2007.08.048、氏 2437006。
Gärtner, Bernd; Welzl, Emo (2001)、「単純なサンプリング補題: 幾何最適化における解析と応用」(PDF)、離散および計算幾何学、25 (4): 569–590、doi : 10.1007/s00454-001-0006-2、MR 1838420、S2CID 14263014。
Gupta, Prosenjit; Janardan, Ravi; Smid, Michiel (1996)、「移動する幾何学的オブジェクトに関する衝突および近接問題に対する高速アルゴリズム」、計算幾何学。理論と応用、6 (6): 371–391、doi :10.1016/0925-7721(95)00028-3、hdl : 11858/00-001M-0000-0014-B50E-D、MR 1415267。
Halman, Nir (2007)、「単純確率ゲーム、パリティゲーム、平均ペイオフゲーム、割引ペイオフゲームはすべて LP 型の問題である」、Algorithmica、49 (1): 37–50、doi :10.1007/s00453-007-0175-3、MR 2344393、S2CID 8183965。
Kalai, Gil (1992)、「準指数ランダム化シンプレックスアルゴリズム」、Proc. 24th ACM Symposium on Theory of Computing、pp. 475–482、doi :10.1145/129712.129759、S2CID 17447465。
$Li, Hongdong (2007)、「外れ値のあるL \infty$ 三角測量の実用的なアルゴリズム」、Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR '07)、pp. 1–8、doi :10.1109/CVPR.2007.383068、hdl : 1885/39190、ISBN 978-1-4244-1179-5、S2CID 14882916。
Löffler, Maarten; van Kreveld, Marc (2010)、「最大境界ボックス、最小直径、および不正確な点に関する関連問題」(PDF)、計算幾何学理論と応用、43 (4): 419–433、doi :10.1016/j.comgeo.2009.03.007、MR 2575803。
Matoušek, Jiří (1995)、「制約違反の少ない幾何最適化について」、離散および計算幾何学、14 (4): 365–384、doi : 10.1007/BF02570713、MR 1360943。
Matoušek, Jiří (2009)、「LP 型問題における退化の除去の再考」、離散および計算幾何学、42 (4): 517–526、doi : 10.1007/s00454-008-9085-7、hdl : 20.500.11850/156948、MR 2556452。
Matoušek, イジー;シャリル, ミシャ; Welzl、Emo (1996)、「線形計画法のサブ指数関数境界」(PDF)、Algorithmica、16 (4–5): 498–516、doi :10.1007/BF01940877、S2CID 877032。
Megiddo, Nimrod (1983)、「 $R 3$ における線形計画法および関連問題のための線形時間アルゴリズム」、SIAM Journal on Computing、12 (4): 759–776、doi :10.1137/0212052、MR 0721011、S2CID 14467740。
Megiddo, Nimrod (1984)、「次元が固定されている場合の線形時間での線形計画法」、Journal of the ACM、31 (1): 114–127、doi : 10.1145/2422.322418、MR 0821388、S2CID 12686747。
ニールセン、フランク、ノック、リチャード (2008)、「最小の囲み情報ディスクについて」(PDF)、情報処理レター、105 (3): 93–97、doi :10.1016/j.ipl.2007.08.007、MR 2378119、S2CID 7570507。
Puerto, J.; Rodríguez-Chía, AM; Tamir, A. (2010)、「平面区分的二次 1 中心問題について」、Algorithmica、57 (2): 252–283、doi :10.1007/s00453-008-9210-2、MR 2587554、S2CID 18587944。
スカーフ、ハーバート E. (1977)、「不可分性を持つ生成集合の構造に関する考察」、米国科学アカデミー紀要、74 (9): 3637–3641、Bibcode :1977PNAS...74.3637S、doi : 10.1073/pnas.74.9.3637、MR 0452678、PMC 431672、PMID 16592435。
Seidel, Raimund (1991)、「小次元線形計画法と凸包の簡単な作成」、離散および計算幾何学、6 (5): 423–434、doi : 10.1007/BF02574699、MR 1115100。
Sharir, Micha ; Welzl, Emo (1992)、「線形計画法と関連問題の組み合わせ限界」、Stacs 92、Lecture Notes in Computer Science、vol. 577、Springer-Verlag、pp. 567–579、doi :10.1007/3-540-55210-3_213、ISBN 978-3-540-55210-9。
スティックニー、アラン; ワトソン、レイン (1978)、「線形相補性問題に対するバード型アルゴリズムの有向グラフモデル」、オペレーションズリサーチ数学、3 (4): 322–333、doi :10.1287/moor.3.4.322、MR 0509668。
Szabó, Tibor; Welzl, Emo (2001)、「立方体の一意のシンクの向き」(PDF)、第 42 回 IEEEコンピュータサイエンスの基礎に関するシンポジウム(ネバダ州ラスベガス、2001 年)、pp. 547–555、doi :10.1109/SFCS.2001.959931、ISBN 0-7695-1390-5、MR 1948744、S2CID 6597643。
Welzl, Emo (1991)、「最小の囲み円盤 (球と楕円体)」、Maurer, H. (編)、『コンピュータサイエンスにおける新しい成果と新しい動向』(PDF)、コンピュータサイエンスの講義ノート、第 555 巻 (555 版)、Springer-Verlag、pp. 359–370、doi :10.1007/BFb0038202、ISBN 3-540-54869-6。

[msw96-1] マトウシェク、シャリール、ヴェルツル (1996)。

[2] 最小円問題は、Matoušek、Sharir、Welzl (1996) によって初めて LP 型の問題であると述べられましたが、Megiddo (1983) や Welzl (1991) など、低次元線形計画法のアイデアに基づいてこの問題のアルゴリズムを説明する論文がいくつか以前にありました。

[3] フィッシャー＆ガートナー（2004年）。

[4] ロフラーとヴァン・クレフェルト (2010)。

[5] ダイアー（1986年）。

[6] ニールセン＆ノック（2008年）。

[7] マトウシェク、シャリール、ヴェルツル (1996);ヴェルツル (1991)。

[8] チャン（2004年）。

[9] アメンタ（1994年）。

[10] アメンタ、ベルン、エップスタイン (1999);エップスタイン (2005)。

[11] ハルマン（2007年）。

[12] アメンタ、ベルン、エップスタイン (1999)。

[13] プエルト、ロドリゲス＝チア、タミル (2010)。

[14] エップスタイン（2006年）。

[15] 李（2007年）。

[16] $V$ のサイズの末尾の境界も知られています。Gärtner & Welzl (2001) を参照してください。

[17] カライ（1992年）。

[18] チャゼルとマトウシェク (1996)。

[19] Matoušek、Sharir、Welzl (1996)。線形計画法の非常によく似た時間制限は、Kalai (1992) によっても与えられています。

[20] この問題の LP 型定式化は Chan (2004) によって提示されましたが、それ以前には Gupta、Janardan、Smid (1996) によって他のアルゴリズム手法を使用して研究されていました。Chan はまた、暗黙的な LP 型アプローチで達成できる時間と一致する $O(n log n)$ 時間アルゴリズムに関する Clarkson の未発表の原稿を引用しています。

[21] マトウシェク（2009年）。

[22] サボー＆ウェルツル（2001）。

[23] ガートナーら。 (2008);ブリーゼとガートナー (2011)。