Введение

Упаковка множеств — классическая NP-полная задача в теории вычислительной сложности и комбинаторике, и входила в список из 21 NP-полных задач, выделенных Карпом. Пусть задано конечное множество S и список подмножеств S. Тогда задача упаковки множеств спрашивает, существуют ли k подмножеств в этом списке, которые попарно не пересекаются (то есть, не имеют общих элементов). Более формально, задана вселенная U и семейство подмножеств F из U, упаковкой называется подсемейство P множеств из F, такое что все множества в P попарно не пересекаются. Размер упаковки равен |P|. В задаче принятия решения об упаковке множеств на вход подается пара (U, F) и целое число k; вопрос заключается в том, существует ли упаковка размера k или больше. В задаче оптимизации упаковки множеств на вход подается пара (U, F), и требуется найти упаковку, использующую максимальное количество множеств. Задача явно принадлежит классу NP, поскольку, имея заданный набор подмножеств, мы можем легко проверить, что они попарно не пересекаются, за полиномиальное время. Задача оптимизации, максимальная упаковка множеств, требует найти максимальное количество попарно не пересекающихся множеств в списке. Это задача максимизации, которую можно естественно сформулировать как задачу целочисленного линейного программирования, относящуюся к классу задач упаковки.

Формулирование целочисленной линейной программы

Проблема максимальной упаковки множеств может быть сформулирована как следующая целочисленная линейная программа. Максимизировать (максимизировать общее число подмножеств) при ограничениях: для всех (выбранные множества должны быть попарно непересекающимися) для всех (каждое множество либо входит в упаковку, либо не входит).

Сложность

Проблема упаковки множеств не только NP-полна, но и ее оптимизационная версия (общая задача о максимальной упаковке множеств) доказана столь же сложной для аппроксимации, как и задача о максимальной клике; в частности, она не может быть аппроксимирована с точностью до какой-либо константы. Наиболее известный алгоритм аппроксимирует ее с точностью до некоторого коэффициента. Взвешенная модификация также может быть аппроксимирована.

Упаковочные наборы с ограниченным размером

У проблемы есть вариант, который более разрешим. Для любого положительного целого числа k≥3, задача покрытия множества с ограничением k является вариантом задачи покрытия множества, в котором каждое множество содержит не более k элементов. При k=1 задача тривиальна. При k=2 задача эквивалентна поиску максимального паросочетания, которое может быть решено за полиномиальное время. Для любого k≥3 задача является NP-трудной, поскольку она является более общей, чем задача о трехмерном сопоставлении. Однако существуют алгоритмы аппроксимации с постоянным фактором:

Циган представил алгоритм, который для любого ε>0 достигает аппроксимации (k+1+ε)/3. Время работы полиномиально относительно количества множеств и элементов, но двойственно экспоненциально относительно 1/ε. Фурер и Ю представили алгоритм, который достигает той же аппроксимации, но с временем работы, экспоненциальным относительно 1/ε.

Упаковочные наборы с ограниченной степенью

В другом, более удобном для анализа варианте, если ни один элемент не содержится более чем в d подмножествах, ответ можно приблизить с точностью до множителя d. Это также справедливо и для взвешенной версии.

Особые случаи

Сопоставление графов является частным случаем упаковки множеств, в котором размер всех множеств равен 2 (множества соответствуют ребрам). В этом частном случае максимальное по размеру сопоставление можно найти за полиномиальное время. Трехмерное сопоставление — это частный случай, в котором размер всех множеств равен 3, и, кроме того, элементы разделены на 3 цвета, при этом каждое множество содержит ровно один элемент каждого цвета. Этот частный случай по-прежнему является NP-трудным, однако для него существуют алгоритмы приближения с лучшими постоянными коэффициентами, чем для общего случая.

Другие связанные проблемы

В задаче о покрытии множеств задано семейство подмножеств универсального множества , и цель состоит в том, чтобы определить, можно ли выбрать t множеств, которые вместе содержат каждый элемент из . Эти множества могут пересекаться. Оптимизационная версия задачи находит минимальное количество таких множеств. Задача о максимальной упаковке множеств не требует покрытия всех возможных элементов. В задаче об точном покрытии каждый элемент универсального множества должен содержаться ровно в одном из подмножеств. Поиск такого точного покрытия является NP-полной задачей, даже в специальном случае, когда размер всех множеств равен 3 (этот специальный случай называется точным 3-покрытием или X3C). Однако, если для каждого элемента из создать одиночное множество и добавить их в список, полученная задача становится примерно такой же простой, как задача о максимальной упаковке множеств. Карп первоначально доказал NP-полноту задачи о максимальной упаковке множеств посредством сведения из задачи о клике.