Максимальный разрез - Maximum cut

Пример максимального среза

Для график, а максимальный разрез это резать размер которого как минимум равен размеру любого другого кроя. То есть это разбиение вершин графа на два дополнительных множества S и Т, такое, что количество ребер между множеством S и набор Т как можно больше. Проблема нахождения максимального разреза в графе известна как Задача Max-Cut.

Проблема может быть сформулирована просто следующим образом. Один хочет подмножество S множества вершин так, чтобы количество ребер между S а дополнительное подмножество максимально велико. Точно так же хочется двудольный подграф графа с максимально возможным количеством ребер.

Существует более общая версия проблемы, которая называется взвешенный Max-Cut где каждому ребру соответствует действительное число, его вес, и цель состоит в том, чтобы максимизировать общий вес ребер между S и его дополнение, а не количество ребер. Взвешенная задача Max-Cut, допускающая как положительные, так и отрицательные веса, может быть тривиально преобразована в взвешенную задачу. минимальный разрез проблема, перевернув знак во всех весах.

Вычислительная сложность

Следующее проблема решения связанных с максимальными сокращениями, широко изучалось в теоретическая информатика:

Учитывая график г и целое число k, определите, есть ли разрез размером не менее k в г.

Эта проблема известна как НП-полный. Легко видеть, что проблема в НП: а да Ответ легко доказать, представив достаточно крупный разрез. NP-полнота задачи может быть продемонстрирована, например, редукцией от максимальная 2-выполнимость (ограничение проблема максимальной выполнимости ).^[1] Взвешенная версия задачи решения была одной из 21 NP-полная задача Карпа;^[2] Карп показал NP-полноту редукцией от проблема раздела.

Канонический вариант оптимизации вышеупомянутой проблемы решения обычно называют Задача максимальной обрезки или Max-Cut и определяется как:

Учитывая график г, найдите максимальный разрез.

Известно, что вариант оптимизации NP-Hard. Противоположная задача - найти минимальный разрез как известно, эффективно решается через Алгоритм Форда – Фулкерсона.

Алгоритмы

Алгоритмы с полиномиальным временем

Поскольку проблема Max-Cut NP-жесткий, не известны полиномиальные алгоритмы для Max-Cut в общих графах.

Планарные графики

Однако в планарные графы, задача максимального отсечения двойственна проблема проверки маршрута (проблема поиска кратчайшего маршрута, который посещает каждое ребро графа хотя бы один раз) в том смысле, что ребра, не принадлежащие максимальному набору разреза графа г являются двойниками ребер, которые удваиваются при оптимальном осмотре двойственный граф из г. Оптимальный обзорный тур образует самопересекающуюся кривую, которая разделяет плоскость на два подмножества, подмножество точек, для которых номер намотки кривой четное и подмножество, для которого номер намотки нечетный; эти два подмножества образуют разрез, который включает в себя все ребра, чьи двойники появляются нечетное количество раз в маршруте. Проблема проверки маршрута может быть решена за полиномиальное время, и эта двойственность позволяет решить задачу максимального разреза за полиномиальное время для плоских графов.^[3] Однако известно, что задача максимального деления пополам является NP-сложной.^[4]

Алгоритмы аппроксимации

Задача Max-Cut: APX-жесткий,^[5] Это означает, что для него не существует схемы полиномиального приближения (PTAS), сколь угодно близкой к оптимальному решению, если только P = NP. Таким образом, каждый известный алгоритм полиномиальной аппроксимации достигает коэффициент аппроксимации строго меньше единицы.

