Imposta problema copertina - Set cover problem

Il problema del set cover è una domanda classica in combinatoria , informatica , ricerca operativa e teoria della complessità . È uno dei 21 problemi NP-completi di Karp che si è dimostrato NP-completo nel 1972.

Si tratta di un problema "il cui studio ha portato allo sviluppo di tecniche fondamentali per l'intero campo" degli algoritmi di approssimazione .

Dato un insieme di elementi (chiamato universo ) e un insieme di insiemi la cui unione è uguale all'universo, il problema della copertura dell'insieme consiste nell'identificare il più piccolo sottoinsieme la cui unione è uguale all'universo. Ad esempio, si consideri l'universo e l'insieme degli insiemi . Chiaramente l'unione di è . Tuttavia, possiamo coprire tutti gli elementi con il seguente numero inferiore di insiemi: . ${\displaystyle \{1,2,...,n\}}$${\displaystyle S}$${\displaystyle m}$${\displaystyle S}$${\displaystyle U=\{1,2,3,4,5\}}$${\displaystyle S=\{\{1,2,3\},\{2,4\},\{3,4\},\{4,5\}\}}$${\displaystyle S}$${\displaystyle U}$${\displaystyle \{\{1,2,3\},\{4,5\}\}}$

Più formalmente, dato un universo e una famiglia di sottoinsiemi di , una copertura è una sottofamiglia di insiemi la cui unione è . Nel problema decisionale che copre l'insieme , l'input è una coppia e un intero ; la domanda è se esiste una copertura fissa di dimensioni o meno. Nel problema di ottimizzazione della copertura degli insiemi , l'input è una coppia , e il compito è trovare una copertura degli insiemi che utilizzi il minor numero di insiemi. ${\displaystyle {\mathcal {U}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {U}}}$${\ Displaystyle {\ mathcal {C}} \ subseteq {\ mathcal {S}}}$${\displaystyle {\mathcal {U}}}$${\displaystyle ({\mathcal {U}}, {\mathcal {S}})}$${\displaystyle k}$${\displaystyle k}$${\displaystyle ({\mathcal {U}}, {\mathcal {S}})}$

La versione decisionale della copertura dell'insieme è NP-completa e la versione di ottimizzazione/ricerca della copertura dell'insieme è NP-difficile .

Se a ogni set viene assegnato un costo, diventa un problema di copertura del set ponderato .

Coppie rivestimento/imballo-problema
Problemi di copertura Problemi di imballaggio Copertura minima impostata Imballaggio massimo impostato Copertura minima del bordo Corrispondenza massima Copertura minima del vertice Set massimo indipendente Copertura del bidone Imballaggio del bidone Copertura poligonale Imballaggio rettangolare
v T e

Formulazione di programmi lineari interi

Il problema di copertura dell'insieme minimo può essere formulato come il seguente programma lineare intero (ILP).

minimizzare	${\displaystyle \sum _{s\in {\mathcal {S}}}x_{s}}$		(minimizzare il numero di set)
soggetto a	${\displaystyle \sum _{s\colon e\in s}x_{s}\geqslant 1}$	per tutti ${\displaystyle e\in {\mathcal {U}}}$	(coprire ogni elemento dell'universo)
	${\displaystyle x_{s}\in \{0,1\}}$	per tutti . ${\displaystyle s\in {\mathcal {S}}}$	(ogni set è nella copertina del set o no)

Questo ILP appartiene alla classe più generale di ILP per la copertura dei problemi . Il divario di integralità di questa ILP è al massimo , quindi il suo rilassamento fornisce un algoritmo di approssimazione dei fattori per il problema di copertura dell'insieme minimo (dove è la dimensione dell'universo). ${\displaystyle \scriptstyle \log n}$${\displaystyle \scriptstyle \log n}$ ${\displaystyle \scriptstyle n}$

Nella copertina del set ponderato, ai set vengono assegnati dei pesi. Indica il peso di set con . Allora il programma lineare intero che descrive la copertura dell'insieme pesato è identico a quello dato sopra, eccetto che la funzione obiettivo da minimizzare è . ${\displaystyle s\in {\mathcal {S}}}$${\displaystyle w_{s}}$${\displaystyle \sum _{s\in {\mathcal {S}}}w_{s}x_{s}}$

Colpire la formulazione del set

La copertura del set è equivalente al problema del set che colpisce . Ciò si vede osservando che un'istanza di copertura degli insiemi può essere vista come un grafo bipartito arbitrario , con gli insiemi rappresentati dai vertici a sinistra, l'universo rappresentato dai vertici a destra e gli archi che rappresentano l'inclusione di elementi negli insiemi. Il compito è quindi trovare un sottoinsieme di cardinalità minimo di vertici di sinistra che copra tutti i vertici di destra. Nel problema degli insiemi di Hitting, l'obiettivo è coprire i vertici di sinistra utilizzando un sottoinsieme minimo dei vertici di destra. La conversione da un problema all'altro si ottiene quindi scambiando i due insiemi di vertici.

