Problemă maximă de acoperire - Maximum coverage problem

Problema de acoperire maximă este o întrebare clasică în informatică , teoria complexității calculului și cercetarea operațională . Este o problemă care este predată pe scară largă în algoritmii de aproximare .

Ca intrare vi se oferă mai multe seturi și un număr . Seturile pot avea unele elemente în comun. Trebuie să selectați cel mult aceste seturi astfel încât să fie acoperit numărul maxim de elemente, adică unirea seturilor selectate are dimensiunea maximă. ${\ displaystyle k}$${\ displaystyle k}$

În mod formal, acoperire maximă (neponderată)

Instanță: un număr și o colecție de seturi .${\ displaystyle k}$${\ displaystyle S = \ {S_ {1}, S_ {2}, \ ldots, S_ {m} \}}$

Obiectiv: Găsiți un subset de seturi, astfel încât numărul de elemente acoperite să fie maximizat.${\ displaystyle S '\ subseteq S}$${\ displaystyle \ left | S '\ right | \ leq k}$${\ displaystyle \ left | \ bigcup _ {S_ {i} \ in S '} {S_ {i}} \ right |}$

Problema de acoperire maximă este NP-hard și nu poate fi aproximată în cadrul ipotezelor standard. Acest rezultat se potrivește în esență cu raportul de aproximare realizat de algoritmul lacom generic utilizat pentru maximizarea funcțiilor submodulare cu o constrângere de cardinalitate . ${\ displaystyle 1 - {\ frac {1} {e}} + o (1) \ aproximativ 0,632}$

Formulare ILP

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

maximiza	${\ displaystyle \ sum _ {e_ {j} \ în E} y_ {j}}$	(maximizarea sumei elementelor acoperite)
supus	${\ displaystyle \ sum {x_ {i}} \ leq k}$	(nu sunt selectate mai mult de seturi) ${\ displaystyle k}$
	${\ displaystyle \ sum _ {e_ {j} \ în S_ {i}} x_ {i} \ geq y_ {j}}$	(dacă este selectat cel puțin un set ) ${\ displaystyle y_ {j}> 0}$${\ displaystyle e_ {j} \ în S_ {i}}$
	${\ displaystyle y_ {j} \ in \ {0,1 \}}$	(dacă atunci este acoperit) ${\ displaystyle y_ {j} = 1}$${\ displaystyle e_ {j}}$
	${\ displaystyle x_ {i} \ in \ {0,1 \}}$	(dacă este selectat apoi pentru copertă) ${\ displaystyle x_ {i} = 1}$${\ displaystyle S_ {i}}$

Algoritm lacom

Algoritmul greedy de acoperire maximă alege seturi în conformitate cu o singură regulă: în fiecare etapă, pentru a alege un set care conține cel mai mare număr de elemente neacoperite. Se poate arăta că acest algoritm atinge un raport de aproximare de . Rezultatele l-aproximabilității arată că algoritmul lacom este în esență cel mai bun algoritm de aproximare a timpului polinomial pentru o acoperire maximă, cu excepția cazului în care . ${\ displaystyle 1 - {\ frac {1} {e}}}$${\ displaystyle P = NP}$

Extensii cunoscute

Rezultatele de inaproximabilitate se aplică tuturor extensiilor problemei de acoperire maximă, deoarece acestea dețin problema de acoperire maximă ca un caz special.

Problema de acoperire maximă poate fi aplicată situațiilor de trafic rutier; un astfel de exemplu este selectarea rutelor de autobuz dintr-o rețea de transport public care ar trebui instalate cu detectoare de gropi pentru a maximiza acoperirea, atunci când este disponibil doar un număr limitat de senzori. Această problemă este o extensie cunoscută a Problemei de acoperire maximă și a fost explorată pentru prima dată în literatură de Junade Ali și Vladimir Dyo.

Versiune ponderată

În versiunea ponderată fiecare element are o greutate . Sarcina este de a găsi o acoperire maximă care să aibă o greutate maximă. Versiunea de bază este un caz special atunci când toate greutățile sunt . ${\ displaystyle e_ {j}}$${\ displaystyle w (e_ {j})}$${\ displaystyle 1}$

maximiza . (maximizarea sumei ponderate a elementelor acoperite).${\ displaystyle \ sum _ {e \ in E} w (e_ {j}) \ cdot y_ {j}}$

supus ; (nu sunt selectate mai mult de seturi). ${\ displaystyle \ sum {x_ {i}} \ leq k}$${\ displaystyle k}$

${\ displaystyle \ sum _ {e_ {j} \ în S_ {i}} x_ {i} \ geq y_ {j}}$; (dacă este selectat cel puțin un set ).${\ displaystyle y_ {j}> 0}$${\ displaystyle e_ {j} \ în S_ {i}}$

${\ displaystyle y_ {j} \ in \ {0,1 \}}$; (dacă atunci este acoperit)${\ displaystyle y_ {j} = 1}$${\ displaystyle e_ {j}}$

${\ displaystyle x_ {i} \ in \ {0,1 \}}$(dacă este selectat apoi pentru copertă).${\ displaystyle x_ {i} = 1}$${\ displaystyle S_ {i}}$

Algoritmul lacom pentru acoperirea maximă ponderată la fiecare etapă alege un set care conține greutatea maximă a elementelor neacoperite. Acest algoritm atinge un raport de aproximare de . ${\ displaystyle 1 - {\ frac {1} {e}}}$

Acoperire maximă bugetată

În versiunea de acoperire maximă bugetată, nu numai că fiecare element are o pondere , ci și fiecare set are un cost . În loc să limiteze numărul de seturi din copertă, este dat un buget . Acest buget limitează costul total al acoperirii care poate fi aleasă. ${\ displaystyle e_ {j}}$${\ displaystyle w (e_ {j})}$${\ displaystyle S_ {i}}$${\ displaystyle c (S_ {i})}$${\ displaystyle k}$${\ displaystyle B}$${\ displaystyle B}$

maximiza . (maximizarea sumei ponderate a elementelor acoperite).${\ displaystyle \ sum _ {e \ in E} w (e_ {j}) \ cdot y_ {j}}$

supus ; (costul seturilor selectate nu poate depăși ). ${\ displaystyle \ sum {c (S_ {i}) \ cdot x_ {i}} \ leq B}$${\ displaystyle B}$

${\ displaystyle \ sum _ {e_ {j} \ în S_ {i}} x_ {i} \ geq y_ {j}}$; (dacă este selectat cel puțin un set ).${\ displaystyle y_ {j}> 0}$${\ displaystyle e_ {j} \ în S_ {i}}$

${\ displaystyle y_ {j} \ in \ {0,1 \}}$; (dacă atunci este acoperit)${\ displaystyle y_ {j} = 1}$${\ displaystyle e_ {j}}$

${\ displaystyle x_ {i} \ in \ {0,1 \}}$(dacă este selectat apoi pentru copertă).${\ displaystyle x_ {i} = 1}$${\ displaystyle S_ {i}}$

Un algoritm lacom nu va mai produce soluții cu o garanție de performanță. Și anume, cel mai rău comportament al acestui algoritm ar putea fi foarte departe de soluția optimă. Algoritmul de aproximare este extins prin următorul mod. Mai întâi, definiți un algoritm lacom modificat, care selectează setul care are cel mai bun raport dintre elementele ponderate descoperite și cost. În al doilea rând, printre coperțile cardinalității , găsiți cea mai bună acoperire care nu încalcă bugetul. Sunați la această acoperire . În al treilea rând, găsiți toate acoperirile cardinalității care nu încalcă bugetul. Folosind aceste acoperiri de cardinalitate ca puncte de plecare, aplicați algoritmul lacom modificat, menținând cea mai bună acoperire găsită până acum. Sunați la această acoperire . La sfârșitul procesului, cea mai bună acoperire aproximativă va fi fie sau . Acest algoritm atinge un raport de aproximare pentru valori de . Acesta este cel mai bun raport de aproximare posibil, cu excepția cazului în care . ${\ 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 \ peste e}}$${\ displaystyle k \ geq 3}$${\ displaystyle NP \ subseteq DTIME (n ^ {O (\ log \ log n)})}$

Acoperire maximă generalizată

În versiunea de acoperire maximă generalizată, fiecare set are un cost , elementul are o greutate și un cost diferit, în funcție de setul care îl acoperă. Și anume, dacă este acoperit de set , greutatea este și costul său este . Se oferă un buget pentru costul total al soluției. ${\ 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}$

maximiza . (maximizarea sumei ponderate a elementelor acoperite în seturile în care sunt acoperite).${\ displaystyle \ sum _ {e \ în E, S_ {i}} w_ {i} (e_ {j}) \ cdot y_ {ij}}$

supus ; (costul seturilor selectate nu poate depăși ). ${\ 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}$; (elementul poate fi acoperit doar de cel mult un set).${\ displaystyle e_ {j} = 1}$

${\ displaystyle \ sum _ {S_ {i}} x_ {i} \ geq y_ {ij}}$; (dacă este selectat cel puțin un set ).${\ displaystyle y_ {j}> 0}$${\ displaystyle e_ {j} \ în S_ {i}}$

${\ displaystyle y_ {ij} \ in \ {0,1 \}}$; (dacă atunci este acoperit de set )${\ displaystyle y_ {ij} = 1}$${\ displaystyle e_ {j}}$${\ displaystyle S_ {i}}$

${\ displaystyle x_ {i} \ in \ {0,1 \}}$(dacă este selectat apoi pentru copertă).${\ displaystyle x_ {i} = 1}$${\ displaystyle S_ {i}}$

Algoritm de acoperire maxim generalizat

Algoritmul utilizează conceptul de cost / greutate reziduală. Costul / greutatea reziduală este măsurat în raport cu o soluție provizorie și este diferența dintre cost / greutate și costul / greutatea câștigată de o soluție provizorie.

Algoritmul are mai multe etape. Mai întâi, găsiți o soluție folosind algoritmul lacom. La fiecare iterație a algoritmului lacom, soluției provizorii se adaugă setul care conține greutatea reziduală maximă a elementelor împărțită la costul rezidual al acestor elemente împreună cu costul rezidual al setului. În al doilea rând, comparați soluția câștigată de primul pas cu cea mai bună soluție care utilizează un număr mic de seturi. În al treilea rând, întoarceți cele mai bune dintre toate soluțiile examinate. Acest algoritm atinge un raport de aproximare de . ${\ displaystyle 1-1 / eo (1)}$

Probleme conexe

• Problema setului de acoperire este de a acoperi toate elementele cu cât mai puține seturi.

Note

Referințe

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

linkuri externe