Sada balení - Set packing

Balení sady je klasický NP-úplný problém v teorii výpočetní složitosti a kombinatoriky a byl jedním z 21 Karpových 21 NP-úplných problémů .

Předpokládejme, že jeden má konečnou množinu S a seznam podmnožin z S . Poté se problém s balením setů zeptá, zda některé podmnožiny k v seznamu nejsou párově disjunktní (jinými slovy, žádné dvě z nich nesdílejí prvek).

Více formálně, vzhledem k vesmíru a rodině podmnožin , je balení podrodinou množin, takže všechny sady jsou párově disjunktní. Velikost balení je . V případě problému s rozhodnutím o balení je vstupem dvojice a celé číslo ; otázkou je, zda existuje sada balení velikosti nebo více. V problému optimalizace sady balíků je vstupem dvojice a úkolem je najít balení sady, které používá nejvíce sad. ${\ 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}})}$

Problém je jasně v NP, protože vzhledem k k podmnožinám můžeme snadno ověřit, že jsou v polynomiálním čase párově disjunktní .

Verze Optimalizace problému, maximální nastavenou balení , vyzve k zadání maximálního počtu dvou disjunktních množin v seznamu. Jedná se o problém s maximalizací, který lze přirozeně formulovat jako celočíselný lineární program patřící do třídy problémů s balením .

Krycí / balicí problémové páry
Krycí problémy Problémy s balením Minimální nastavený kryt Maximální sada balení Minimální kryt hrany Maximální shoda Minimální vrcholový kryt Maximální nezávislá sada Zakrytí koše Balení koše Polygonový potah Obdélníkové balení
proti t E

Celé číslo lineární formulace programu

Problém s maximální sadou balení lze formulovat jako následující celočíselný lineární program .

maximalizovat	${\ displaystyle \ sum _ {S \ v {\ mathcal {S}}} x_ {S}}$		(maximalizovat celkový počet podmnožin)
podléhá	${\ displaystyle \ suma _ {S \ dvojtečka e \ v S} x_ {S} \ leqslant 1}$	pro všechny ${\ displaystyle e \ in {\ mathcal {U}}}$	(vybrané sady musí být párově disjunktní)
	${\ displaystyle x_ {S} \ v \ {0,1 \}}$	pro všechny . ${\ displaystyle S \ v {\ mathcal {S}}}$	(každá sada je v balení sady nebo ne)

Složitost

Set packing problem is not only NP-complete, but its optimization version (general maximum set packing problem) has been mentioned as obtížné aproximovat jako maximum clique problem ; zejména jej nelze aproximovat v rámci žádného konstantního faktoru. Nejznámější algoritmus jej aproximuje s faktorem . Rovněž lze aproximovat váženou variantu. ${\ displaystyle O ({\ sqrt {| U |}})}$

Problém však má variantu, která je lépe ovladatelná: pokud předpokládáme, že žádná podmnožina nepřesáhne k ≥3 prvků, lze odpověď aproximovat v rámci faktoru k / 2 + ε pro libovolné ε> 0; zejména problém s 3-prvkovými sadami lze přiblížit přibližně do 50%. V jiné přitažlivější variantě, pokud se žádný prvek nevyskytuje ve více než k podskupin, lze odpověď aproximovat v rámci faktoru k . To platí také pro váženou verzi.

Ekvivalentní problémy

Mezi problémem nezávislé sady a problémem se sadou balení existuje redukce polynomu v čase jedna ku jedné :

• Vzhledem k problému s balením sady v kolekci vytvořte graf, kde pro každou sadu existuje vrchol a hrana mezi a if . Nyní každá nezávislá sada vrcholů v generovaném grafu odpovídá sadě balení . ${\ displaystyle {\ mathcal {S}}}$${\ displaystyle S \ v {\ mathcal {S}}}$${\ displaystyle v_ {S}}$${\ displaystyle v_ {S}}$${\ displaystyle v_ {T}}$${\ displaystyle S \ cap T \ neq \ varnothing}$${\ displaystyle {\ mathcal {S}}}$
• Vzhledem k problému nezávislé sady vrcholů v grafu vytvořte kolekci sad, kde pro každý vrchol existuje sada obsahující všechny sousedící hrany . Nyní každé balení sady ve generované kolekci odpovídá nezávislému vrcholu nastavenému v . ${\ displaystyle G (V, E)}$${\ displaystyle v}$${\ displaystyle S_ {v}}$${\ displaystyle v}$${\ displaystyle G (V, E)}$

Jedná se také o obousměrné snížení PTAS a ukazuje, že tyto dva problémy lze stejně obtížně aproximovat.

Speciální případy

Odpovídající a trojrozměrná shoda jsou speciální případy balení sady. Srovnání maximální velikosti lze najít v polynomiálním čase, ale nalezení největší 3-dimenzionální shody nebo největší nezávislé množiny je NP-tvrdé.

Další související problémy

Balení sady je jednou z rodiny problémů souvisejících s zakrytím nebo rozdělením prvků sady. Jedním z úzce souvisejících problémů je problém s krytem sady . Zde jsme také dána nastavenou S a seznam souprav, ale cílem je určit, zda si můžeme vybrat K sady, které dohromady obsahují každý prvek S . Tyto sady se mohou překrývat. Optimalizační verze najde minimální počet takových sad. Maximální sada balení nemusí pokrývat všechny možné prvky.

Na druhou stranu problém přesného krytí NP-Complete vyžaduje, aby každý prvek byl obsažen přesně v jedné z podmnožin. Nalezení takového přesného krytu vůbec, bez ohledu na jeho velikost, je NP-úplný problém. Pokud však vytvoříme sadu singletonů pro každý prvek S a přidáme je do seznamu, výsledný problém je asi tak snadný jako balení sady.

Karp původně ukázal balení setu NP-Complete snížením problému s klikou .

Viz také: Balení v hypergrafu .

Poznámky

Reference

• Maximální balení sady , Viggo Kann.
• " nastavit balení ". Slovník algoritmů a datových struktur , editor Paul E. Black, National Institute of Standards and Technology. Všimněte si, že zde uvedená definice je poněkud odlišná.
• Steven S. Skiena. " Nastavit balení ". Příručka pro návrh algoritmu .
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski a Gerhard Woeginger . Msgstr " Maximální balení sady ". Kompendium problémů s optimalizací NP . Poslední úprava 20. března 2000.
• Michael R. Garey a David S. Johnson (1979). Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti . WH Freemane. ISBN   978-0-7167-1045-5 . A3.1: SP3, str. 221.
• Vazirani, Vijay V. (2001). Aproximační algoritmy . Springer-Verlag. ISBN   978-3-540-65367-7 .

externí odkazy

• [1] : Program Pascal pro řešení problému. Z diskrétních optimalizačních algoritmů s programy Pascal od MacIej M. Syslo, ISBN   0-13-215509-5 .
• Srovnávací hodnoty se skrytými optimálními řešeními pro krytí sady, balení sady a stanovení vítěze
• Řešení problému s balením v PHP
• Optimalizace třírozměrného balení koše