De RosaとKhajaviradは、K-平均クラスタリングのための新しい多項式サイズの線形プログラミング（LP）緩和を導入しました（2022）。この論文では、この緩和の理論的および計算的特性をさらに調査します。合成データセットおよび実データセットに関する数値実験から明らかなように、提案されたLP緩和はほぼ常にタイトであり、つまり、その最適解は元の非凸問題に対して実行可能です。この予期せぬ挙動をよりよく理解するために、理論的側面において、2つのクラスタを持つK-平均クラスタリングに焦点を当て、与えられたデータの分割がLP緩和の最適解であるための十分条件を得ます。さらに、入力が人気のある確率モデルに従って生成される際の十分条件を分析し、LPの回復保証を得ます。LP緩和が決してタイトでない入力のファミリーを構築することで、理論的研究を締めくくります。クラスタリングされるデータポイントの数をnとすると、LP緩和は数式：テキストを参照してください不等式を含み、大規模データセットには実用的でありません。このスケーラビリティの問題に対処するために、PDLPのGPU実装と共にカッティングプレーンアルゴリズムを用いて、提案されたLPを解決する効率的なアルゴリズムを開発し、したがって最大で数式：テキストを参照してくださいデータポイントのK-平均クラスタリング問題を解決します。資金：著者は、空軍科学研究局Grant FA9550-23-1-0123により部分的に資金提供を受けました。
Rosaら（火曜日）がこの問題を研究しました。