4551
правка
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) мНет описания правки |
||
Строка 7: | Строка 7: | ||
В своей основополагающей статье 1988 года Лейтон и Рао [14] разработали алгоритм | В своей основополагающей статье 1988 года Лейтон и Рао [14] разработали аппроксимационный алгоритм по двум критериям для решения задачи о минимальной бисекции с логарифмическим коэффициентом. Этот алгоритм нашел множество приложений, однако вопрос поиска настоящего аппроксимационного алгоритма со схожим коэффициентом оставался открытым еще десять лет. В 1999 году Файге и Краутгамер [6] предложили первый аппроксимационный алгоритм с полиномиальным временем выполнения, который аппроксимирует задачу с полилогарифмическим относительно размера графа коэффициентом. | ||
( | (Аппроксимационный алгоритм по двум критериям разбивает вершины на два множества, каждое из которых содержит не более 2/3 вершин, и его значение (т. е. количество ребер, соединяющих множества) сравнивается со значением наилучшего разбиения на множества равного размера). | ||
Строка 54: | Строка 54: | ||
== Основные результаты == | == Основные результаты == | ||
Фейге и Краутхамер [6] предложили алгоритм | Фейге и Краутхамер [6] предложили аппроксимационный алгоритм для задачи о минимальной бисекции. Изначально они получили коэффициент апрроксимации <math>O(log^2 \; n)</math>, поскольку в их подходе использовался алгоритм Лейтона и Рао [14]; однако, применив вместо него алгоритм из [2], авторы улучшили коэффициент до <math>O(log^{1,5} \; n)</math>. | ||
Строка 78: | Строка 78: | ||
== Родственные работы == | == Родственные работы == | ||
Аппроксимационный алгоритм по двум критериям для нахождения <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] и по ссылкам, приведенным в этой работе. | ||
== Применение == | == Применение == | ||
Строка 90: | Строка 90: | ||
Стоит отметить, что во многих подобных ситуациях применение истинной аппроксимации необязательно, аппроксимации по двум критериям может быть вполне достаточно. Тем не менее, алгоритмы, описанные в разделе «Основные результаты», использовались для разработки алгоритмов для решения других задач – таких как (1) алгоритм | Стоит отметить, что во многих подобных ситуациях применение истинной аппроксимации необязательно, аппроксимации по двум критериям может быть вполне достаточно. Тем не менее, алгоритмы, описанные в разделе «Основные результаты», использовались для разработки алгоритмов для решения других задач – таких как (1) аппроксимационный алгоритм для решения задачи о минимальной бисекции в k-однородных гиперграфах [3]; (2) аппроксимационный алгоритм для варианта задачи о минимальном множественном разрезе [17]; (3) алгоритм эффективного определения невыполнимости случайных булевых формул в 2k-конъюнктивной нормальной форме (2k-SAT) при достаточно большом количестве дизъюнктов [5]. | ||
Строка 105: | Строка 105: | ||
Версия с вершинным разрезом задачи о минимальном разрезе определяется следующим образом. Цель состоит в разбиении вершин входного графа на множества <math>V = A \cup B \cup S \;</math>, где |S| насколько возможно мало, при соблюдении следующего ограничения: <math>max \{ |A|, |B| \} \le n/2 \;</math>, и ни одно ребро не связывает множества A и B. Неизвестно, можно ли получить алгоритм | Версия с вершинным разрезом задачи о минимальном разрезе определяется следующим образом. Цель состоит в разбиении вершин входного графа на множества <math>V = A \cup B \cup S \;</math>, где |S| насколько возможно мало, при соблюдении следующего ограничения: <math>max \{ |A|, |B| \} \le n/2 \;</math>, и ни одно ребро не связывает множества A и B. Неизвестно, можно ли получить аппроксимационный алгоритм с полилогарифмическим коэффициентом для решения этой задачи. Стоит отметить, что на тот же вопрос, касающийся версии задачи о минимальной бисекции для ориентированных графов, Фейге и Яхалом дали отрицательный ответ [8]. | ||
== См. также == | == См. также == |
правка