Problema di copertura massima - Maximum coverage problem

Il problema della copertura massima è una domanda classica nell'informatica , nella teoria della complessità computazionale e nella ricerca operativa . È un problema ampiamente insegnato negli algoritmi di approssimazione .

Come input ti vengono dati diversi set e un numero . I set possono avere alcuni elementi in comune. È necessario selezionare al massimo di questi insiemi in modo tale da coprire il numero massimo di elementi, ovvero l'unione degli insiemi selezionati ha la dimensione massima. ${\displaystyle k}$${\displaystyle k}$

Formalmente, copertura massima (non ponderata)

Istanza: un numero e una raccolta di insiemi .${\displaystyle k}$${\displaystyle S=\{S_{1},S_{2},\ldots ,S_{m}\}}$

Obiettivo: Trovare un sottoinsieme di insiemi, tale che e il numero di elementi coperti sia massimizzato.${\displaystyle S'\subseteq S}$${\displaystyle \left|S'\right|\leq k}$${\displaystyle \left|\bigcup _{S_{i}\in S'}{S_{i}}\right|}$

Il problema della copertura massima è NP-hard e non può essere approssimato all'interno di ipotesi standard. Questo risultato corrisponde essenzialmente al rapporto di approssimazione ottenuto dal generico algoritmo greedy utilizzato per la massimizzazione delle funzioni submodulari con un vincolo di cardinalità . ${\displaystyle 1-{\frac {1}{e}}+o(1)\circa 0,632}$

Formulazione ILP

Il problema della copertura massima può essere formulato come il seguente programma lineare intero .

massimizzare	${\displaystyle \sum _{e_{j}\in E}y_{j}}$	(massimizzando la somma degli elementi coperti)
soggetto a	${\displaystyle \sum {x_{i}}\leq k}$	(non vengono selezionati più di set) ${\displaystyle k}$
	${\displaystyle \sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}}$	(se poi almeno un set è selezionato) ${\displaystyle y_{j}>0}$${\displaystyle e_{j}\in S_{i}}$
	${\displaystyle y_{j}\in \{0,1\}}$	(se poi è coperto) ${\displaystyle y_{j}=1}$${\displaystyle e_{j}}$
	${\displaystyle x_{i}\in \{0,1\}}$	(se poi è selezionato per la copertina) ${\displaystyle x_{i}=1}$${\displaystyle S_{i}}$

Algoritmo avido

L' algoritmo greedy per la massima copertura sceglie gli insiemi secondo una regola: in ogni fase, scegli un insieme che contenga il maggior numero di elementi scoperti. Si può dimostrare che questo algoritmo raggiunge un rapporto di approssimazione di . I risultati di approssimabilità ln mostrano che l'algoritmo greedy è essenzialmente il miglior algoritmo di approssimazione del tempo polinomiale per la massima copertura a meno che . ${\displaystyle 1-{\frac {1}{e}}}$${\displaystyle P=NP}$

Estensioni conosciute

I risultati di inapprossimabilità si applicano a tutte le estensioni del problema di massima copertura poiché considerano il problema di massima copertura come un caso speciale.

Il problema della massima copertura può essere applicato a situazioni di traffico stradale; un esempio è selezionare quali linee di autobus in una rete di trasporto pubblico dovrebbero essere installate con rilevatori di buche per massimizzare la copertura, quando è disponibile solo un numero limitato di sensori. Questo problema è un'estensione nota del problema della copertura massima ed è stato esplorato per la prima volta in letteratura da Junade Ali e Vladimir Dyo.

Versione ponderata

Nella versione pesata ogni elemento ha un peso . Il compito è trovare una copertura massima che abbia il peso massimo. La versione base è un caso speciale quando tutti i pesi sono . ${\displaystyle e_{j}}$${\displaystyle w(e_{j})}$${\displaystyle 1}$

massimizzare . (massimizzando la somma ponderata degli elementi coperti).${\displaystyle \sum _{e\in E}w(e_{j})\cdot y_{j}}$

soggetto a ; (non vengono selezionati più di set). ${\displaystyle \sum {x_{i}}\leq k}$${\displaystyle k}$

${\displaystyle \sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}}$; (se poi è selezionato almeno un set ).${\displaystyle y_{j}>0}$${\displaystyle e_{j}\in S_{i}}$

${\displaystyle y_{j}\in \{0,1\}}$; (se poi è coperto)${\displaystyle y_{j}=1}$${\displaystyle e_{j}}$

${\displaystyle x_{i}\in \{0,1\}}$(se poi è selezionato per la copertina).${\displaystyle x_{i}=1}$${\displaystyle S_{i}}$

L'algoritmo greedy per la copertura massima ponderata in ogni fase sceglie un insieme che contiene il peso massimo degli elementi scoperti. Questo algoritmo raggiunge un rapporto di approssimazione di . ${\displaystyle 1-{\frac {1}{e}}}$

Copertura massima preventivata

Nella versione a massima copertura preventivata, non solo ogni elemento ha un peso , ma anche ogni set ha un costo . Invece di limitare il numero di set nella copertina, viene fornito un budget . Questo budget limita il costo totale della copertura che può essere scelta. ${\displaystyle e_{j}}$${\displaystyle w(e_{j})}$${\displaystyle S_{i}}$${\displaystyle c(S_{i})}$${\displaystyle k}$${\displaystyle B}$${\displaystyle B}$