Algoritmo avido

Esiste un algoritmo greedy per l'approssimazione in tempo polinomiale dell'insiemi che copre che sceglie gli insiemi secondo una regola: in ogni fase, scegli l'insieme che contiene il maggior numero di elementi scoperti. Questo metodo può essere implementato in modo lineare nel tempo nella somma delle dimensioni degli insiemi di input, utilizzando una coda di bucket per dare la priorità agli insiemi. Raggiunge un rapporto di approssimazione di , dove è la dimensione del set da coprire. In altre parole, trova una copertura che può essere volte più grande di quella minima, dove è il -esimo numero armonico : ${\displaystyle H(s)}$${\displaystyle}$${\displaystyle H(n)}$${\displaystyle H(n)}$${\displaystyle n}$

Questo algoritmo greedy raggiunge effettivamente un rapporto di approssimazione di dove è l'insieme di cardinalità massimo di . Per le istanze dense, tuttavia, esiste un algoritmo di approssimazione per ogni . ${\displaystyle H(s^{\prime })}$${\displaystyle s^{\prime }}$${\displaystyle S}$${\displaystyle \delta-}$${\displaystyle c\ln {m}}$${\displaystyle c>0}$

C'è un esempio standard in cui l'algoritmo greedy raggiunge un rapporto di approssimazione di . L'universo è costituito da elementi. Il sistema di insiemi consiste di insiemi disgiunti a coppie con dimensioni rispettivamente, nonché di due insiemi disgiunti aggiuntivi , ciascuno dei quali contiene metà degli elementi di ciascuno . Su questo input, l'algoritmo greedy prende gli insiemi , in quell'ordine, mentre la soluzione ottima consiste solo di e . Un esempio di tale input per è raffigurato a destra. ${\displaystyle \log _{2}(n)/2}$${\displaystyle n=2^{(k+1)}-2}$${\displaystyle k}$${\displaystyle S_{1},\ldots ,S_{k}}$${\displaystyle 2,4,8,\ldots ,2^{k}}$${\displaystyle T_{0},T_{1}}$${\displaystyle S_{i}}$${\displaystyle S_{k},\ldots ,S_{1}}$${\displaystyle T_{0}}$${\displaystyle T_{1}}$${\displaystyle k=3}$

I risultati di inapprossimabilità mostrano che l'algoritmo greedy è essenzialmente il miglior algoritmo di approssimazione del tempo polinomiale per set cover fino a termini di ordine inferiore (vedi i risultati di inapprossimabilità di seguito), sotto ipotesi di complessità plausibile. Un'analisi più rigorosa per l'algoritmo greedy mostra che il rapporto di approssimazione è esattamente . ${\displaystyle \ln {n}-\ln {\ln {n}}+\Theta (1)}$

Sistemi a bassa frequenza

Se ogni elemento si trova al massimo in f insiemi, allora si può trovare una soluzione in tempo polinomiale che approssima l'ottimo entro un fattore di f usando il rilassamento LP .

Se il vincolo viene sostituito da for all S in nel programma lineare intero mostrato sopra , allora diventa un programma lineare (non intero) L . L'algoritmo può essere descritto come segue: ${\displaystyle x_{S}\in \{0,1\}}$${\displaystyle x_{S}\geq 0}$${\displaystyle {\mathcal {S}}}$

1. Trova una soluzione ottima O per il programma L usando un metodo in tempo polinomiale per risolvere programmi lineari.
2. Scegli tutti gli insiemi S per i quali la corrispondente variabile x _S ha valore almeno 1/ f nella soluzione O .

Risultati di inapprossimabilità

Quando si fa riferimento alla dimensione dell'universo, Lund e Yannakakis (1994) hanno mostrato che la copertura degli insiemi non può essere approssimata in tempo polinomiale entro un fattore di , a meno che NP non abbia algoritmi di tempo quasi polinomiale . Feige (1998) ha migliorato questo limite inferiore sotto le stesse ipotesi, che sostanzialmente corrispondono al rapporto di approssimazione raggiunto dall'algoritmo greedy. Raz & Safra (1997) hanno stabilito un limite inferiore di , dove è una certa costante, nell'ipotesi più debole che P NP . Un risultato simile con un valore maggiore di è stato recentemente dimostrato da Alon, Moshkovitz & Safra (2006) . Dinur & Steurer (2013) hanno mostrato un'inapprossimabilità ottimale dimostrando che non può essere approssimata a meno che P NP . ${\displaystyle n}$${\displaystyle {\tfrac {1}{2}}\log _{2}{n}\circa 0,72\ln {n}}$${\displaystyle {\bigl (}1-o(1){\bigr )}\cdot \ln {n}}$${\displaystyle c\cdot \ln {n}}$${\displaystyle c}$${\displaystyle \not =}$${\displaystyle c}$${\displaystyle {\bigl (}1-o(1){\bigr )}\cdot \ln {n}}$${\displaystyle =}$

