Problém s maximálním pokrytím - Maximum coverage problem

The problém s maximálním pokrytím je klasická otázka v počítačová věda, teorie výpočetní složitosti, a operační výzkum Je to problém, o kterém se často učí aproximační algoritmy.

Jako vstup dostanete několik sad a číslo ${ displaystyle k}$ . Sady mohou mít některé prvky společné. Musíte vybrat maximálně ${ displaystyle k}$ z těchto sad tak, aby byl pokryt maximální počet prvků, tj. sjednocení vybraných sad má maximální velikost.

Formálně (nevážený) maximální pokrytí

Instance: Číslo

{ displaystyle k}

a sbírka sad

{ displaystyle S = {S_ {1}, S_ {2}, ldots, S_ {m} }}

.

Cíl: Najít podmnožinu

{ displaystyle S ^ {'} subseteq S}

sad, takové

{ displaystyle left | S ^ {'} right | leq k}

a počet zahrnutých prvků

{ displaystyle left | bigcup _ {S_ {i} v S ^ {'}} {S_ {i}} vpravo |}

je maximalizován.

Problém s maximálním pokrytím je NP-tvrdé a nelze jej v rámci aproximovat ${ displaystyle 1 - { frac {1} {e}} + o (1) přibližně 0,632}$ za standardních předpokladů. Tento výsledek v zásadě odpovídá aproximačnímu poměru dosaženému použitým obecným chamtivým algoritmem maximalizace submodulárních funkcí s omezením mohutnosti.^[1]

Formulace ILP

Problém s maximálním pokrytím lze formulovat následovně celočíselný lineární program.

maximalizovat	${ displaystyle sum _ {e_ {j} v E} y_ {j}}$	(maximalizovat součet zahrnutých prvků)
podléhá	${ displaystyle sum {x_ {i}} leq k}$	(ne více než ${ displaystyle k}$ sady jsou vybrány)
	${ displaystyle sum _ {e_ {j} v S_ {i}} x_ {i} geq y_ {j}}$	(li ${ displaystyle y_ {j}> 0}$ pak alespoň jedna sada ${ displaystyle e_ {j} v S_ {i}}$ je vybráno)
	${ displaystyle y_ {j} v {0,1 }}$	(li ${ displaystyle y_ {j} = 1}$ pak ${ displaystyle e_ {j}}$ je zakryt)
	${ displaystyle x_ {i} v {0,1 }}$	(li ${ displaystyle x_ {i} = 1}$ pak ${ displaystyle S_ {i}}$ je vybrán pro obal)

Chamtivý algoritmus

The chamtivý algoritmus pro maximální pokrytí vybírá sady podle jednoho pravidla: v každé fázi vyberte sadu, která obsahuje největší počet nekrytých prvků. Je možné ukázat, že tento algoritmus dosahuje přibližného poměru ${ displaystyle 1 - { frac {1} {e}}}$ .^[2] Výsledky přibližnosti ukazují, že chamtivý algoritmus je v podstatě nejlepším možným algoritmem aproximace polynomiálního času pro maximální pokrytí, pokud ${ displaystyle P = NP}$ .^[3]

Známá rozšíření

Výsledky nepřístupnosti se vztahují na všechna rozšíření problému maximálního pokrytí, protože problém maximálního pokrytí považují za speciální případ.

Problém maximálního pokrytí lze použít na situace v silničním provozu; jedním takovým příkladem je výběr, které autobusové trasy v síti veřejné dopravy by měly být instalovány s detektory výmolů, aby se maximalizovalo pokrytí, když je k dispozici pouze omezený počet senzorů. Tento problém je známým rozšířením problému maximálního pokrytí a byl poprvé prozkoumán v literatuře Junade Ali a Vladimir Dyo.^[4]

Vážená verze

Ve vážené verzi každý prvek ${ displaystyle e_ {j}}$ má váhu ${ displaystyle w (e_ {j})}$ . Úkolem je najít maximální pokrytí, které má maximální váhu. Základní verze je speciální případ, kdy jsou všechny váhy ${ displaystyle 1}$ .

maximalizovat

{ displaystyle sum _ {e v E} w (e_ {j}) cdot y_ {j}}

. (maximalizace váženého součtu zahrnutých prvků).

podléhá

{ displaystyle sum {x_ {i}} leq k}

; (ne více než

{ displaystyle k}

sady jsou vybrány).

{ displaystyle sum _ {e_ {j} v S_ {i}} x_ {i} geq y_ {j}}

; (li

{ displaystyle y_ {j}> 0}

pak alespoň jedna sada

{ displaystyle e_ {j} v S_ {i}}

je vybrána).

{ displaystyle y_ {j} v {0,1 }}

; (li

{ displaystyle y_ {j} = 1}

pak

{ displaystyle e_ {j}}

je zakryt)

{ displaystyle x_ {i} v {0,1 }}

(li

{ displaystyle x_ {i} = 1}

pak

{ displaystyle S_ {i}}

pro obal).

Chamtivý algoritmus pro vážené maximální pokrytí v každé fázi vybere sadu, která obsahuje maximální váhu nekrytých prvků. Tento algoritmus dosahuje přibližného poměru ${ displaystyle 1 - { frac {1} {e}}}$ .^[1]

Rozpočtové maximální pokrytí

Ve verzi s maximálním pokrytím v rozpočtu platí nejen každý prvek ${ displaystyle e_ {j}}$ mít váhu ${ displaystyle w (e_ {j})}$ , ale také každá sada ${ displaystyle S_ {i}}$ má náklady ${ displaystyle c (S_ {i})}$ . Namísto ${ displaystyle k}$ který omezuje počet sad v krytu rozpočtu ${ displaystyle B}$ je dáno. Tento rozpočet ${ displaystyle B}$ omezuje celkové náklady na krytí, které lze zvolit.

maximalizovat

{ displaystyle sum _ {e v E} w (e_ {j}) cdot y_ {j}}

. (maximalizace váženého součtu zahrnutých prvků).

podléhá

{ displaystyle sum {c (S_ {i}) cdot x_ {i}} leq B}

; (cena vybraných sad nesmí překročit

{ displaystyle B}

).

{ displaystyle sum _ {e_ {j} v S_ {i}} x_ {i} geq y_ {j}}

; (li

{ displaystyle y_ {j}> 0}

pak alespoň jedna sada

{ displaystyle e_ {j} v S_ {i}}

je vybrána).

{ displaystyle y_ {j} v {0,1 }}

; (li

{ displaystyle y_ {j} = 1}

pak

{ displaystyle e_ {j}}

je zakryt)

{ displaystyle x_ {i} v {0,1 }}

(li

{ displaystyle x_ {i} = 1}

pak

{ displaystyle S_ {i}}

pro obal).

Chamtivý algoritmus již nebude vyrábět řešení se zárukou výkonu. Chování tohoto algoritmu v nejhorším případě může být velmi daleko od optimálního řešení. Aproximační algoritmus je rozšířen následujícím způsobem. Nejprve definujte upravený chamtivý algoritmus, který vybere sadu ${ displaystyle S_ {i}}$ který má nejlepší poměr vážených nekrytých prvků k nákladům. Zadruhé, mezi obálkami mohutnosti ${ displaystyle 1,2, ..., k-1}$ , najít nejlepší krytí, které neporušuje rozpočet. Zavolej tento obal ${ displaystyle H_ {1}}$ . Za třetí, najděte všechny obálky mohutnosti ${ displaystyle k}$ které neporušují rozpočet. Pomocí těchto obalů mohutnosti ${ displaystyle k}$ jako výchozí body použijte upravený chamtivý algoritmus a zachovejte dosud nejlepší pokrytí. Zavolej tento obal ${ displaystyle H_ {2}}$ . Na konci procesu bude přibližné nejlepší krytí buď ${ displaystyle H_ {1}}$ nebo ${ displaystyle H_ {2}}$ . Tento algoritmus dosahuje přibližného poměru ${ displaystyle 1- {1 over e}}$ pro hodnoty ${ displaystyle k geq 3}$ . Toto je nejlepší možný poměr přiblížení, pokud ${ displaystyle NP subseteq DTIME (n ^ {O ( log log n)})}$ .^[5]

Zobecněné maximální pokrytí

V generalizované verzi s maximálním pokrytím každá sada ${ displaystyle S_ {i}}$ má náklady ${ displaystyle c (S_ {i})}$ , prvek ${ displaystyle e_ {j}}$ má jinou váhu a cenu v závislosti na tom, která sada ji pokrývá ${ displaystyle e_ {j}}$ je pokryta sadou ${ displaystyle S_ {i}}$ hmotnost ${ displaystyle e_ {j}}$ je ${ displaystyle w_ {i} (e_ {j})}$ a jeho cena je ${ displaystyle c_ {i} (e_ {j})}$ . Rozpočet ${ displaystyle B}$ je uveden pro celkové náklady na řešení.

maximalizovat

{ displaystyle sum _ {e v E, S_ {i}} w_ {i} (e_ {j}) cdot y_ {ij}}

. (maximalizace váženého součtu zahrnutých prvků v sadách, ve kterých jsou zahrnuty).

podléhá

{ displaystyle sum {c_ {i} (e_ {j}) cdot y_ {ij}} + sum {c (S_ {i}) cdot x_ {i}} leq B}

; (cena vybraných sad nesmí překročit

{ displaystyle B}

).

{ displaystyle sum _ {i} y_ {ij} leq 1}

; (živel

{ displaystyle e_ {j} = 1}

může být pokryta maximálně jednou sadou).

{ displaystyle sum _ {S_ {i}} x_ {i} geq y_ {ij}}

; (li

{ displaystyle y_ {j}> 0}

pak alespoň jedna sada

{ displaystyle e_ {j} v S_ {i}}

je vybrána).

{ displaystyle y_ {ij} v {0,1 }}

; (li

{ displaystyle y_ {ij} = 1}

pak

{ displaystyle e_ {j}}

je pokryta sadou

{ displaystyle S_ {i}}

)

{ displaystyle x_ {i} v {0,1 }}

(li

{ displaystyle x_ {i} = 1}

pak

{ displaystyle S_ {i}}

pro obal).

Zobecněný algoritmus maximálního pokrytí

Algoritmus využívá koncept zbytkové ceny / váhy. Zbytková cena / hmotnost se měří proti předběžnému řešení a je to rozdíl mezi cenou / hmotností a cenou / hmotností získanou předběžným řešením.

Algoritmus má několik fází. Nejprve najděte řešení pomocí chamtivého algoritmu. V každé iteraci chamtivého algoritmu je k předběžnému řešení přidána sada, která obsahuje maximální zbytkovou hmotnost prvků dělenou zbytkovou cenou těchto prvků spolu se zbytkovou cenou sady. Zadruhé porovnejte řešení získané prvním krokem s nejlepším řešením, které používá malý počet sad. Zatřetí, vraťte ze všech zkoumaných řešení to nejlepší. Tento algoritmus dosahuje přibližného poměru ${ displaystyle 1-1 / e-o (1)}$ .^[6]

Související problémy

Nastavit problém s krytem je pokrýt všechny prvky co nejmenším počtem sad.

Poznámky

^ ^A ^b G. L. Nemhauser, L. A. Wolsey a M. L. Fisher. Analýza aproximací pro maximalizaci funkcí podmodulární množiny I, Mathematical Programming 14 (1978), 265–294
^ Hochbaum, Dorit S. (1997). „Přibližování problémů s obalem a balením: Sada krytů, Vrcholový kryt, Nezávislá sada a související problémy“. V Hochbaum, Dorit S. (ed.). Aproximační algoritmy pro NP-těžké problémy. Boston: PWS Publishing Company. str. 94–143. ISBN 978-053494968-6.
^ Feige, Uriel (Červenec 1998). „Prahová hodnota ln n pro přibližné nastavení krytu ". Deník ACM. New York, NY, USA: Sdružení pro výpočetní techniku. 45 (4): 634–652. doi:10.1145/285055.285059. ISSN 0004-5411. S2CID 52827488.
^ Ali, Junade; Dyo, Vladimir (2017). Pokrytí a umístění mobilních senzorů pro vozidla na předem stanovených trasách: chamtivý heuristický přístup. Sborník ze 14. mezinárodní společné konference o elektronickém podnikání a telekomunikacích. Svazek 2: WINSYS. 83–88. doi:10.5220/0006469800830088. ISBN 978-989-758-261-5.
^ Khuller, Samir; Moss, Anna; Naor, Joseph (Seffi) (1999). Msgstr "Problém rozpočtovaného maximálního pokrytí". Dopisy o zpracování informací. 70: 39–45. CiteSeerX 10.1.1.49.5784. doi:10.1016 / S0020-0190 (99) 00031-9.
^ Cohen, Reuven; Katzir, Liran (2008). "Zobecněný problém maximálního pokrytí". Dopisy o zpracování informací. 108: 15–22. CiteSeerX 10.1.1.156.2073. doi:10.1016 / j.ipl.2008.03.017.

Reference

Vazirani, Vijay V. (2001). Aproximační algoritmy. Springer-Verlag. ISBN 978-3-540-65367-7.

externí odkazy

[NVF-1] A ^b G. L. Nemhauser, L. A. Wolsey a M. L. Fisher. Analýza aproximací pro maximalizaci funkcí podmodulární množiny I, Mathematical Programming 14 (1978), 265–294

[2] Hochbaum, Dorit S. (1997). „Přibližování problémů s obalem a balením: Sada krytů, Vrcholový kryt, Nezávislá sada a související problémy“. V Hochbaum, Dorit S. (ed.). Aproximační algoritmy pro NP-těžké problémy. Boston: PWS Publishing Company. str. 94–143. ISBN 978-053494968-6.

[3] Feige, Uriel (Červenec 1998). „Prahová hodnota ln n pro přibližné nastavení krytu ". Deník ACM. New York, NY, USA: Sdružení pro výpočetní techniku. 45 (4): 634–652. doi:10.1145/285055.285059. ISSN 0004-5411. S2CID 52827488.

[4] Ali, Junade; Dyo, Vladimir (2017). Pokrytí a umístění mobilních senzorů pro vozidla na předem stanovených trasách: chamtivý heuristický přístup. Sborník ze 14. mezinárodní společné konference o elektronickém podnikání a telekomunikacích. Svazek 2: WINSYS. 83–88. doi:10.5220/0006469800830088. ISBN 978-989-758-261-5.

[5] Khuller, Samir; Moss, Anna; Naor, Joseph (Seffi) (1999). Msgstr "Problém rozpočtovaného maximálního pokrytí". Dopisy o zpracování informací. 70: 39–45. CiteSeerX 10.1.1.49.5784. doi:10.1016 / S0020-0190 (99) 00031-9.

[6] Cohen, Reuven; Katzir, Liran (2008). "Zobecněný problém maximálního pokrytí". Dopisy o zpracování informací. 108: 15–22. CiteSeerX 10.1.1.156.2073. doi:10.1016 / j.ipl.2008.03.017.

[1]

[2]

[3]

[4]

[5]

[6]