Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях: различия между версиями

'''Теорема. Алгоритм RCL представляет собой алгоритм Kc(q)/I-аппроксимации для маршрутизации и распределения каналов в задаче планирования ребер в отсутствие интерференции.'''

Доказательство. Заметим, что поток f(e(i)), возвращаемый алгоритмом распределения каналов в разделе «Распределение каналов», удовлетворяет ограничению нагруженности линий связи. Таким образом, из результата, полученного в разделе «Планирование потока управления линий связи», следует, что в результате масштабирования потока с дополнительным коэффициентом 1/c(q) можно сформировать его план, свободный от интерференции. В результате получаем допустимое решение объединенной задачи маршрутизации, распределения каналов и планирования со значением <math>\lambda \;</math>, равным по меньшей мере <math>\lambda^* / \phi c(q) \;</math>. Таким образом, алгоритм RCL представляет собой алгоритм <math>\phi c(q) = Kc(q)/I \;</math> -аппроксимации. □