4551
правка
Жадные алгоритмы покрытия множества: различия между версиями
Перейти к навигации
Перейти к поиску
Жадные алгоритмы покрытия множества (посмотреть исходный код)
Версия от 10:03, 6 апреля 2018
, 6 апреля 2018→Другие результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 48: | Строка 48: | ||
== Другие результаты == | == Другие результаты == | ||
Было показано, что коэффициент аппроксимации жадного алгоритма составляет ln n — ln ln n + O(1) [12]. Для специального случая систем множеств, дополнения которых имеют конечную размерность Вапника — Червоненкиса (VC-размерность), другие алгоритмы демонстрируют заметно лучший коэффициент аппроксимации [ ]. Известны алгоритмы аппроксимации с постоянным коэффициентом для тесно связанных с ними геометрических вариантов таких задач, как метод k-медиан и задача о размещении объектов. | |||
Жадный алгоритм можно естественным образом обобщить на множество задач. Например, для определенной выше задачи минимизации линейной функции относительно субмодулярных ограничений естественное расширение жадного алгоритма дает решение с Hk-аппроксимацией, где k = maxs2Sf(fsg) — f(;), в предположении, что f является целочисленной функцией[10]. | |||
Обобщая задачу о покрытии множества, можно потребовать, чтобы каждый элемент x содержался в произвольном числе множеств rx; только в этом случае он будет считаться элементом покрытия. Для этого обобщения существует алгоритм O(log n)-аппроксимации с полиномиальным временем выполнения [8]. | |||
Для специального случая, когда каждый элемент принадлежит не более чем к r множествам, имеется более простой алгоритм r-аппроксимации ([15] § 15.2). Если множества имеют однородные веса (ws = 1), алгоритм сводится к следующему: выбрать любой максимальный набор элементов, никакие два из которых не содержатся в одном множестве; вернуть все множества, содержащие выбранный элемент. | |||
В варианте «Максимальное k-покрытие» требуется, чтобы набор множеств, суммарный вес которых не превышает k, покрывал максимально возможное количество элементов. Для этого варианта существует алгоритм (1 — 1/e)-аппроксимации ([15], задача 2.18) (см. [7] для варианта множеств с неоднородными весами). | |||
Широкое обсуждение применения жадных методов для аппроксимации задачи комбинаторной оптимизации можно найти в главе 4 работы [5]). | |||
Наконец, в свете весьма правдоподобных теоретико-сложностных допущений, коэффициент аппроксимации ln n является практически лучшим для любого алгоритма с полиномиальным временем выполнения [3, 4]. | |||
== Применение == | |||
Задача о покрытии множествами и ее обобщения и варианты являются фундаментальными для множества областей применения. Несколько примеров: | |||
• выбор небольшого количества узлов сети для хранения файла таким образом, чтобы у всех узлов сети поблизости имелась его копия; | |||
• выбор небольшого количества предложений для озвучивания с целью настройки всех функций модели распознавания речи [11]; | |||
• выбор небольшого количества кадров для съемки с телескопом, на которых был бы отражен свет всех галактик в ночном небе; | |||
• поиск короткой строки, содержащей каждую строку заданного множества в качестве последовательной подстроки. | |||
== См. также == | |||
* [[Локальный поиск для метода k-медиан и задачи о размещении объектов]] | |||
== Литература == | |||
1. Bronnimann, H., Goodrich, M.T.: Almost optimal set covers infinite VC-dimension. Discret. Comput. Geom. 14(4), 463-479 (1995) | |||
2. Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233-235 (1979) | |||
3. Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM 41 (5), 960-981 (1994) | |||
4. Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634-652 (1998) | |||
5. Gonzalez, T.F.: Handbook of Approximation Algorithms and Metaheuristics. Chapman & Hall/CRC Computer & Information Science Series (2007) | |||
6. Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9,256-278 (1974) | |||
7. Khuller, S., Moss, A., Naor, J.:The budgeted maximum coverage problem. Inform. Process. Lett. 70(1), 39^5 (1999) | |||
8. Kolliopoulos, S.G., Young, N.E.: Tight approximation results for general covering integer programs. In: Proceedings of the forty-second annual IEEE Symposium on Foundations of Computer Science, pp. 522-528 (2001) | |||
9. Lovasz, L.: On the ratio of optimal integral and fractional covers. Discret. Math. 13, 383-390 (1975) | |||
10. Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988) | |||
11. van Santen, J.P.H., Buchsbaum, A.L.: Methods for optimal text selection. In: Proceedings of the European Conference on Speech Communication and Technology (Rhodos, Greece) 2, 553-556(1997) | |||
12. Slavik, P.: A tight analysis of the greedy algorithm for set cover. J. Algorithms 25(2), 237-254 (1997) | |||
13. Srinivasan, A.: Improved approximations of packing and covering problems. In: Proceedings of the twenty-seventh annual ACM Symposium on Theory of Computing, pp. 268-276 (1995) | |||
14. Stein, S.K.: Two combinatorial covering theorems. J. Comb. Theor. A 16, 391-397 (1974) | |||
15. Vazirani, V.V.: Approximation Algorithms. Springer, Berlin Heidelberg (2001) | |||