Coperchio del set ponderato

Rilassando il programma lineare intero per la copertura dell'insieme ponderato sopra indicato , si può utilizzare l' arrotondamento casuale per ottenere un'approssimazione del fattore. L'analisi corrispondente per la copertura del set non ponderata è delineata in Arrotondamento casuale#Algoritmo di arrotondamento casuale per la copertura del set e può essere adattata al caso ponderato. ${\displaystyle O(\log n)}$

Problemi correlati

• Colpire il set è una riformulazione equivalente di Set Cover.
• La copertura del vertice è un caso speciale di Hitting Set.
• La copertura del bordo è un caso speciale di Set Cover.
• La copertura dell'insieme geometrico è un caso speciale di copertura dell'insieme quando l'universo è un insieme di punti e gli insiemi sono indotti dall'intersezione dell'universo e delle forme geometriche (ad es. dischi, rettangoli).${\displaystyle \mathbb {R} ^{d}}$
• Imposta l'imballaggio
• Il problema della copertura massima consiste nello scegliere al massimo k insiemi per coprire il maggior numero possibile di elementi.
• L'insieme dominante è il problema di selezionare un insieme di vertici (l'insieme dominante) in un grafo in modo tale che tutti gli altri vertici siano adiacenti ad almeno un vertice nell'insieme dominante. È stato dimostrato che il problema del set dominante è NP completo attraverso una riduzione dalla copertura del set.
• Il problema esatto della copertura è scegliere un set di copertura senza elementi inclusi in più di un set di copertura.
• Copertina del set rosso blu

Appunti

Riferimenti

• Alon, Noga ; Moshkovitz, Dana ; Safra, Shmuel (2006), "Costruzione algoritmica di insiemi per k-restrizioni", ACM Trans. Algoritmi , 2 (2): 153-177, CiteSeerX  10.1.1.138.8682 , doi : 10,1145 / 1.150.334,1150,336 mila , ISSN  1.549-6.325 , S2CID  11.922.650.
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L .; Stein, Clifford (2001), Introduzione agli algoritmi , Cambridge, Massachusetts: MIT Press e McGraw-Hill, pp. 1033-1038, ISBN 978-0-262-03293-3
• Feige, Uriel (1998), "Una soglia di ln n per l'approssimazione della copertina del set", Journal of the ACM , 45 (4): 634–652, CiteSeerX  10.1.1.70.5014 , doi : 10.1145/285055.285059 , ISSN  0004-5411 , S2CID  52827488.
• Karpinski, Marek; Zelikovsky, Alexander (1998), "Approssimazione di casi densi di problemi di copertura", Atti del DIMACS Workshop on Network Design: Connectivity and Facilities Location , 40 , pp. 169-178, ISBN 9780821870846
• Lund, Carsten ; Yannakakis, Mihalis (1994), "Sulla durezza dell'approssimazione dei problemi di minimizzazione", Journal of the ACM , 41 (5): 960–981, doi : 10.1145/185675.306789 , ISSN  0004-5411 , S2CID  9021065.
• Raz, Ran ; Safra, Shmuel (1997), "Un test di basso grado di probabilità di errore subcostante e una caratterizzazione PCP di probabilità di errore subcostante di NP", STOC '97: Atti del ventinovesimo simposio annuale ACM sulla teoria della informatica , ACM, pp. 475-484, ISBN 978-0-89791-888-6.
• Dinur, Irit ; Steurer, David (2013), "Approccio analitico alla ripetizione parallela", STOC '14: Atti del quarantaseiesimo simposio annuale ACM sulla teoria dell'informatica , ACM, pp. 624-633.
• Vazirani, Vijay V. (2001), Algoritmi di approssimazione (PDF) , Springer-Verlag, ISBN 978-3-540-65367-7
• Korte, Bernhard ; Vygen, Jens (2012), Ottimizzazione combinatoria: teoria e algoritmi (5 ed.), Springer, ISBN 978-3-642-24487-2
• Cardoso, Nuno; Abreu, Rui (2014), "An Efficient Distributed Algorithm for Computing Minimal Hitting Sets" (PDF) , Atti del 25° seminario internazionale sui principi della diagnosi , Graz, Austria, doi : 10.5281/zenodo.10037

link esterno

• Benchmark con soluzioni ottimali nascoste per la copertura del set, l'imballaggio del set e la determinazione del vincitore
• Un compendio di problemi di ottimizzazione NP - Minimum Set Cover