Ресинхронизация схемы: различия между версиями

Поскольку в ограничения входят только разностные неравенства с целочисленными константными термами, решение ослабленной линейной программы (без целочисленных ограничений) даст только целочисленные решения. И более того, можно показать, что эта задача является двойственной к задаче нахождения потока с минимальной стоимостью в сети и, таким образом, имеет эффективное решение.

'''Теорема 1. Целочисленная линейная программа для задачи ресинхронизации с минимальной площадью является двойственной к следующей задаче нахождения потока с минимальной стоимостью в сети:'''

<math>in[v] + \sum_{(v, w) \in E \vee D[u, v] > \phi} f[v, w] = out[v] + \sum_{(u, v) \in E \; \; D[u, v] > \phi} f[u, v] \; \; \forall v \in V</math>

Для построения потока в сети с минимальной стоимостью необходимо вначале вычислить обе матрицы, W и D. Поскольку W[u, v] – кратчайший путь из u в v относительно w, вычисление W можно выполнить при помощи алгоритма нахождения кратчайших путей между всеми парами – например, алгоритма Флойда-Уоршелла [1]. Далее, если упорядоченная пара (w[x, y], - d[x]) используется в качестве веса ребра для каждой пары <math>(x, y) \in E \;</math>, алгоритм нахождения кратчайших путей между всеми парами можно также использовать для вычисления W и D. Алгоритм будет присваивать веса при помощи покомпонентного сложения и затем сравнивать их посредством лексикографической сортировки.