4430
правок
Аппроксимация метрических пространств древесными метриками: различия между версиями
Материал из WEGA
Аппроксимация метрических пространств древесными метриками (посмотреть исходный код)
Версия от 22:10, 31 октября 2016
, 31 октября 2016→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 56: | Строка 56: | ||
== Применение == | == Применение == | ||
Аппроксимация метрики случайными деревьями находит применение в оперативных и распределенных вычислениях, поскольку рандомизация хорошо справляется с рассеянными объектами, а деревья легко поддерживать и обрабатывать. Алон и др. [ ] первыми использовали встраивание деревьев для получения конкурентного алгоритма решения k-серверной задачи. Бартал [ ] в своей статье отметил несколько возможных направлений: система метрических задач, распределенная подкачка, распределенная k-серверная задача, распределенная система обслуживания очередей, работа с мобильным пользователем. | |||
После статьи Бартала в 1996 году было найдено множество применений алгоритмов аппроксимации. Многие из них позволяют решать задачи на древесных метриках или HST-метриках. Аппроксимируя метрики общего вида при помощи этих метрик, можно превратить их в алгоритмы для метрик общего вида, как правило, с потерей только члена O(log n) в коэффициенте аппроксимации. Среди примеров подобного подхода можно упомянуть разметку при помощи метрики, построение сетей с применением «оптового» подхода и группировку деревьев Штейнера. Среди новых областей применения стоит отметить алгоритм аппроксимации для Unique Games [12], проектирование информационных сетей [13] и сетей с рассеянной маршрутизацией [11]. | |||
Статья в SIGACT News [ ] представляет обзор метрической аппроксимации при помощи древесных метрик и более детальное обсуждение построения алгоритмов и техник. См. другие примеры применения в [3, 9]. | |||
== Открытые вопросы == | |||
Если имеется метрика, порожденная графом, то некоторым практическим приложениям (таким как решение определенного класса линейных систем) требуется не просто древесная метрика, а древесная метрика, порожденная остовным деревом графа. Элкин, Эмек, Спилмен и Тенг [7] предложили алгоритм поиска остовного дерева со средней невязкой O(log n log log n). Остается открытым вопрос, является ли эта граница точной. | |||
== См. также == | |||
* [[Системы метрических задач]] | |||
* [[Разреженные остовы графов]] | |||
== Литература == | |||
1. Alon, N., Karp, R.M., Peleg, D., West, D.: A graph-theoretic game and its application to the k-server problem. SIAM J. Comput. 24,78-100(1995) | |||
2. Bartal, Y.: Probabilistic approximation of metric spaces and its algorithmic applications. In: FOCS '96: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, Washington, DC, USA, IEEE Computer Society, pp. 184-193(1996) | |||
3. Bartal, Y.: On approximating arbitrary metrices by tree metrics. In: STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 161-168. ACM Press, New York (1998) | |||
4. Bartal, Y., Charikar, M., Raz, D.: Approximating min-sum k-clustering in metric spaces. In:STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing, pp. 11-20. ACM Press, New York (2001) | |||
5. Calinescu, G., Karloff, H., Rabani, Y.: Approximation algorithms for the 0-extension problem. In: SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics, pp. 8-16. (2001) | |||
6. Charikar, M., Chekuri, C., Goel, A., Guha, S.: Rounding via trees: deterministic approximation algorithms for group steiner trees and k-median. In: STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 114-123. ACM Press, New York (1998) | |||
7. Elkin, M., Emek, Y., Spielman, D.A., Teng, S.-H.: Lower-stretch spanning trees. In: STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pp. 494-503. ACM Press, New York (2005) | |||
8. Fakcharoenphol, J., Rao, S., Talwar, K.: Approximating metrics by tree metrics. SIGACT News 35,60-70 (2004) | |||
9. Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69,485-497 (2004) | |||
10. Gupta, A.: Steiner points in tree metrics don't (really) help. In: SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics, pp. 220-227. (2001) | |||
11. Gupta, A., Hajiaghayi, M.T., Racke, H.: Oblivious network design. In: SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 970-979. | |||
ACM Press, New York (2006) | |||
12. Gupta, A., Talwar, K.: Approximating unique games. In: SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, New York, NY, USA, pp. 99-106. ACM Press, New York (2006) | |||
13. Hayrapetyan, A., Swamy, C., Tardos, Ё.: Network design for information networks. In: SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics, pp. 933-942. (2005) | |||
14. Indyk, P., Matousek, J.: Low-distortion embeddings of finite metric spaces. In: Goodman, J.E., O'Rourke, J. (eds.) Handbook of Discrete and Computational Geometry. CRC Press, Inc., Chap. 8 (2004), To appear | |||
15. Karp, R.: A 2k-competitive algorithm for the circle. Manuscript (1989) | |||
16. Matousek, J.: Lectures on Discrete Geometry. Springer, New York (2002) | |||
17. Rabinovich, Y., Raz, R.: Lower bounds on the distortion of embedding finite metric spaces in graphs. Discret. Comput. Geom. 19, 79-94(1998) | |||
18. Seymour, P.D.: Packing directed circuits fractionally. Combinatorica 15, 281-288 (1995) | |||