massimizzare . (massimizzando la somma ponderata degli elementi coperti).${\displaystyle \sum _{e\in E}w(e_{j})\cdot y_{j}}$

soggetto a ; (il costo dei set selezionati non può superare ). ${\displaystyle \sum {c(S_{i})\cdot x_{i}}\leq B}$${\displaystyle B}$

${\displaystyle \sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}}$; (se poi è selezionato almeno un set ).${\displaystyle y_{j}>0}$${\displaystyle e_{j}\in S_{i}}$

${\displaystyle y_{j}\in \{0,1\}}$; (se poi è coperto)${\displaystyle y_{j}=1}$${\displaystyle e_{j}}$

${\displaystyle x_{i}\in \{0,1\}}$(se poi è selezionato per la copertina).${\displaystyle x_{i}=1}$${\displaystyle S_{i}}$

Un algoritmo greedy non produrrà più soluzioni con una garanzia di prestazioni. Vale a dire, il comportamento peggiore di questo algoritmo potrebbe essere molto lontano dalla soluzione ottimale. L'algoritmo di approssimazione viene esteso nel modo seguente. Innanzitutto, definire un algoritmo greedy modificato, che seleziona l'insieme che ha il miglior rapporto tra elementi scoperti ponderati e costo. In secondo luogo, tra le copertine di cardinalità , trova la migliore copertina che non viola il budget. Chiama questa copertina . Terzo, trova tutte le coperture di cardinalità che non violano il budget. Usando queste coperture di cardinalità come punti di partenza, applica l'algoritmo greedy modificato, mantenendo la migliore copertura trovata finora. Chiama questa copertina . Alla fine del processo, la migliore copertura approssimativa sarà o . Questo algoritmo raggiunge un rapporto di approssimazione di per i valori di . Questo è il miglior rapporto di approssimazione possibile a meno che . ${\displaystyle S_{i}}$${\displaystyle 1,2,...,k-1}$${\displaystyle H_{1}}$${\displaystyle k}$${\displaystyle k}$${\displaystyle H_{2}}$${\displaystyle H_{1}}$${\displaystyle H_{2}}$${\displaystyle 1-{1 \over e}}$${\displaystyle k\geq 3}$${\displaystyle NP\subseteq DTIME(n^{O(\log \log n)})}$

Copertura massima generalizzata

Nella versione a massima copertura generalizzata ogni set ha un costo , l'elemento ha un peso e un costo diverso a seconda di quale set lo copre. Vale a dire, se è coperto da set, il peso di è e il suo costo è . Viene fornito un budget per il costo totale della soluzione. ${\displaystyle S_{i}}$${\displaystyle c(S_{i})}$${\displaystyle e_{j}}$${\displaystyle e_{j}}$${\displaystyle S_{i}}$${\displaystyle e_{j}}$${\displaystyle w_{i}(e_{j})}$${\displaystyle c_{i}(e_{j})}$${\displaystyle B}$

massimizzare . (massimizzando la somma ponderata degli elementi coperti negli insiemi in cui sono coperti).${\displaystyle \sum _{e\in E,S_{i}}w_{i}(e_{j})\cdot y_{ij}}$

soggetto a ; (il costo dei set selezionati non può superare ). ${\displaystyle \sum {c_{i}(e_{j})\cdot y_{ij}}+\sum {c(S_{i})\cdot x_{i}}\leq B}$${\displaystyle B}$

${\displaystyle \sum _{i}y_{ij}\leq 1}$; (l'elemento può essere coperto al massimo da un set).${\displaystyle e_{j}=1}$

${\displaystyle \sum _{S_{i}}x_{i}\geq y_{ij}}$; (se poi è selezionato almeno un set ).${\displaystyle y_{j}>0}$${\displaystyle e_{j}\in S_{i}}$

${\displaystyle y_{ij}\in \{0,1\}}$; (se poi è coperto da set )${\displaystyle y_{ij}=1}$${\displaystyle e_{j}}$${\displaystyle S_{i}}$

${\displaystyle x_{i}\in \{0,1\}}$(se poi è selezionato per la copertina).${\displaystyle x_{i}=1}$${\displaystyle S_{i}}$

Algoritmo di copertura massima generalizzato

L'algoritmo utilizza il concetto di costo/peso residuo. Il costo/peso residuo viene misurato rispetto a una soluzione provvisoria ed è la differenza del costo/peso dal costo/peso ottenuto da una soluzione provvisoria.

L'algoritmo ha diverse fasi. Innanzitutto, trova una soluzione usando l'algoritmo greedy. In ogni iterazione dell'algoritmo greedy alla soluzione provvisoria viene aggiunto l'insieme che contiene il peso residuo massimo degli elementi diviso per il costo residuo di questi elementi insieme al costo residuo dell'insieme. In secondo luogo, confronta la soluzione ottenuta con il primo passaggio con la soluzione migliore che utilizza un numero limitato di insiemi. Terzo, restituisci la migliore tra tutte le soluzioni esaminate. Questo algoritmo raggiunge un rapporto di approssimazione di . ${\displaystyle 1-1/eo(1)}$

Problemi correlati

• Il problema della copertura dei set è quello di coprire tutti gli elementi con il minor numero possibile di set.

Appunti

Riferimenti

• Vazirani, Vijay V. (2001). Algoritmi di approssimazione . Springer-Verlag. ISBN 978-3-540-65367-7.

link esterno