4446
правок
Минимальная бисекция: различия между версиями
Материал из WEGA
м
нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показано 6 промежуточных версий этого же участника) | |||
| Строка 7: | Строка 7: | ||
В своей основополагающей статье 1988 года Лейтон и Рао [14] разработали алгоритм | В своей основополагающей статье 1988 года Лейтон и Рао [14] разработали аппроксимационный алгоритм по двум критериям для решения задачи о минимальной бисекции с логарифмическим коэффициентом. Этот алгоритм нашел множество приложений, однако вопрос поиска настоящего аппроксимационного алгоритма со схожим коэффициентом оставался открытым еще десять лет. В 1999 году Файге и Краутгамер [6] предложили первый аппроксимационный алгоритм с полиномиальным временем выполнения, который аппроксимирует задачу с полилогарифмическим относительно размера графа коэффициентом. | ||
( | (Аппроксимационный алгоритм по двум критериям разбивает вершины на два множества, каждое из которых содержит не более 2/3 вершин, и его значение (т. е. количество ребер, соединяющих множества) сравнивается со значением наилучшего разбиения на множества равного размера). | ||
| Строка 54: | Строка 54: | ||
== Основные результаты == | == Основные результаты == | ||
Фейге и Краутхамер [ ] предложили алгоритм | Фейге и Краутхамер [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>.''' | ||
| Строка 63: | Строка 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>.''' | ||
| Строка 72: | Строка 72: | ||
Теорема 4. Для графов, не включающих фиксированный граф в качестве минора (т.е. планарных графов) задачи о минимальной бисекции, / | '''Теорема 4. Для графов, не включающих фиксированный граф в качестве минора (т.е. планарных графов) задачи о минимальной бисекции, <math>\beta</math>-сбалансированном сечении и заранее заданном разбиении с фиксированным r могут быть приближенно решены за полиномиальное время с коэффициентом O(log n).''' | ||
Стоит отметить, что все эти результаты можно еще больше обобщить, включая в них веса вершин и вершины-полюса (пары s — t); см. главу 5 в [ 6]. | Стоит отметить, что все эти результаты можно еще больше обобщить, включая в них веса вершин и вершины-полюса (пары 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] и по ссылкам, приведенным в этой работе. | |||
== Применение == | == Применение == | ||
| Строка 92: | Строка 90: | ||
Стоит отметить, что во многих подобных ситуациях применение истинной аппроксимации необязательно, аппроксимации по двум критериям может быть вполне достаточно. Тем не менее, алгоритмы, описанные в разделе «Основные результаты», использовались для разработки алгоритмов для решения других задач – таких как (1) алгоритм | Стоит отметить, что во многих подобных ситуациях применение истинной аппроксимации необязательно, аппроксимации по двум критериям может быть вполне достаточно. Тем не менее, алгоритмы, описанные в разделе «Основные результаты», использовались для разработки алгоритмов для решения других задач – таких как (1) аппроксимационный алгоритм для решения задачи о минимальной бисекции в k-однородных гиперграфах [3]; (2) аппроксимационный алгоритм для варианта задачи о минимальном множественном разрезе [17]; (3) алгоритм эффективного определения невыполнимости случайных булевых формул в 2k-конъюнктивной нормальной форме (2k-SAT) при достаточно большом количестве дизъюнктов [5]. | ||
С учетом практического подхода были предложены и изучены многочисленные эвристики (алгоритмы без гарантии для наихудшего случая) для разбиения графов; их комплексный обзор можно найти в [1]. Одной из самых известных является эвристика локального поиска Лина-Кернигана для минимальной бисекции [11]. | |||
== Открытые вопросы == | == Открытые вопросы == | ||
В настоящее время существует большой разрыв между коэффициентом аппроксимации O(log n) для задачи о минимальной бисекции, полученным в результате применения теоремы 1, и сложностью известных для него результатов аппроксимации. Как упоминалось выше, задача о минимальной бисекции является NP-полной [9]. | В настоящее время существует большой разрыв между коэффициентом аппроксимации <math>O(log^{1,5} \; n)</math> для задачи о минимальной бисекции, полученным в результате применения теоремы 1, и сложностью известных для него результатов аппроксимации. Как упоминалось выше, задача о минимальной бисекции является NP-полной [9]. | ||
Неизвестно, является ли эта задача APX-полной, однако некоторые результаты позволяют предположить такую возможность. Буй и Джонс [4] показали, что для любого фиксированного значения | Неизвестно, является ли эта задача 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 включает рандомизированные алгоритмы с субэкспоненциальным временем выполнения. | ||
| Строка 108: | Строка 105: | ||
Версия с вершинным разрезом задачи о минимальном разрезе определяется следующим образом. Цель состоит в разбиении вершин входного графа на множества V = A | Версия с вершинным разрезом задачи о минимальном разрезе определяется следующим образом. Цель состоит в разбиении вершин входного графа на множества <math>V = A \cup B \cup S \;</math>, где |S| насколько возможно мало, при соблюдении следующего ограничения: <math>max \{ |A|, |B| \} \le n/2 \;</math>, и ни одно ребро не связывает множества A и B. Неизвестно, можно ли получить аппроксимационный алгоритм с полилогарифмическим коэффициентом для решения этой задачи. Стоит отметить, что на тот же вопрос, касающийся версии задачи о минимальной бисекции для ориентированных графов, Фейге и Яхалом дали отрицательный ответ [8]. | ||
== См. также == | == См. также == | ||
| Строка 115: | Строка 111: | ||
*'' [[Сепараторы в графах]] | *'' [[Сепараторы в графах]] | ||
*'' [[Самое | *'' [[Самое разреженное сечение]] | ||
