For Ultrametric Violation
Distance, the reduction from Multicut still holds, implying that it seems unlikely to have an \(O(1)\) -approximation for weighted graphs. However, we adapt the algorithm of Ailon and Charikar [1]} to design an \(O(\log n \log \log n)\) -approximation algorithm even for weighted instances.

Для нарушения ультраметрического расстояния редукция от Мультикат все еще остается, что означает, что маловероятно иметь \(O(1)\)-аппроксимацию для взвешенных графов. Однако мы адаптировали алгоритм Айлона и Чарикара [1] для разработки \(O(\log n \log \log n)\)-аппроксимационного алгоритма даже для взвешенных случаев.