Компоновка схемы: различия между версиями

Качество компоновки при помощи квадратичных алгоритмов может оказаться невысоким. Для аппроксимации линейной целевой функции можно итеративно решить уравнение (1), вычисляя <math>w_{ij} = \frac{1}{|x_i - x_j|} \;</math> на каждой итерации. Другим вариантом может быть решение единичной <math>\beta \;</math>-регуляризованной задачи оптимизации, заданной формулой <math>\Phi(\mathbf{x}) = min_x \sum_{i,j} w_{ij} \sqrt{(x_i - x_j)^2 + \beta} , \beta > 0 \;</math> - например, с использованием прямо-двойственного метода Ньютона с квадратичной сходимостью [1].

Функция HPWL может быть доказуемо аппроксимирована строго выпуклыми и дифференцируемыми функциями. Для 2-точечных гиперребер можно применять <math>\beta \;</math>-регуляризацию [1]. Для m-точечного гиперребра (при <math>m \ge 3 \;</math>) можно переформулировать HPWL в виде максимума (по норме <math>l_{\infty} \;</math>) среди всех m(m — 1)/2 попарных расстояний <math>|x_i - x_j| \;</math> и аппроксимировать <math>l_{\infty} \;</math>-норму <math>l_p \;</math>-нормой (p-м корнем из суммы p-х степеней). Это позволяет устранить недифференцируемость при всех значениях, кроме '''0''', что впоследствии убирается при помощи <math>\beta \;</math>-регуляризации. Полученная аппроксимация HPWL задается формулой

(2) <math>HPWL_{p - \beta - reg} (G_h) = \sum_{e_k \in E_h} \bigg( \sum_{i,j \in C_k} |x_i - x_j|^p + \beta \bigg)^{1/p} \;</math>.

которое оценивает сверху функцию HPWL с произвольно малой относительной ошибкой, так как <math>p \to \infty \;</math> и <math>\beta \to 0 \;</math> [7]. Кроме того, HPWL также можно аппроксимировать при помощи функции, задаваемой формулой