Есть простой рандомизированный 0.5-алгоритм аппроксимации: для каждой вершины подбросьте монетку, чтобы решить, какой половине раздела ее назначить.^[6][7] В ожидании половина кромок - это обрезанные кромки. Этот алгоритм может быть дерандомизированный с метод условных вероятностей; следовательно, существует также простой детерминированный алгоритм 0,5-аппроксимации с полиномиальным временем.^[8][9] Один такой алгоритм начинается с произвольного разбиения вершин данного графа ${displaystyle G = (V, E)}$ и многократно перемещает одну вершину за раз с одной стороны раздела на другую, улучшая решение на каждом шаге, пока больше нельзя будет сделать никаких улучшений этого типа. Количество итераций не более ${displaystyle | E |}$ потому что алгоритм улучшает разрез по крайней мере на одно ребро на каждом шаге. Когда алгоритм завершается, по крайней мере половина ребер, инцидентных каждой вершине, принадлежит разрезу, иначе перемещение вершины улучшит разрез. Следовательно, в разрез входит не менее ${displaystyle | E | / 2}$ края.

Алгоритм полиномиальной аппроксимации для Max-Cut с наиболее известным коэффициентом аппроксимации - это метод Гоэманса и Уильямсона, использующий полуопределенное программирование и рандомизированное округление что достигает отношения приближения ${displaystyle alpha приблизительно 0,878,}$ где

${displaystyle alpha = {frac {2} {pi}} min _ {0leq heta leq pi} {frac {heta} {1-cos heta}}.}.$^[10][11]

Если догадка уникальных игр верно, это наилучший возможный коэффициент приближения для максимального разреза.^[12] Было доказано, что без таких недоказанных предположений NP-трудно аппроксимировать максимальное значение отсечки с коэффициентом аппроксимации лучше, чем ${displaystyle {frac {16} {17}} около 0,941}$.^[13][14]

В ^[15] существует расширенный анализ 10 эвристик для этой проблемы, включая реализацию с открытым исходным кодом.

Приложения

Теоретическая физика

В статистическая физика и неупорядоченные системы, задача Max Cut эквивалентна минимизации Гамильтониан из спин-стекло модель, проще всего Модель Изинга.^[16] Для модели Изинга на графе G и только взаимодействиях ближайших соседей гамильтониан имеет вид

${displaystyle H [s] = - sum _ {ijin E (G)} J_ {ij} s_ {i} s_ {j}}$

Здесь каждая вершина я на графике - это сайт вращения, который может принимать значение вращения ${displaystyle s_ {i} = pm 1.}$ Разделы конфигурации спина ${displaystyle V (G)}$ на два набора, те, у которых есть раскрутка ${displaystyle V ^ {+}}$ и те, у кого есть замедление ${displaystyle V ^ {-}.}$ Обозначим через ${displaystyle delta (V ^ {+})}$ набор ребер, соединяющих два набора. Тогда мы можем переписать гамильтониан как

${displaystyle {egin {выровнено} H [s] & = - сумма _ {ijin E (V ^ {+})} J_ {ij} -sum _ {ijin E (V ^ {-})} J_ {ij} + sum _ {ijin delta (V ^ {+})} J_ {ij} & = - sum _ {ijin E (G)} J_ {ij} + 2sum _ {ijin delta (V ^ {+})} J_ { ij} & = C + 2sum _ {ijin delta (V ^ {+})} J_ {ij} end {выровнено}}}$

Минимизация этой энергии эквивалентна задаче min-cut или установке весов графов как ${displaystyle w_ {ij} = - J_ {ij},}$ проблема максимального сокращения.^[16]

Схемотехника

Проблема максимального сокращения имеет приложения в Конструкция СБИС.^[16]

Смотрите также

• Минимальный разрез
• Минимальный k-разрез
• Нечетный цикл поперечный, что эквивалентно запросу наибольшего двудольного индуцированный подграф

Заметки

использованная литература

• Аузиелло, Джорджио; Крещенци, Пьерлуиджи; Гамбози, Джорджио; Канн, Вигго; Маркетти-Спаккамела, Альберто; Протаси, Марко (2003), Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимируемости, Springer.

Максимальный вырез (оптимизационная версия) - это проблема ND14 в Приложении B (стр. 399).

• Гарей, Майкл Р.; Джонсон, Дэвид С. (1979), Компьютеры и непреодолимость: руководство по теории NP-полноты, W.H. Фриман, ISBN  978-0-7167-1045-5.

Максимальный отсек (вариант решения) - это проблема ND16 в Приложении A2.2.

