Set ambalare - Set packing

Setul de ambalare este o problemă clasică NP-completă în teoria complexității de calcul și combinatorică și a fost una dintre problemele Karp cu 21 NP-complete .

Să presupunem că cineva are un set finit S și o listă de subseturi de S . Apoi, problema setului de ambalare întreabă dacă unele k subseturi din listă sunt disjuncte în perechi (cu alte cuvinte, niciunul dintre ele nu împărtășește un element).

Mai formal, având în vedere un univers și o familie de subseturi de , un ambalaj este o subfamilie de seturi astfel încât toate seturile să fie disjuncte în perechi. Dimensiunea ambalajului este . În problema de decizie de ambalare setată , intrarea este o pereche și un număr întreg ; întrebarea este dacă există un ambalaj setat de dimensiuni sau mai mult. În problema de optimizare a setului de setare , intrarea este o pereche , iar sarcina este de a găsi un set de ambalare care utilizează cele mai multe seturi. ${\ 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}})}$

Problema este în mod clar în NP deoarece, având în vedere k subseturi, putem verifica cu ușurință că sunt perechi disjuncte în timp polinomial .

Versiunea de optimizare a problemei, ambalarea maximă setată , solicită numărul maxim de seturi disjuncte perechi din listă. Este o problemă de maximizare care poate fi formulată în mod natural ca un program liniar întreg , aparținând clasei de probleme de ambalare .

Perechi de acoperire / ambalare-problemă
Probleme de acoperire Probleme de ambalare Capac minim setat Ambalare setată maximă Capac minim de margine Potrivire maximă Capac minim de vârf Set independent maxim Acoperire coș Ambalare coș Acoperire poligon Ambalare dreptunghiulară
v t e

Formularea programului liniar întreg

Problema maximă de ambalare setată poate fi formulată ca următorul program liniar întreg .

maximiza	${\ displaystyle \ sum _ {S \ in {\ mathcal {S}}} x_ {S}}$		(maximizați numărul total de subseturi)
supus	${\ displaystyle \ sum _ {S \ colon e \ in S} x_ {S} \ leqslant 1}$	pentru toți ${\ displaystyle e \ in {\ mathcal {U}}}$	(seturile selectate trebuie să fie pereche disjuncte)
	${\ displaystyle x_ {S} \ in \ {0,1 \}}$	pentru toți . ${\ displaystyle S \ in {\ mathcal {S}}}$	(fiecare set este fie în ambalajul setului, fie nu)

Complexitate

Problema de ambalare a setului nu este doar NP-completă, dar versiunea sa de optimizare (problema generală de ambalare a setului maxim) s-a dovedit la fel de dificil de aproximat ca problema maximă a clicelor ; în special, nu poate fi aproximat în cadrul vreunui factor constant. Cel mai cunoscut algoritm îl aproximează într-un factor de . Varianta ponderată poate fi, de asemenea, aproximată. ${\ displaystyle O ({\ sqrt {| U |}})}$

Cu toate acestea, problema are o variantă mai ușor de tratat: dacă presupunem că niciun subset nu depășește k ≥3 elemente, răspunsul poate fi aproximat într-un factor de k / 2 + ε pentru orice ε> 0; în special, problema cu seturi de 3 elemente poate fi aproximată în aproximativ 50%. Într-o altă variantă mai tratabilă, dacă niciun element nu apare în mai mult de k din subseturi, răspunsul poate fi aproximat într-un factor de k . Acest lucru este valabil și pentru versiunea ponderată.

Probleme echivalente

Există o reducere unu-la-unu a timpului polinomial între problema setului independent și problema setului de ambalare:

• Având în vedere o problemă de ambalare a setului într-o colecție , creați un grafic unde pentru fiecare set există un vârf și există o margine între și dacă . Acum, fiecare set independent de vârfuri din graficul generat corespunde unui set de ambalare . ${\ displaystyle {\ mathcal {S}}}$${\ displaystyle S \ in {\ mathcal {S}}}$${\ displaystyle v_ {S}}$${\ displaystyle v_ {S}}$${\ displaystyle v_ {T}}$${\ displaystyle S \ cap T \ neq \ varnothing}$${\ displaystyle {\ mathcal {S}}}$
• Având în vedere o problemă independentă de set de vârfuri pe un grafic , creați o colecție de seturi în care pentru fiecare vârf există un set care conține toate muchiile adiacente . Acum fiecare set de ambalaje din colecția generată corespunde unui vârf independent setat în . ${\ displaystyle G (V, E)}$${\ displaystyle v}$${\ displaystyle S_ {v}}$${\ displaystyle v}$${\ displaystyle G (V, E)}$

Aceasta este, de asemenea, o reducere bidirecțională a PTAS și arată că cele două probleme sunt la fel de dificil de aproximat.

Cazuri speciale

Potrivirea și potrivirea tridimensională sunt cazuri speciale de ambalare setată. O potrivire de dimensiune maximă poate fi găsită în timp polinomial, dar găsirea unei potriviri tridimensionale mai mari sau a unui set independent mai mare este NP-hard.

Alte probleme conexe

Ambalarea setului este una dintre o familie de probleme legate de acoperirea sau partiționarea elementelor unui set. O problemă strâns legată este problema acoperirii setului . Aici, de asemenea , dat un set de S și o listă de seturi, dar scopul este de a determina dacă putem alege k seturi care conțin împreună fiecare element al S . Aceste seturi se pot suprapune. Versiunea de optimizare găsește numărul minim de astfel de seturi. Ambalajul setat maxim nu trebuie să acopere fiecare element posibil.

Pe de altă parte, problema exactă a acoperirii NP-complete necesită ca fiecare element să fie conținut exact în unul dintre subseturi. Găsirea unei astfel de acoperiri exacte, indiferent de dimensiune, este o problemă NP-completă . Cu toate acestea, dacă creăm un set single pentru fiecare element al lui S și îl adăugăm la listă, problema rezultată este la fel de ușoară ca ambalarea setată.

Karp a arătat inițial setul de ambalare NP-complet printr-o reducere de la problema clicii .

A se vedea, de asemenea: Ambalarea într-un hypergraph .

Note

Referințe

• Ambalare set maxim , Viggo Kann.
• „ set ambalare ”. Dicționar de algoritmi și structuri de date , editor Paul E. Black, Institutul Național de Standarde și Tehnologie. Rețineți că definiția de aici este oarecum diferită.
• Steven S. Skiena. „ Setați ambalarea ”. Manualul de proiectare a algoritmului .
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski și Gerhard Woeginger . " Ambalare maximă setată ". Un compendiu de probleme de optimizare NP . Ultima modificare pe 20 martie 2000.
• Michael R. Garey și David S. Johnson (1979). Calculatoare și Intractability: Un ghid pentru teoria completitudinii NP . WH Freeman. ISBN   978-0-7167-1045-5 . A3.1: SP3, pag.221.
• Vazirani, Vijay V. (2001). Algoritmi de aproximare . Springer-Verlag. ISBN   978-3-540-65367-7 .

linkuri externe

• [1] : Un program Pascal pentru rezolvarea problemei. Din algoritmi de optimizare discretă cu programe Pascal de MacIej M. Syslo, ISBN   0-13-215509-5 .
• Repere cu soluții ascunse optime pentru acoperirea seturilor, ambalarea seturilor și determinarea câștigătorilor
• Rezolvarea problemei de ambalare în PHP
• Optimizarea ambalării tridimensionale a coșurilor