4446
правок
Системы метрических задач: различия между версиями
Материал из WEGA
→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 81: | Строка 81: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
По-прежнему сохраняется очевидный разрыв между верхней и нижней границами рандомизированного коэффициента конкурентоспособности общей задачи MTS над конечной метрикой общего вида. Известно, что, в отличие от детерминированного случая, рандомизированный коэффициент конкурентоспособности не является константным над всеми метрическими пространствами того же размера. Однако в случаях, когда известны точные границы, коэффициент конкурентоспособности равен @(log n). Из этого можно сделать очевидный вывод, что для любой n-точечной метрики рандомизированный коэффициент конкурентоспособности равен @(log n). Вероятно, самыми простыми классами метрических пространств, для которых неизвестна верхняя граница рандомизированного коэффициента конкурентоспособности лучше O(log и), являются пути и циклы. | |||
Кроме того, не хватает «средней теории» для задачи MTS. С одной стороны, общая задача MTS достаточно хорошо изучена. С другой же стороны, такие специализированные задачи MTS, как обновление списков, детерминированные k-серверные алгоритмы и детерминированное взвешенное кэширование, также хорошо изучены и имеют намного лучшие коэффициенты конкурентоспособности по сравнению с соответствующей общей задачей. На данный момент недостает «промежуточных» моделей MTS, которые могли бы объяснить низкие коэффициенты конкурентоспособности для некоторых конкретных онлайн-задач, упомянутых выше. | |||
Хотелось бы усилить формулировку теоремы 5 и получить детерминированный онлайн-алгоритм с полиномиальным временем выполнения, коэффициент конкурентоспособности которого для любого экземпляра задачи MTS на любом n-точечном метрическом пространстве не более чем в poly-log(n) превышает детерминированный коэффициент конкурентоспособности для этого экземпляра. | |||
== См. также == | |||
* [[Алгоритм DC-дерева для k серверов на деревьях]] | |||
* [[Аппроксимация метрических пространств древесными метриками]] | |||
* [[Онлайн-алгоритм обновления списков]] | |||
* [[Онлайн-алгоритм подкачки и кэширования]] | |||
* [[Подкачка страниц]] | |||
* [[Задача об аренде лыж]] | |||
* [[Алгоритм рабочей функции для k серверов]] | |||
== Литература == | |||
1. Bartal, Y., Blum, A., Burch, C., Tomkins, A.: A polylog()-competitive algorithm for metrical task systems. In: Proceedings of the 29th annual ACM Symposium on the Theory of Computing, pp. 711-719. ACM, New York (1997) | |||
2. Bartal, Y., Bollobas, B., Mendel, M.: Ramsey-type theorems for metric spaces with applications to online problems. J. Comput. Syst.Sci. 72,890-921 (2006) | |||
3. Bartal, Y., Mendel, M.: Multiembedding of metric spaces. SIAM J. Comput. 34, 248-259 (2004) | |||
4. Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University Press, Cambridge, UK (1998) | |||
5. Borodin, A., Linial, N., Saks, M.E.: An optimal on-line algorithm for metrical task system. J. ACM 39, 745-763 (1992) | |||
6. Burley, W.R., Irani, S.: On algorithm design for metrical task systems. Algorithmica 18,461^85 (1997) | |||
7. Chrobak, M., Larmore, L.L.: Metrical task systems, the server problem and the work function algorithm. In: Fiat, A., Woeginger, G J. (eds.) Online Algorithms. The State of the Art. LNCS, vol. 1442, ch.4, pp. 74-96. Springer, London (1998) | |||
8. Fakcharoenphol, J., Rao, S.,Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69,485-497(2004) | |||
9. Fiat, A., Mendel, M.: Better algorithms for unfair metrical task systems and applications. SIAM J. Comput. 32, 1403-1422 (2003) | |||
10. Irani, S., Seiden, S.S.: Randomized algorithms for metrical task systems. Theor. Comput. Sci. 194,163-182 (1998) | |||
11. Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for server problems. J. Algorithms 11,208-230 (1990) | |||
12. Mendel, M., Naor, A.: Ramsey partitions and proximity data structures. J. Eur. Math. Soc. 9(2), 253-275 (2007) | |||