Максимальный двудольный подграф (вариант решения) - это задача GT25 в Приложении A1.2.

• Гаур, Дайя Рам; Кришнамурти, Рамеш (2007), «Округление LP и расширения», в Гонсалес, Теофило Ф. (ред.), Справочник по аппроксимационным алгоритмам и метаэвристике, Чепмен и Холл / CRC.
• Goemans, Мишель X.; Уильямсон, Дэвид П. (1995), «Улучшенные алгоритмы аппроксимации для задач максимального разреза и выполнимости с использованием полуопределенного программирования», Журнал ACM, 42 (6): 1115–1145, Дои:10.1145/227683.227684, S2CID  15794408.
• Хэдлок, Ф. (1975), "Нахождение максимального разреза плоского графа за полиномиальное время", SIAM J. Comput., 4 (3): 221–225, Дои:10.1137/0204019.
• Хостад, Йохан (2001), "Некоторые оптимальные результаты о несовместимости", Журнал ACM, 48 (4): 798–859, Дои:10.1145/502090.502098, S2CID  5120748.
• Янсен, Клаус; Карпинский, Марек; Лингас, Анджей; Зайдель, Эйке (2005), "Схемы аппроксимации полиномиального времени для MAX-BISECTION на плоских и геометрических графах", SIAM Журнал по вычислениям, 35 (1): 110–119, CiteSeerX  10.1.1.62.5082, Дои:10.1137 / s009753970139567x.
• Карп, Ричард М. (1972), "Сводимость комбинаторных задач ", Миллер, Р. Э .; Тэчер, Дж. У. (ред.), Сложность компьютерных вычислений, Plenum Press, стр. 85–103..
• Хот, Субхаш; Киндлер, Гай; Моссель, Эльханан; О'Доннелл, Райан (2007), «Оптимальные результаты несовместимости для MAX-CUT и других CSP с двумя переменными?», SIAM Журнал по вычислениям, 37 (1): 319–357, Дои:10.1137 / S0097539705447372.
• Хуллер, Самир; Рагхавачари, Баладжи; Янг, Нил Э. (2007), «Жадные методы», в Гонсалес, Теофило Ф. (ред.), Справочник по аппроксимационным алгоритмам и метаэвристике, Чепмен и Холл / CRC.
• Митценмахер, Майкл; Упфаль, Эли (2005), Вероятность и вычисления: рандомизированные алгоритмы и вероятностный анализ, Кембридж.
• Мотвани, Раджив; Рагхаван, Прабхакар (1995), Рандомизированные алгоритмы, Кембридж.
• Ньюман, Аланта (2008), "Макс вырезать", в Као, Мин-Янг (ред.), Энциклопедия алгоритмов, Springer, стр. 489–492, Дои:10.1007/978-0-387-30162-4_219, ISBN  978-0-387-30770-1.
• Пападимитриу, Христос Х.; Яннакакис, Михалис (1991), «Оптимизация, аппроксимация и классы сложности», Журнал компьютерных и системных наук, 43 (3): 425–440, Дои:10.1016 / 0022-0000 (91) 90023-Х.
• Тревизан, Лука; Соркин Григорий; Судан, Мадху; Уильямсон, Дэвид (2000), «Устройства, приближение и линейное программирование», Материалы 37-го симпозиума IEEE по основам компьютерных наук: 617–626.
• Даннинг, Иэн; Гупта, Свати; Зильберхольц, Джон (2018), «Что лучше всего работает, когда? Систематическая оценка эвристики для Max-Cut и QUBO», ИНФОРМС Журнал по вычислительной технике, 30 (3): 608–624, Дои:10.1287 / ijoc.2017.0798.

внешние ссылки

• Пьерлуиджи Крещенци, Вигго Канн, Магнус Халльдорссон, Марек Карпински, Герхард Вёгингер (2000), «Максимальный разрез», в «Сборник задач оптимизации НП».
• Андреа Казини, Никола Ребальати (2012), «Библиотека Python для решения Max Cut»