Упаковка множеств

Упаковка множеств — это классическая NP-полная задача в теории вычислительной сложности и комбинаторике и является одной из 21 NP-полных задач Карпа.

Представим, что мы имеем конечное множество S и список подмножеств множества S. Задача упаковки задаётся вопросом, есть ли k подмножеств в списке, которые попарно не пересекаются.

Более формально, если задано множество ${\displaystyle {\mathcal {U}}}$ и семейство ${\displaystyle {\mathcal {S}}}$ подмножеств множества ${\displaystyle {\mathcal {U}}}$, упаковка — это подсемейство ${\displaystyle {\mathcal {C}}\subseteq {\mathcal {S}}}$ множеств, такое, что все множества из ${\displaystyle {\mathcal {C}}}$ попарно не пересекаются, а ${\displaystyle |{\mathcal {C}}|}$ называется размером упаковки. В задаче разрешимости упаковки, входом является пара ${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$ и число ${\displaystyle k}$. Вопрос заключается в определении, существует ли упаковка размера ${\displaystyle k}$ или более. В задаче оптимизации упаковки входом является пара ${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$, а задача заключается в поиске упаковки, использующей как можно больше множеств.

Ясно, что задача принадлежит NP, поскольку, если задано k подмножеств, мы можем просто проверить, что они попарно не пересекаются, за полиномиальное время.

Оптимизационная версия задачи, максимальная упаковка множеств, задаёт вопрос о максимальном числе попарно непересекающихся множеств из списка. Эта задача может естественным образом быть сформулирована как задача целочисленного линейного программирования, она принадлежит классу задач упаковки, а её двойственная задача линейного программирования^[англ.] является задачей о покрытии множества[1].

Пары задач покрытия/упаковки
Задачи покрытия
Минимальное покрытие множества Минимальное вершинное покрытие Минимальное рёберное покрытие
Задачи упаковки
Максимальная упаковка множеств Максимальное паросочетание Максимальное независимое множество

Формулировка задачи линейного программирования

Задачу нахождения максимальной упаковки можно сформулировать как следующую задачу целочисленного линейного программирования.

максимизировать	${\displaystyle \sum _{S\in {\mathcal {S}}}x_{S}}$		(найти максимальное множество подмножеств)
при условиях	${\displaystyle \sum _{S\colon e\in S}x_{S}\leqslant 1}$	для всех ${\displaystyle e\in {\mathcal {U}}}$	(выбранные множества должны попарно не пересекаться)
	${\displaystyle x_{S}\in \{0,1\}}$	для всех ${\displaystyle S\in {\mathcal {S}}}$.	(любое множество либо в упаковке, либо нет)

Примеры

В качестве примера представим, что на вашей кухне имеется набор различных продуктов (${\displaystyle {\mathcal {U}}}$), и у вас есть поваренная книга с коллекцией рецептов блюд ( ${\displaystyle {\mathcal {S}}}$). Каждый рецепт требует наличия некоторого набора продуктов. Вы хотите приготовить максимальное количество блюд из поваренной книги (в предположении, что продукт используется только в одном блюде). В этом случае вы ищете упаковку множеств (${\displaystyle {\mathcal {C}}}$) на (${\displaystyle {\mathcal {U}},{\mathcal {S}}}$) – набор рецептов, в котором продукт не входит в два разных рецепта.

В качестве другого примера представим встречу иностранных представителей, каждый из которых говорит на английском и ещё нескольких других языках. Вы хотите объявить некоторое решение некоторой группе представителей, но вы им не доверяете и не хотите, чтобы они обсуждали решение между собой на языке, который вы не понимаете. Чтобы добиться этого, вы выбираете группу таким образом, что никакие два представителя не говорят на языке, отличном от английского. С другой стороны, вы хотите донести ваше решение максимальному количеству представителей. В этом случае элементами множества являются языки, отличные от английского, а подмножества – языки, на которых говорят конкретные представители. Если два множества не пересекаются, представители не могут разговаривать на языке, отличном от английского. Максимальная упаковка выберет наибольшее возможное число представителей при приведённых ограничениях. Хотя задача в общем виде трудноразрешима, в данном примере хорошим эвристическим подходом будет выбор представителей, говорящих на одном языке (отличном от английского), так что не придётся исключить многих других.

Взвешенная версия

Существует взвешенная версия задачи об упаковке множеств, в которой каждому подмножеству приписан некоторый вес (вещественное число) и мы хотим максимизировать суммарный вес: ${\displaystyle \sum _{S\in {\mathcal {S}}}w(S)\cdot x_{S}}$

В первом примере мы можем приписать вес рецепту, равный числу друзей, которым нравится блюдо, так что ужин доставит удовольствие максимальному числу друзей.

Кажется, что вес делает задачу сложнее, но большинство известных результатов для задачи без весов применимы и к взвешенной задаче.

Эвристика

Задача упаковки может быть трудной для некоторого k, но может быть нетрудно найти k, для которого её легко решить для определённых входных данных. Например, можно использовать жадный алгоритм, в котором мы ищем множество, пересекающееся с наименьшим числом других множеств, добавляем его в решение и удаляем множества, с которыми оно пересекается. Продолжаем делать то же самое, пока есть множества. Мы получим упаковку некоторого размера, хотя и не обязательно максимального размера. Хотя никакой алгоритм не может всегда дать близкий к максимальному результат (см. следующий раздел), во многих практических приложениях этот эвристический алгоритм даёт хорошие результаты.

Сложность

Задача упаковки множеств не только NP-полна, но и доказано, что оптимизационную версию так же трудно аппроксимировать, как и задачу о максимальной клике. В частности, её нельзя аппроксимировать с любым постоянным множителем [2]. Лучший известный алгоритм аппроксимирует с коэффициентом ${\displaystyle O({\sqrt {|U|}})}$[3]. Взвешенный вариант может быть аппроксимировано в той же степени[4].

Однако задача имеет вариант, который более податлив — если мы не позволяем подмножествам иметь более k≥3 элементов, ответ может быть аппроксимирован с коэффициентом k/2 + ε для любого ε > 0. В частности, задача с 3-элементными множествами может быть аппроксимирована с коэффициентом, близким к 50 %. В другом более податливом варианте с условием, что никакой элемент не входит более чем в k подмножеств, ответ может быть аппроксимирован с коэффициентом k. То же верно для взвешенной версии.

Эквивалентные задачи

Существует один-к-одному сведение за полиномиальное время между задачей о независимом множестве и задачей упаковки множеств:

• Если дана задача упаковки множеств на наборе ${\displaystyle {\mathcal {S}}}$, создаём граф, в котором каждое множество ${\displaystyle S\in {\mathcal {S}}}$ представляет вершину ${\displaystyle v_{S}}$, и существует дуга между ${\displaystyle v_{S}}$ и ${\displaystyle v_{T}}$ тогда и только тогда, когда ${\displaystyle S\cap T\neq \phi }$. Теперь каждое независимое множество вершин в полученном графе соответствует упаковке множеств в ${\displaystyle {\mathcal {S}}}$.
• Если дана задача поиска независимого множества вершина графе ${\displaystyle G(V,E)}$, создадим набор множеств, в котором каждой вершине ${\displaystyle v}$ соответствует множество в ${\displaystyle S_{v}}$, содержащее все рёбра, смежные ${\displaystyle v}$. Теперь каждая упаковка в полученном наборе соответствует независимому множеству вершин в ${\displaystyle G(V,E)}$.

Сведение является двусторонним PTAS-сведением^[англ.] и это показывает, что две задачи одинаково трудно аппроксимировать.

Специальные случаи

Паросочетание и трёхмерное паросочетание^[англ.] являются специальными случаями упаковки множеств. Паросочетание максимального размера может быть найдено за полиномиальное время, но поиск наибольшего 3-мерного паросочетания или наибольшего независимого множества являются NP-трудными задачами.

Другие связанные задачи

Упаковка множеств входит в семейство задач покрытия или разделения элементов множества. Одной из близких задач является задача о покрытии множества. Здесь нам также задано множество S и список множеств, но задачей является определение, можем ли мы выбрать k множеств, которые вместе содержат все элементы множества S. Эти множества могут перекрываться. Оптимизационная версия ищет минимальное число таких множеств. Задача максимальной упаковки не требует покрытия всех элементов без исключения.

NP-полная задача точного покрытия^[англ.], с другой стороны, требует, чтобы каждый элемент содержался в точности в одном подмножестве. Поиск такого точного покрытия, независимо от размера, является NP-полной задачей.

Карп (Karp) показал NP-полноту задачи упаковки множеств путём сведения к ней задачи о клике.

См. также: Упаковки гиперграфов^[англ.].

Примечания

1. Vazirani, 2001.
2. Hazan, Safra, Schwartz, 2006. См., в частности, стр. 21 — "Максимальная клика (а потому, максимальное независимое множество и максимальная упаковка множеств) не может быть аппроксимировано с ${\displaystyle O(n^{1-\epsilon })}$ разве только NP ⊂ ZPP."
3. Halldórsson, Kratochvíl, Telle, 1998, с. 176–185.
4. Halldórsson, 1999, с. 261–270.

Литература

• Maximum Set Packing, Viggo Kann.
• "set packing". Dictionary of Algorithms and Data Structures, Редактор Paul E. Black, National Institute of Standards and Technology. Заметьте, что определение здесь несколько отличается.
• Стивен С. Скиена. 18.2 Задача укладки множества // Алгоритмы. Руководство по разработке. — 2. — Санкт-Петербург: «БХВ-Петербург», 2011. — С. 635-638. — ISBN 978-5-9775-0560-4.
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger. "Maximum Set Packing". A compendium of NP optimization problems.
• М.Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. — М.: «Мир», 1982. A3.1: SP3, стр.279.
• Vijay V. Vazirani. Approximation Algorithms. — Springer-Verlag, 2001. — ISBN 3-540-65367-8.
• Elad Hazan, Shmuel Safra, Oded Schwartz. On the complexity of approximating k-set packing // Computational Complexity. — 2006. — Т. 15, вып. 1. — С. 20–39. — doi:10.1007/s00037-006-0205-6.
• Magnus M. Halldórsson, Jan Kratochvíl, Jan Arne Telle. 25th International Colloquium on Automata, Languages and Programming. — Springer-Verlag, 1998. — Т. 1443. — С. 176–185.
• Magnus M. Halldórsson. 5th Annual International Conference on Computing and Combinatorics. — Springer-Verlag, 1999. — Т. 1627. — С. 261–270.

Ссылки

• Программа на Паскале для решения задачи. Из книги Discrete Optimization Algorithms with Pascal Programs (MacIej M. Syslo, ISBN 0-13-215509-5).
• Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner Determination
• Solving packaging problem in PHP