세트 패킹

집합 패킹은 계산 복잡도 이론과 조합론에서 전형적인 NP-완전 문제이며 Karp의 21개의 NP-완전 문제 중 하나였다.유한 집합 S와 S의 부분 집합 목록이 있다고 가정합니다.그런 다음, 집합 패킹 문제가 목록의 일부 k개의 하위 집합이 쌍으로 분리되었는지 여부를 묻습니다(즉, 두 개의 하위 집합 중 요소를 공유하지 않음).

$좀$ 더 형식적으로 말하면, 우주$U{\displaystyle \mathcal{}}$($style)$와 U$(style)$의$$서브셋의 $패밀리{\displaystyle \mathcal{}}$ S$(style)$가 $주어진다면,$ 패킹은 이러한 모든 디스플레이의 $서브셋$ C$($$style$$)$이다$.$$yle${\$mathcal {C}}$은(는) 쌍으로 분리됩니다.패킹 사이즈는 ${\style$ {\$mathcal {C$입니다. 세트 패킹 결정 문제에서 입력은 쌍$({\displaystyle U,}$ $)$ $디스플레이({\mathcal {U}},$ {\$mathcal {S})$이고 정수 ${\display$ k$\}$는 k$\display$ k$} 이상$의 패킹 $사이즈$가 설정되어 있는지 여부입니다.세트 패킹 최적화 문제에서 입력은 쌍$({\displaystyle U}$,${\displaystyle S\mathcal{}}$) {$displaystyle({\mathcal {U}},$ {\$mathcal$ {S$\}\})$이며, 작업은 가장 많은 세트를 사용하는 세트 패킹을 찾는 것입니다.

k개의 부분 집합이 주어지면 다항식 시간에 쌍으로 분리된 것을 쉽게 확인할 수 있기 때문에 문제는 분명히 NP에 있습니다.

문제의 최적화 버전인 최대 집합 패킹은 목록에서 쌍으로 분리된 집합의 최대 수를 요구합니다.이는 패킹 문제에 속하는 정수 선형 프로그램으로 자연스럽게 공식화할 수 있는 최대화 문제입니다.

커버/패킹 문제 쌍
문제 해결 포장 문제 최소 세트 커버 최대 세트 패킹 최소 가장자리 커버 최대 일치 최소 정점 커버 최대 독립 집합 휴지통 덮개 휴지통 패킹 폴리곤 피복 직사각형 패킹
v t

정수 선형 프로그램 공식화

최대 세트 패킹 문제는 다음과 같은 정수 선형 프로그램으로 공식화할 수 있습니다.

극대화하다	$\displaystyle \sum _{S\in\mathcal {S}}x_{S}}$		(서브셋의 합계수를 나타냅니다)
의 영향을 받는.	$\displaystyle \sum _{S\colon e\in S}x_{S}\leqslant 1$	$모든{\displaystyle }$ e${\$ U \ $display style$e \ $in$\ $mathcal${$U$} } 。	(선택한 세트는 쌍으로 분리해야 합니다.)
	$(\displaystyle x_{S}\in\{0,1\})$	$모든{\displaystyle }$ S${\displaystyle s\mathcal{}}$S \ $style$S \ $in$\$mathcal${ $S$}$$。	(모든 세트는 세트 패킹에 포함되거나 포함되지 않음)

복잡성

세트 패킹 문제는 NP-완전일 뿐만 아니라 최적화 버전(일반적인 최대 세트 패킹 문제)은 최대 클리크 문제만큼 근사하기 어렵다는 것이 입증되었습니다. 특히 상수 ^[1]요인 내에서 근사할 수 없습니다.가장 잘 알려진 알고리즘은 O$U$)(\$displaystyle$ O$({\sqrt${$U$^[2]의 $계수{\displaystyle }$ 내에서 근사합니다.가중 변형도 근사할 수 있습니다.^[3]

단, 이 문제에는 보다 다루기 쉬운 변형이 있다. 즉, 서브셋이 k33 요소를 초과하지 않는다고 가정할 경우, 답은 임의의 θ > 0에 대해 k/2 + θ의 계수 내에서 근사할 수 있다. 특히, 3-원소 세트의 문제는 약 50% 내에서 근사할 수 있다.더 다루기 쉬운 또 다른 변종에서, k개의 부분 집합보다 더 많은 원소가 발생하지 않는 경우, 답은 k개의 인수 내에서 근사할 수 있다.이는 가중치 버전에도 해당됩니다.

관련 문제

동등한 문제

하이퍼그래프 매칭은 세트 패킹과 동일합니다.세트는 하이퍼퍼지에 대응합니다.

독립 집합 문제도 집합 패킹과 동일하며, 둘 사이에 일대일 다항식 시간 감소가 있습니다.

• $컬렉션{\displaystyle \mathcal{}}$ S$(\$ {$S{\displaystyle }$$\})$에 세트 패킹 문제가$$${\displaystyle 있는\mathcal{}}$ 경우 각 $세트$ S(\$displaystyle S\$$in$$\$mathcal {$S$$\})$에 ${\displaystyle {대해}_{}}$ $정점$ V(\$displaystyle$v_${$S$$})와$$V_style$V_style 사이$에 가장자리가 있는 그래프를 작성합니다.${\displaystyle St}$ T $、$ { $display style$S \ $cap$T \ $neq$\ $varnothing$ 。생성된 그래프 내의 모든 독립된 정점 세트는 S$$\ $display \ mathcal$ { S$\}\}$ 의 $세트{\displaystyle \mathcal{}}$ 패킹에 대응합니다.
• $그래프{\displaystyle }$ G$($ $)$에 독립된 정점 집합 문제가 있는 경우 각 $정점{\displaystyle }$ v$(\displaystyle$$$v$)$에 대해 v$(\displaystyle$ v$)$에 $인접$한 모든 모서리를 포함하는$$ $집합{\displaystyle {}_{}}$ S $(\$가 있는 집합 집합을 작성합니다. 생성된 집합의 모든 집합 패킹은 에 해당합니다.G${\displaystyle }$( ${\displaystyle V}$,${\displaystyle E}$) {$displaystyle$ G$(V, E$에 설정된 독립 정점.

이것도 쌍방향 PTAS의 감소로, 두 문제의 근사화가 동등하게 어렵다는 것을 알 수 있습니다.

특수한 경우

그래프 매칭은 모든 세트의 크기가 2인 세트 패킹의 특수한 경우입니다(세트는 모서리에 해당).이 특별한 경우 다항식 시간에서 최대 크기 일치를 찾을 수 있습니다.

3차원 매칭은 모든 세트의 크기가 3인 특수한 케이스이며, 또한 요소를 3가지 색상으로 분할하여 각 세트에 정확하게 각 색상의 요소가 1개씩 포함되어 있습니다.이 특수한 경우는 일반적인 경우보다 더 나은 상수 계수 근사 알고리즘을 가지고 있지만 여전히 NP-hard이다.

기타 관련 문제

세트 커버 문제에서는 $우주{\displaystyle \mathcal{}}$U의 서브셋으로 $구성$된 패밀리 S$($$디스플레이$ $스타일$$)$가 주어지며$$, 목표는$U$의 $모든{\displaystyle \mathcal{}}$ $요소$를 포함하는 k 세트를 함께 선택할 수 있는지 여부를 결정하는 것입니다. 이 세트들은 중복될 수 있습니다$.$최적화 버전은 이러한 세트의 최소 수를 찾습니다.최대 세트 패킹이 가능한 모든 요소를 포함할 필요는 없습니다.

정확한 커버 문제에서는 U$($ 스타일 {\$mathcal {U})$의 $모든{\displaystyle \mathcal{}}$ 요소가 정확히 하나의 서브셋에 포함되어야 합니다.이러한 정확한 커버를 찾는 것은 NP-완전한 문제이며, 모든 세트의 크기가 3인 특수한 경우(이 특별한 경우를 정확한 3 커버 또는 X3C라고 부릅니다)에도 마찬가지입니다.단, S의 각 요소에 대해 싱글톤 세트를 작성하여 목록에 추가하면 세트 패킹과 같은 문제가 발생합니다.

Karp는 원래 clique 문제를 줄임으로써 set packing NP-complete를 나타냈습니다.

'하이퍼그래프에서의 포장'도 참조해 주세요.

메모들

레퍼런스

• 최대 세트 포장, Viggo Kann.
• "세트 패킹"알고리즘과 데이터 구조 사전, 편집자 Paul E.블랙, 국립표준기술연구소여기서의 정의는 다소 다릅니다.
• 스티븐 S.스키나."패킹 세트"알고리즘 설계 매뉴얼.
• 피에를루이지 크레센지, 비고 칸, 마그누스 할도르손, 마렉 카르핀스키, 게르하르트 워징거."최대 세트 패킹"NP 최적화 문제의 개요.최종 변경일 : 2000년 3월 20일
• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 978-0-7167-1045-5. A3.1: SP3, 페이지 221.
• Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. ISBN 978-3-540-65367-7.

외부 링크

• [1]: 문제를 해결하기 위한 Pascal 프로그램.MacIej M. Syslo, ISBN 0-13-215509-5의 Pascal 프로그램을 사용한 이산 최적화 알고리즘.
• 세트 커버, 세트 패킹 및 수상자 판별을 위한 최적의 솔루션이 숨어 있는 벤치마크
• PHP 패키징 문제 해결
• 3차원 빈 패킹 최적화