Förpackningsset

Uppsättningspackning är ett klassiskt NP-komplett problem inom beräkningskomplexitetsteori och kombinatorik , och är ett av Karps 21 NP-kompletta problem .

Föreställ dig att vi har en finit mängd S och en lista med delmängder av mängden S . Packningsproblemet frågar om det finns k delmängder i en lista som är parvis disjunkta.

Mer formellt, om en uppsättning och en familj av delmängder av uppsättningen ges , är en packning en underfamilj av uppsättningar så att alla uppsättningar från är parvis osammanhängande, och kallas storleken på packningen. I packningslösningsproblemet är indata ett par och ett tal . Frågan är att avgöra om det finns ett paket av storlek eller mer. I packningsoptimeringsproblemet är ingången ett par och uppgiften är att hitta en packning med så många uppsättningar som möjligt. ${\mathcal {U}}$ $\mathcal{S}$ ${\mathcal {U}}$ ${\mathcal {C}}\subseteq {\mathcal {S}}$ ${\mathcal {C}}$ $|{\mathcal {C}}|$ $({\mathcal {U}),{\mathcal {S)))$ $k$ $k$ $({\mathcal {U}),{\mathcal {S)))$

Det är tydligt att problemet tillhör NP , eftersom givet k delmängder kan vi helt enkelt kontrollera att de är parvis disjunkta i polynomtid .

Optimeringsversionen av problemet, den maximala packningen av uppsättningar , ställer frågan om det maximala antalet parvis osammanhängande uppsättningar från listan. Detta problem kan naturligtvis formuleras som ett heltalslinjärt programmeringsproblem , det tillhör klassen av packningsproblem , och dess dubbla linjära programmeringsproblem är ett uppsättningstäckande problem [1] .

Uttalande av det linjära programmeringsproblemet

Problemet med att hitta den maximala packningen kan formuleras som följande linjära heltalsproblem .

maximera	$\sum _{S\in {\mathcal {S}}}x_{S}$		(hitta den maximala uppsättningen av delmängder)
under förhållanden	$\sum _{S\colon e\in S}x_{S}\leqslant 1$	för alla $e\in {\mathcal {U}}$	(valda uppsättningar måste vara parvis osammanhängande)
	$x_{S}\in \{0,1\}$	för alla . $S\in {\mathcal {S}}$	(vilket set är antingen packat eller inte)

Exempel

Som ett exempel, låt oss säga att du har en samling olika livsmedel i ditt kök ( ) och att du har en kokbok med en samling recept ( ). Varje recept kräver en viss uppsättning produkter. Du vill laga det maximala antalet rätter från kokboken (förutsatt att produkten endast används i en maträtt). I det här fallet letar du efter en uppsättningsförpackning ( ) av ( ) - en uppsättning recept där produkten inte ingår i två olika recept. ${\mathcal {U}}$ $\mathcal{S}$ ${\mathcal {C}}$ ${\mathcal {U}},{\mathcal {S}}$

Som ett annat exempel, låt oss föreställa oss ett möte med utländska representanter, som var och en talar engelska och flera andra språk. Du vill tillkännage ett beslut för någon grupp av företrädare, men du litar inte på dem och du vill inte att de ska diskutera beslutet sinsemellan på ett språk som du inte förstår. För att uppnå detta väljer du en grupp på ett sådant sätt att inte två representanter talar ett annat språk än engelska. Å andra sidan vill du förmedla ditt beslut till maximalt antal representanter. I det här fallet är elementen i uppsättningen andra språk än engelska, och delmängderna är de språk som talas av specifika representanter. Om de två uppsättningarna inte överlappar varandra kan representanterna inte tala ett annat språk än engelska. Den maximala packningen kommer att välja största möjliga antal representanter under de givna begränsningarna. Även om problemet i allmänhet är svårlöst, skulle i det här exemplet en bra heuristik vara att välja representanter som talar ett enda språk (annat än engelska) så att många andra inte behöver uteslutas.

Viktad version

Det finns en viktad version av uppsättningspackningsproblemet där varje delmängd tilldelas en viss vikt (ett reellt tal) och vi vill maximera den totala vikten: $\sum _{S\in {\mathcal {S}}}w(S)\cdot x_{S}$

I det första exemplet kan vi tilldela receptet en vikt som är lika med antalet vänner som gillar rätten, så att middagen kommer att glädja det maximala antalet vänner.

Vikten verkar göra problemet svårare, men de flesta av de kända resultaten för problemet utan vikter gäller även för det viktade problemet.

Heuristik

Packningsproblemet kan vara svårt för vissa k , men det kanske inte är svårt att hitta ett k som det är lätt att lösa för vissa ingångar. Till exempel kan vi använda den giriga algoritmen , där vi hittar mängden som skär det minsta antalet andra mängder, lägger till den i lösningen och tar bort mängderna som den korsar sig med. Vi fortsätter att göra detsamma så länge det finns set. Vi kommer att få ett paket av någon storlek, men inte nödvändigtvis maxstorleken. Även om ingen algoritm alltid kan ge nära det maximala resultatet (se nästa avsnitt), ger denna heuristiska algoritm bra resultat i många praktiska tillämpningar.

Svårighet

Inte bara är packningsproblemet NP-komplett, utan optimeringsversionen har visat sig vara lika svår att uppskatta som det maximala klickproblemet . I synnerhet kan den inte approximeras med någon konstant faktor [2] . Den mest kända algoritmen approximerar med en faktor [3] . Den viktade varianten kan approximeras i samma utsträckning [4] . $O({\sqrt {|U|}})$

