Системы метрических задач: различия между версиями

Компонент аппроксимации метрики, упоминающийся в доказательстве теоремы 4, называется ''подмножествами Рамсея''. Первыми в этом контексте его использовали Карлофф, Рабани и Равид, впоследствии результат улучшили Блюм, Карлофф, Рабани и Сакс, а также Бартал, Боллобас и Мендель [2]. Строгий результат для подмножеств Рамсея доказали Бартал, Линиал, Мендель и Наор. Более простое (и строгое) доказательство можно найти в работе [12].

Нижняя граница <math>\Omega (log \; n /log \; log \; n)</math> коэффициента конкурентоспособности любого рандомизированного алгоритма решения общей задачи MTS на n-точечной ультраметрике была доказана в [2], улучшив тем самым предыдущие результаты Карлоффа, Рабани и Равида, а также Блюма, Карлоффа, Рабани и Сакса.

Теорема 5 [6]. Задача определения коэффициента конкурентоспособности для данного экземпляра задачи <math>MTS ((X, d_X), a_0 \in X, T) \;</math> является [[PSPACE-hard problem|PSPACE-трудной]], даже если метрика <math>d_X \;</math> является униформной. С другой стороны, если метрика dX является униформной, существует детерминированный онлайн-алгоритм с полиномиальным временем выполнения для решения задачи math>MTS((X, d_X), a_0 \in X, T) \;</math>, коэффициент конкурентоспособности которого в O(log |X|) раз превышает детерминированный коэффициент конкурентоспособности алгоритма для <math>MTS((X, d_X), a_0, T) \;</math>. Предполагается, что экземпляр <math>((X, d_X), a_0, T) \;</math> задан явным образом.