4511
правок
Минимальная бисекция: различия между версиями
Перейти к навигации
Перейти к поиску
м
нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показано 13 промежуточных версий этого же участника) | |||
| Строка 7: | Строка 7: | ||
В своей основополагающей статье 1988 года Лейтон и Рао [14] разработали алгоритм | В своей основополагающей статье 1988 года Лейтон и Рао [14] разработали аппроксимационный алгоритм по двум критериям для решения задачи о минимальной бисекции с логарифмическим коэффициентом. Этот алгоритм нашел множество приложений, однако вопрос поиска настоящего аппроксимационного алгоритма со схожим коэффициентом оставался открытым еще десять лет. В 1999 году Файге и Краутгамер [6] предложили первый аппроксимационный алгоритм с полиномиальным временем выполнения, который аппроксимирует задачу с полилогарифмическим относительно размера графа коэффициентом. | ||
( | (Аппроксимационный алгоритм по двум критериям разбивает вершины на два множества, каждое из которых содержит не более 2/3 вершин, и его значение (т. е. количество ребер, соединяющих множества) сравнивается со значением наилучшего разбиения на множества равного размера). | ||
== Разрезы и бисекции == | == Разрезы и бисекции == | ||
Пусть G = (V, E) – неориентированный граф, имеющий n = |V| вершин. Для простоты предположим, что n четно Для подмножества S вершин положим S = V | Пусть G = (V, E) – неориентированный граф, имеющий n = |V| вершин. Для простоты предположим, что n четно Для подмножества S вершин положим <math>\bar{S} = V \backslash S \;</math>. [[Разрез]] <math>(\bar{S}, S) \;</math>, также называемый [[сечение|сечением]], определяется как множество всех ребер, имеющих одну конечную точку в <math>S \;</math>, а другую – в <math>\bar{S} \;</math>. Говорится, что эти ребра пересекают разрез, а множества <math>S \;</math> и <math>\bar{S} \;</math> называются сторонами разреза. | ||
Будем предполагать, что ребра графа G имеют неотрицательные веса. (В невзвешенной версии будем | Будем предполагать, что ребра графа G имеют неотрицательные веса. (В невзвешенной версии будем предполагать веса всех ребер единичными). [[Стоимость]] разреза <math>(S, \bar{S}) \;</math> определяется как сумма весов всех ребер, пересекающих разрез. | ||
Разрез (S, S’) называется бисекцией графа G, если обе его стороны имеют одинаковую мощность, а именно – |S| = | | Разрез (S, S’) называется [[бисекция|бисекцией]] графа G, если обе его стороны имеют одинаковую мощность, а именно – <math>|S| = |\bar{S}| = n/2 \;</math>. Обозначим за b(G) минимальную стоимость бисекции G. | ||
Задача 1 (Минимальная бисекция) | '''Задача 1 (Минимальная бисекция)''' | ||
Дано: неориентированный граф G с неотрицательными весами ребер. | Дано: неориентированный граф G с неотрицательными весами ребер. | ||
Требуется: найти бисекцию (S, S) графа G с минимальной стоимостью. | Требуется: найти бисекцию <math>(S, \bar{S}) \;</math> графа G с минимальной стоимостью. | ||
Это определение имеет одно существенное отличие от определения классической задачи о минимальном разрезе (см, например, [ ] и ссылки в этой работе): в нем имеется ограничение на обе стороны разреза. В результате задача о минимальной бисекции (MINIMUM-BISECTION) является NP-полной [ ], тогда как задача о минимальном разрезе (MINIMUM-CUT) может быть решена за полиномиальное время. | Это определение имеет одно существенное отличие от определения классической задачи о минимальном разрезе (см, например, [10] и ссылки в этой работе): в нем имеется ограничение на обе стороны разреза. В результате задача о минимальной бисекции (MINIMUM-BISECTION) является NP-полной [9], тогда как задача о минимальном разрезе (MINIMUM-CUT) может быть решена за полиномиальное время. | ||
Сбалансированные разрезы и реберные сепараторы | == Сбалансированные разрезы и реберные сепараторы == | ||
Вышеприведенное, довольно простое определение минимальной бисекции можно расширить несколькими способами. В частности, можно задать только верхнюю границу размера каждой стороны разреза. Для 0 < | Вышеприведенное, довольно простое определение минимальной бисекции можно расширить несколькими способами. В частности, можно задать только верхнюю границу размера каждой стороны разреза. Для <math>0 < \beta < 1 \;</math> разрез <math>(S, \bar{S}) \;</math> называется <math>\beta</math>-сбалансированным, если <math>max \{ |S|, |\bar{S}| \} \le \beta n \;</math>. Отметим, что из последнего требования следует <math>min \{ |S|, |\bar{S}| \} \ge (1 - \beta) n \;</math>. В этих терминах бисекция является 1/2-сбалансированным разрезом. | ||
Задача 2 (/ | '''Задача 2 (<math>\beta</math>-сбалансированный разрез)''' | ||
Дано: неориентированный граф G с неотрицательными весами ребер. | Дано: неориентированный граф G с неотрицательными весами ребер. | ||
Требуется: найти | Требуется: найти <math>\beta</math>-сбалансированный разрез <math>(S, \bar{S}) \;</math> графа G с <math>max \{ |S|, |\bar{S}| \} \le \beta n \;</math>, такой, что его стоимость насколько возможно мала. | ||
Специальный случай | Специальный случай <math>\beta = 2/3 \;</math> часто называется задачей о реберном сепараторе (EDGE-SEPARATOR). | ||
В общем случае размер обеих сторон может изначально задаваться произвольным образом (они не обязательно должны быть равными); в этом случае входные условия содержат число k, а задача заключается в нахождении разреза (S, S), такого, что |S| = k. Можно также разделить граф на более чем два фрагмента равного размера – в этом случае входные данные содержат число r > | В общем случае размер обеих сторон может изначально задаваться произвольным образом (они не обязательно должны быть равными); в этом случае входные условия содержат число k, а задача заключается в нахождении разреза <math>(S, \bar{S}) \;</math>, такого, что |S| = k. Можно также разделить граф на более чем два фрагмента равного размера – в этом случае входные данные содержат число <math>r \ge 2 \;</math> – или разделить граф на r фрагментов размерами <math>k_1, ..., k_r \;</math>, где числа <math>k_i \;</math> заранее заданы во входных данных; и в том и в другом случае задача заключается в минимизации количества ребер между различными фрагментами. | ||
Задача 3. Заранее заданное разбиение | '''Задача 3. Заранее заданное разбиение''' | ||
Дано: неориентированный граф G = (V, E) с неотрицательными весами ребер и целые числа | Дано: неориентированный граф G = (V, E) с неотрицательными весами ребер и целые числа <math>k_1, ..., k_r \;</math>, такие, что <math>\sum_i k_i = |V| \;</math>. | ||
Требуется: найти разбиение <math>V = V_1 \cup ... \cup V_r \;</math> графа G с <math>|V_i| = k_i \;</math> для всех i, такое, что общий вес ребер, конечные точки которых принадлежат к разным множествам <math>V_i \;</math>, насколько возможно мал. | |||
== Основные результаты == | == Основные результаты == | ||
Фейге и Краутхамер [ ] предложили алгоритм | Фейге и Краутхамер [6] предложили аппроксимационный алгоритм для задачи о минимальной бисекции. Изначально они получили коэффициент апрроксимации <math>O(log^2 \; n)</math>, поскольку в их подходе использовался алгоритм Лейтона и Рао [14]; однако, применив вместо него алгоритм из [2], авторы улучшили коэффициент до <math>O(log^{1,5} \; n)</math>. | ||
Теорема 1. Задача о минимальной бисекции может быть приближенно решена за полиномиальное время с коэффициентом O( | '''Теорема 1. Задача о минимальной бисекции может быть приближенно решена за полиномиальное время с коэффициентом <math>O(log^{1,5} \; n)</math>. Более конкретно, алгоритм создает для входного графа G бисекцию <math>(S, \bar{S}) \;</math>, стоимость которой не превышает <math>O(log^{1,5} \; n) \cdot b(G)</math>.''' | ||
| Строка 64: | Строка 63: | ||
Теорема 2. Задача о сбалансированном разрезе (и, в частности, о реберном сепараторе может быть приближенно решена за полиномиальное время с коэффициентом O( | '''Теорема 2. Задача о <math>\beta</math>-сбалансированном разрезе (и, в частности, о реберном сепараторе) может быть приближенно решена за полиномиальное время с коэффициентом <math>O(log^{1,5} \; n)</math>.''' | ||
Теорема 3. Задача о заранее заданном разбиении может быть приближенно решена за время | '''Теорема 3. Задача о заранее заданном разбиении может быть приближенно решена за время <math>n^{O(r)} \;</math> с коэффициентом <math>O(log^{1,5} \; n)</math>.''' | ||
| Строка 73: | Строка 72: | ||
Теорема 4. Для графов, не включающих фиксированный граф в качестве минора (т.е. планарных графов) задачи о минимальной бисекции, / | '''Теорема 4. Для графов, не включающих фиксированный граф в качестве минора (т.е. планарных графов) задачи о минимальной бисекции, <math>\beta</math>-сбалансированном сечении и заранее заданном разбиении с фиксированным r могут быть приближенно решены за полиномиальное время с коэффициентом O(log n).''' | ||
Стоит отметить, что все эти результаты можно еще больше обобщить, включая в них веса вершин и вершины-полюса (пары s — t); см. главу 5 в [6]. | |||
== Родственные работы == | == Родственные работы == | ||
Аппроксимационный алгоритм по двум критериям для нахождения <math>\beta</math>-сбалансированного разреза возвращает разрез, являющийся <math>\beta'</math>-сбалансированным для заранее определенного значения <math>\beta' > \beta \;</math>. Например, для бисекции <math>\beta = 1/2 \;</math> и чаще всего <math>\beta' = 2/3 \;</math>. | |||
Алгоритмы из вышеприведенных теорем используют (в качестве черного ящика) аппроксимационный алгоритм для задачи под названием «разрез с минимальным частным» или эквивалентной ей задачи нахождения самого разреженного сечения с равномерным спросом (?). Лучшие из известных на данный момент аппроксимационные алгоритмы с коэффициентом <math>O( \sqrt{log \; n})</math> для решения этой задачи для графов общего вида предложили Арора, Рао и Вазирани [2], а алгоритм для графов, не включающих фиксированный минор, с временем выполнения O(1) – Кляйн, Плоткин и Рао. Эти аппроксимационные алгоритмы для вычисления разреза с минимальным частным позволяют получить аппроксимационный алгоритм по двум критериям с полиномиальным временем выполнения (иногда называемый алгоритмом псевдоаппроксимации) для решения задачи о минимальной бисекции. Например, для графов общего вида алгоритм гарантированно вычисляет 2/3-сбалансированный разрез со стоимостью не более <math>O( \sqrt{log \; n}) \cdot b(G)</math>. Отметим, впрочем, что 2/3-сбалансированный разрез не является хорошей аппроксимацией для значения b(G). Например, если граф G состоит из трех непересекающихся клик равного размера, оптимальный 2/3-сбалансированный разрез не содержит ребер, тогда как <math>b(G) = \Omega(n^2) \;</math>. Информацию о других работах в этом направлении, включая аппроксимационные алгоритмы для плотных графов, для ориентированных графов, а также для других задач о разбиении графов см. в главе 1 [6] и по ссылкам, приведенным в этой работе. | |||
== Применение == | == Применение == | ||
| Строка 93: | Строка 90: | ||
Стоит отметить, что во многих подобных ситуациях применение истинной аппроксимации необязательно, аппроксимации по двум критериям может быть вполне достаточно. Тем не менее, алгоритмы, описанные в разделе «Основные результаты», использовались для разработки алгоритмов для решения других задач – таких как (1) алгоритм | Стоит отметить, что во многих подобных ситуациях применение истинной аппроксимации необязательно, аппроксимации по двум критериям может быть вполне достаточно. Тем не менее, алгоритмы, описанные в разделе «Основные результаты», использовались для разработки алгоритмов для решения других задач – таких как (1) аппроксимационный алгоритм для решения задачи о минимальной бисекции в k-однородных гиперграфах [3]; (2) аппроксимационный алгоритм для варианта задачи о минимальном множественном разрезе [17]; (3) алгоритм эффективного определения невыполнимости случайных булевых формул в 2k-конъюнктивной нормальной форме (2k-SAT) при достаточно большом количестве дизъюнктов [5]. | ||
С учетом практического подхода были предложены и изучены многочисленные эвристики (алгоритмы без гарантии для наихудшего случая) для разбиения графов; их комплексный обзор можно найти в [1]. Одной из самых известных является эвристика локального поиска Лина-Кернигана для минимальной бисекции [11]. | |||
== Открытые вопросы == | |||
В настоящее время существует большой разрыв между коэффициентом аппроксимации <math>O(log^{1,5} \; n)</math> для задачи о минимальной бисекции, полученным в результате применения теоремы 1, и сложностью известных для него результатов аппроксимации. Как упоминалось выше, задача о минимальной бисекции является NP-полной [9]. | |||
Неизвестно, является ли эта задача APX-полной, однако некоторые результаты позволяют предположить такую возможность. Буй и Джонс [4] показали, что для любого фиксированного значения <math>\epsilon > 0 \;</math> задача аппроксимации минимальной бисекции с дополнительным членом <math>n^{2 - \epsilon} \;</math> будет NP-полной. Фейге [7] показал, что если опровержение для задачи выполнимости булевых формул в k-конъюнктивной нормальной форме в случае k=3 является сложным в среднем на реальном распределении входных данных, то для любого фиксированного значения <math>\varepsilon > 0 \;</math> не существует алгоритма <math>(4/3 - \varepsilon \;)</math>-аппроксимации задачи о минимальной бисекции. Хот [12] доказал, что для нахождения минимальной бисекции неприменима аппроксимационная схема с полиномиальным временем выполнения (PTAS), за исключением случая, если класс NP включает рандомизированные алгоритмы с субэкспоненциальным временем выполнения. | |||
Если рассматривать более широкий контекст, в настоящее время существует мультипликативный разрыв в O(log n) между коэффициентом аппроксимации для задачи о минимальной бисекции и коэффициентом аппроксимации для задачи о разрезах с минимальным частным (таким образом, это соотношение актуально также для аппроксимации по двум критериям). Любопытно, можно ли сократить этот разрыв – например, при помощи алгоритма из [2], применив его вне подхода «черного ящика». | |||
Версия с вершинным разрезом задачи о минимальном разрезе определяется следующим образом. Цель состоит в разбиении вершин входного графа на множества <math>V = A \cup B \cup S \;</math>, где |S| насколько возможно мало, при соблюдении следующего ограничения: <math>max \{ |A|, |B| \} \le n/2 \;</math>, и ни одно ребро не связывает множества A и B. Неизвестно, можно ли получить аппроксимационный алгоритм с полилогарифмическим коэффициентом для решения этой задачи. Стоит отметить, что на тот же вопрос, касающийся версии задачи о минимальной бисекции для ориентированных графов, Фейге и Яхалом дали отрицательный ответ [8]. | |||
== См. также == | |||
См. вводную часть статьи Ароры, Рао и Вазирани [2]. | |||
*'' [[Сепараторы в графах]] | |||
*'' [[Самое разреженное сечение]] | |||
== Литература == | |||
1. Alpert, C.J., Kahng, A. B.: Recent directions in netlist partitioning: a survey. Integr. VLSI J. 19(1-2), 1-81 (1995) | |||
2. Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings, and graph partitionings. In: 36th Annual Symposium on the Theory of Computing, pp. 222-231, Chicago, June 2004 | |||
3. Berman, P., Karpinski, M.: Approximability of hypergraph minimum bisection. ECCC Report TR03-056, Electronic Colloquium on Computational Complexity, vol. 10(2003) | |||
4. Bui,T.N., Jones, C.: Finding good approximate vertex and edge partitions is NP-hard. Inform. Process. Lett. 42(3), 153-159 (1992) | |||
5. Coja-Oghlan, A.,Goerdt, A., Lanka, A., Schadlich, F.: Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-SAT. Theor. Comput. Sci. 329(1-3), 1-45(2004) | |||
6. Feige, U., Krauthgamer, R.: A polylogarithmic approximation of the minimum bisection. SIAM Review 48(1), 99-130 (2006) (Previous versions appeared in Proceedings of 41st FOCS, 1999; and in SIAM J. Comput. 2002) | |||
8. Feige, U., Yahalom, O.: On the complexity of finding balanced oneway cuts. Inf. Process. Lett. 87(1), 1-5 (2003) | |||
7. Feige, U.: Relations between average case complexity and approximation complexity. In: 34th Annual ACM Symposium on the Theory of Computing, pp. 534-543, Montreal, May 19-21, | |||
2002 | |||
9. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman and Company (1979) | |||
10. Karger, D.R.: Minimum cuts in near-linear time. J. ACM 47(1), 46-76 (2000) | |||
11. Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49(2), 291-307 (1970) | |||
12. Khot, S.: Ruling out PTAS for graph Min-Bisection, Densest Subgraph and BipartiteClique. In:45th Annual IEEE Symposium on Foundations of Computer Science, pp. 136-145, Georgia Inst. of Technol., Atlanta 17-19Oct.2004 | |||
13. Klein, P., Plotkin, S.A., Rao, S.: Excluded minors, network decomposition, and multicommodity flow. In: 25th Annual ACM Symposium on Theory of Computing, pp. 682-690, San Diego, 1993 May 16-18 | |||
14. Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6), 787-832, 29th FOCS, 1988 (1999) | |||
15. Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615-627 (1980) | |||
16. Rosenberg, A.L., Heath, L.S.: Graph separators, with applications. Frontiers of Computer Science. Kluwer Academic/Plenum Publishers, New York (2001) | |||
17. Svitkina, Z., Tardos, Ё.: Min-Max multiway cut. In: 7th International workshop on Approximation algorithms for combinatorial optimization (APPROX), pp. 207-218, Cambridge, 2004 August 22-24 | |||