LP-type problem とは

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