Problemet har dock en variant som är mer formbar - om vi inte tillåter delmängder att ha mer än k ≥ 3 element, kan svaret approximeras med en faktor k / 2 + ε för valfri ε > 0. problem med 3-elementuppsättningar kan approximeras med en koefficient nära 50%. I en annan mer formbar variant, med villkoret att inget element är i mer än k delmängder, kan svaret approximeras med en faktor k . Detsamma gäller för den viktade versionen.

Motsvarande problem

Det finns en en-till-en-minskning av polynomtiden mellan det oberoende uppsättningsproblemet och uppsättningspackningsproblemet:

Med tanke på ett uppsättningspackningsproblem på en uppsättning skapar vi en graf där varje uppsättning representerar en vertex , och det finns en båge mellan och if och endast if . Nu motsvarar varje oberoende uppsättning av hörn i den resulterande grafen en packning av uppsättningar i . $\mathcal{S}$ $S\in {\mathcal {S}}$ $v_{S}$ $v_{S}$ $v_{T}$ $S\cap T\neq \phi$ $\mathcal{S}$
Med tanke på uppgiften att hitta en oberoende uppsättning i en vertex av grafen skapar vi en uppsättning uppsättningar där varje vertex motsvarar en uppsättning i , som innehåller alla kanter intill . Nu motsvarar varje packning i den resulterande uppsättningen en oberoende uppsättning av hörn i . $G(V,E)$ $v$ ${\displaystyle S_{v))$ $v$ $G(V,E)$

Minskningen är en tvåvägs PTAS-reduktion och den visar att de två problemen är lika svåra att approximera.

Särskilda tillfällen

Matchning och 3D-matchning är specialfall av setpackning. En matchning av maximal storlek kan hittas i polynomtid, men att hitta den största 3-dimensionella matchningen eller den största oberoende uppsättningen är NP-hårda problem.

Andra relaterade uppgifter

Uppsättningsförpackning hör till familjen av problem med att täcka eller separera delar av en uppsättning. Ett av de relaterade problemen är problemet med att täcka setet . Här får vi också en mängd S och en lista med mängder, men utmaningen är att avgöra om vi kan välja k mängder som tillsammans innehåller alla element i S . Dessa uppsättningar kan överlappa varandra. Optimeringsversionen letar efter det minsta antalet sådana uppsättningar. Det maximala packningsproblemet kräver inte att alla delar täcks utan undantag.

Problemet med NP-komplett exakt täckning kräver å andra sidan att varje element ingår i exakt en delmängd. Att hitta en sådan exakt täckning, oavsett storlek, är en NP-komplett uppgift.

Karp visade NP-fullständigheten av setpackningsproblemet genom att reducera klickproblemet till det .

Se även: Förpackningar av hypergrafer .

Anteckningar

↑ Vazirani, 2001 .
↑ Hazan, Safra, Schwartz, 2006 . Se särskilt s. 21 — "En maximal klick (och därför en maximal oberoende uppsättning och en maximal packning av uppsättningar) kan inte approximeras med om inte NP ⊂ ZPP." $O(n^{1-\epsilon })$
↑ Halldórsson, Kratochvíl, Telle, 1998 , sid. 176–185.
↑ Halldorsson, 1999 , sid. 261–270.

Litteratur

Maximal Set Packing , Viggo Kann.
" set packning ". Dictionary of Algorithms and Data Structures , redigerad av Paul E. Black, National Institute of Standards and Technology. Observera att definitionen här är något annorlunda.
Stephen S. Skiena. 18.2 Problemet med att stapla en uppsättning // Algoritmer. Utvecklingsguide. - 2. - St. Petersburg: "BHV-Petersburg", 2011. - S. 635-638. - ISBN 978-5-9775-0560-4 .
Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger. " Maximal Set Packing ". Ett kompendium av NP-optimeringsproblem .
M. Gary, D. Johnson. Datormaskiner och svåra problem. - M. : "Mir", 1982. A3.1: SP3, s.279.
Vijay V. Vazirani. Approximationsalgoritmer. - Springer-Verlag, 2001. - ISBN 3-540-65367-8 .
Elad Hazan, Shmuel Safra, Oded Schwartz. Om komplexiteten i att approximera k -set packning // Computational Complexity . - 2006. - T. 15 , nr. 1 . — S. 20–39 . - doi : 10.1007/s00037-006-0205-6 .
Magnus M. Halldorsson. Femte årliga internationella konferensen om datorer och kombinatorik. - Springer-Verlag, 1999. - T. 1627 . — S. 261–270 .

Länkar

Pascal-program för att lösa problemet . Från diskreta optimeringsalgoritmer med Pascal-program (MacIej M. Syslo, ISBN 0-13-215509-5 ).
Benchmarks med dolda optimala lösningar för settäckning, setpackning och vinnarbestämning
Lösa paketeringsproblem i PHP

Förpackningsuppgifter
Packningscirklar	I en cirkel / i en rätvinklig triangel / i en likbent rätvinklig triangel / i en kvadrat Apollonius matta Cirkelpackningssats Tammes problem (på sfären)
Ballongpackning	Apolloniev i en boll tät packning kontaktnummer Sfärisk packningsgräns (hamming)
Andra paket	Till containrar Tetraedrar Uppsättningar
Pussel	Conway Slotobera - Graatsmy