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

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

Хотелось бы усилить формулировку теоремы 5 и получить детерминированный онлайн-алгоритм с полиномиальным временем выполнения, коэффициент конкурентоспособности которого для любого экземпляра задачи MTS на любом n-точечном метрическом пространстве не более чем в poly-log(n) превышает детерминированный коэффициент конкурентоспособности для этого экземпляра.