Besides the improved approximation ratio, the strength of our algorithm is its simplicity. Note that the \(O(n^3)\)  complexity is actually not cubic since the input has size \(\Omega (n^2)\) . Furthermore, since in particular the algorithm can be used to verify whether the input data is already a metric (deciding whether the objective is 0 or not), the \(O(n^3)\)  complexity is tight by a result of Williams and Williams [1]} (assuming a standard fine-grained complexity conjecture).

Помимо улучшенной оценочной пропорции, сильной стороной нашего алгоритма является его простота. Обратите внимание, что сложность \(O(n^3)\) на самом деле не является кубической, поскольку входной размер составляет \(\Omega(n^2)\). Кроме того, поскольку алгоритм может использоваться в частности для проверки, являются ли входные данные уже метрикой (принятие решения, является ли цель нулевой или нет), сложность \(O(n^3)\) является оптимальной в соответствии с результатом Уильямса и Уильямса [1] (при условии стандартной гипотезы о сложности с гранулированием).