Задайте задачу разделения - Set splitting problem

В теория сложности вычислений, то Установить разделение проблема в следующем проблема решения: учитывая семью F подмножеств конечного множества S, решите, существует ли раздел S на два подмножества S1, S2 так что все элементы F разбиваются этим разбиением, т.е. ни один из элементов F полностью в S1 или же S2. Разделение множества - одно из Garey & Johnson's классический НП-полный проблемы.[1]

Варианты

Оптимизационная версия этой задачи называется Максимальное разделение набора и требует найти раздел, который максимизирует количество разделенных элементов F. Это APX-полный[2] проблема и, следовательно, в НПО.

В Набор k-Расщепление проблема формулируется следующим образом: дано S, F, и целое число k, существует ли раздел S который разделяет по крайней мере k подмножества F? Исходная формулировка представляет собой ограниченный случай с k равной мощности F. Набор k-Разрезка есть управляемый с фиксированными параметрами, т.е. если k считается фиксированным параметром, а не частью входных данных, тогда существует полиномиальный алгоритм для любого фиксированного k. Дене, Феллоуз и Розамонд представили алгоритм, который решает эту проблему во времени. для какой-то функции ж и постоянный c.[3]

Когда каждый элемент F ограничивается мощностью точно k, вариант решения называется Ek-Установить разделение и версия оптимизации Макс Ek-Установить разделение. За k > 2 первое остается NP полным, а при k ≥ 2 последнее остается APX полным.[4] За k ≥ 4, Ek-Установка разбиения устойчива к приближению. То есть, если P = NP, нет полиномиального времени (множителя) алгоритм аппроксимации что существенно лучше, чем случайное разделение.[5][6]

В Разделение взвешенного набора вариант, в котором подмножества в F имеют веса, и цель состоит в том, чтобы максимизировать общий вес разделенных подмножеств.

Подключение к другим проблемам

Разделение множества - это частный случай Проблема не-все-равной выполнимости без отрицательных переменных. Кроме того, Ek-Установка расщепления равна немонохроматичности раскраска графика из k-униформа гиперграфы. За k= 2, вариант оптимизации сводится к известному Максимальный разрез.[6]

Рекомендации

  1. ^ Гарей, Майкл Р.; Джонсон, Дэвид С. (1979). Компьютеры и непреодолимость: руководство по теории NP-полноты. Нью-Йорк: W.H. Фримен. ISBN  0-7167-1045-5.
  2. ^ Петранк, Эрез (1994). «Трудность приближения: расположение зазора». Вычислительная сложность. Springer.
  3. ^ Дене, Франк; Товарищи, Майкл; Розамонд, Фрэнсис (2003). Алгоритм FPT для разделения множеств (PDF). Теоретико-графические концепции в компьютерных науках (WG2003), Конспект лекций по информатике. 2880. Springer. С. 180–191.
  4. ^ Ловас, Ласло (1973). Покрытия и раскраски гиперграфов. 4-я Юго-Восточная конференция по комбинаторике, теории графов и вычислениям.
  5. ^ Хостад, Йохан (2001). «Некоторые результаты оптимальной несовместимости». Журнал ACM. Ассоциация вычислительной техники. 48: 798–859. Дои:10.1145/502090.502098.
  6. ^ а б Гурусвами, Венкатесан (2003). «Результаты о несовместимости для задач о расщеплении множеств и выполнимости без смешанных предложений». Алгоритмика. Springer. 38: 451–469. Дои:10.1007 / s00453-003-1072-z.