4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
Строка 75: | Строка 75: | ||
Основным техническим вкладом модели MTS является разработка алгоритма рабочей функции, используемого для доказательства верхней границы в теореме 1. Кутсупиас и Пападимитриу впоследствии проанализировали этот алгоритм в контексте k-серверной задачи и показали, что он является 2k-1-конкурентным. Кроме того, хотя модель MTS служит обобщением k-серверной задачи, общая задача MTS на n-точечной метрике по существу эквивалентна (n - 1)-серверной задаче на той же метрике [2]. Следовательно, из нижних границ коэффициента конкурентоспособности общей задачи MTS можно получить нижние границы для k-серверной задачи, а алгоритмы решения общей задачи MTS могут стать первым шагом к разработке алгоритма для решения k-серверной задачи, как и в случае с алгоритмом рабочей функции. | Основным техническим вкладом модели MTS является разработка алгоритма рабочей функции, используемого для доказательства верхней границы в теореме 1. Кутсупиас и Пападимитриу впоследствии проанализировали этот алгоритм в контексте k-серверной задачи и показали, что он является (2k - 1)-конкурентным. Кроме того, хотя модель MTS служит обобщением k-серверной задачи, общая задача MTS на n-точечной метрике по существу эквивалентна (n - 1)-серверной задаче на той же метрике [2]. Следовательно, из нижних границ коэффициента конкурентоспособности общей задачи MTS можно получить нижние границы для k-серверной задачи, а алгоритмы решения общей задачи MTS могут стать первым шагом к разработке алгоритма для решения k-серверной задачи, как и в случае с алгоритмом рабочей функции. | ||
правка