Maksimal dekningsproblem - Maximum coverage problem

Den maksimal dekning problem er et klassisk spørsmål i informatikk , beregningsorientert kompleksitet teori , og operasjoner forskning . Det er et problem som er mye undervist i tilnærmingsalgoritmer .

Som input får du flere sett og et tall . Settene kan ha noen elementer til felles. Du må velge på de fleste av disse settene slik at det maksimale antallet elementer dekkes, dvs. foreningen av de valgte settene har maksimal størrelse. ${\ displaystyle k}$${\ displaystyle k}$

Formelt (uvektet) maksimal dekning

Forekomst: Et nummer og en samling sett .${\ displaystyle k}$${\ displaystyle S = \ {S_ {1}, S_ {2}, \ ldots, S_ {m} \}}$

Mål: Finn en delmengde sett, slik at og antallet dekkede elementer er maksimert.${\ displaystyle S '\ subseteq S}$${\ displaystyle \ left | S '\ right | \ leq k}$${\ displaystyle \ left | \ bigcup _ {S_ {i} \ in S '} {S_ {i}} \ right |}$

Det maksimale dekningsproblemet er NP-hardt , og kan ikke tilnærmes innenfor standardforutsetninger. Dette resultatet samsvarer i hovedsak med tilnærmingsforholdet oppnådd av den generiske grådige algoritmen som brukes for maksimering av submodulære funksjoner med en kardinalitetsbegrensning . ${\ displaystyle 1-{\ frac {1} {e}}+o (1) \ ca 0,632}$

ILP -formulering

Problemet med maksimal dekning kan formuleres som følgende lineære heltallsprogram .

maksimere	${\ displaystyle \ sum _ {e_ {j} \ in E} y_ {j}}$	(maksimere summen av dekkede elementer)
underlagt	${\ displaystyle \ sum {x_ {i}} \ leq k}$	(ikke mer enn sett er valgt) ${\ displaystyle k}$
	${\ displaystyle \ sum _ {e_ {j} \ i S_ {i}} x_ {i} \ geq y_ {j}}$	(hvis minst ett sett er valgt) ${\ displaystyle y_ {j}> 0}$${\ displaystyle e_ {j} \ i S_ {i}}$
	${\ displaystyle y_ {j} \ in \ {0,1 \}}$	(hvis det er dekket) ${\ displaystyle y_ {j} = 1}$${\ displaystyle e_ {j}}$
	${\ displaystyle x_ {i} \ in \ {0,1 \}}$	(hvis da er valgt for omslaget) ${\ displaystyle x_ {i} = 1}$${\ displaystyle S_ {i}}$

Grådig algoritme

Den grådige algoritmen for maksimal dekning velger sett i henhold til en regel: Velg hvert sett på hvert trinn som inneholder det største antallet avdekte elementer. Det kan vises at denne algoritmen oppnår et tilnærmingsforhold på . I tilnærmelsesresultater viser at den grådige algoritmen i hovedsak er den best mulige tilnærmingsalgoritmen for polynomisk tid for maksimal dekning med mindre . ${\ displaystyle 1-{\ frac {1} {e}}}$${\ displaystyle P = NP}$

Kjente utvidelser

Inapproximability -resultatene gjelder for alle utvidelser av problemet med maksimal dekning, ettersom de holder problemet med maksimal dekning som et spesialtilfelle.

Problemet med maksimal dekning kan brukes på veitrafikksituasjoner; et slikt eksempel er å velge hvilke bussruter i et offentlig transportnettverk som skal installeres med hulldektorer for å maksimere dekningen, når bare et begrenset antall sensorer er tilgjengelig. Dette problemet er en kjent forlengelse av problemet med maksimal dekning og ble først utforsket i litteratur av Junade Ali og Vladimir Dyo.

Vektet versjon

I den vektede versjonen har hvert element en vekt . Oppgaven er å finne en maksimal dekning som har maksimal vekt. Grunnversjonen er et spesialtilfelle når alle vekter er . ${\ displaystyle e_ {j}}$${\ displaystyle w (e_ {j})}$${\ displaystyle 1}$

maksimere . (maksimere den veide summen av dekkede elementer).${\ displaystyle \ sum _ {e \ in E} w (e_ {j}) \ cdot y_ {j}}$

underlagt ; (ikke mer enn sett er valgt). ${\ displaystyle \ sum {x_ {i}} \ leq k}$${\ displaystyle k}$

${\ displaystyle \ sum _ {e_ {j} \ i S_ {i}} x_ {i} \ geq y_ {j}}$; (hvis minst ett sett er valgt).${\ displaystyle y_ {j}> 0}$${\ displaystyle e_ {j} \ i S_ {i}}$

${\ displaystyle y_ {j} \ in \ {0,1 \}}$; (hvis det er dekket)${\ displaystyle y_ {j} = 1}$${\ displaystyle e_ {j}}$

${\ displaystyle x_ {i} \ in \ {0,1 \}}$(hvis da er valgt for omslaget).${\ displaystyle x_ {i} = 1}$${\ displaystyle S_ {i}}$

Den grådige algoritmen for den veide maksimale dekningen i hvert trinn velger et sett som inneholder maksimalvekten til udekkede elementer. Denne algoritmen oppnår et tilnærmingsforhold på . ${\ displaystyle 1-{\ frac {1} {e}}}$

Budsjettert maksimal dekning

I den budsjetterte versjonen for maksimal dekning har ikke bare hvert element en vekt , men også hvert sett har en kostnad . I stedet for det begrenser antall sett i dekselet et budsjett er gitt. Dette budsjettet begrenser den totale kostnaden for dekselet som kan velges. ${\ displaystyle e_ {j}}$${\ displaystyle w (e_ {j})}$${\ displaystyle S_ {i}}$${\ displaystyle c (S_ {i})}$${\ displaystyle k}$${\ displaystyle B}$${\ displaystyle B}$

maksimere . (maksimere den veide summen av dekkede elementer).${\ displaystyle \ sum _ {e \ in E} w (e_ {j}) \ cdot y_ {j}}$

underlagt ; (kostnaden for de valgte settene kan ikke overstige ). ${\ displaystyle \ sum {c (S_ {i}) \ cdot x_ {i}} \ leq B}$${\ displaystyle B}$

${\ displaystyle \ sum _ {e_ {j} \ i S_ {i}} x_ {i} \ geq y_ {j}}$; (hvis minst ett sett er valgt).${\ displaystyle y_ {j}> 0}$${\ displaystyle e_ {j} \ i S_ {i}}$

${\ displaystyle y_ {j} \ in \ {0,1 \}}$; (hvis det er dekket)${\ displaystyle y_ {j} = 1}$${\ displaystyle e_ {j}}$

${\ displaystyle x_ {i} \ in \ {0,1 \}}$(hvis da er valgt for omslaget).${\ displaystyle x_ {i} = 1}$${\ displaystyle S_ {i}}$

En grådig algoritme vil ikke lenger produsere løsninger med ytelsesgaranti. Nemlig den verste tilfelle av denne algoritmen kan være veldig langt fra den optimale løsningen. Tilnærmelsesalgoritmen utvides på følgende måte. Først definerer du en modifisert grådig algoritme, som velger settet som har det beste forholdet mellom vektede avdekte elementer til kostnad. For det andre, blant dekk til kardinalitet , finn det beste dekselet som ikke bryter budsjettet. Ring dette dekselet . For det tredje, finn alle dekk til kardinalitet som ikke bryter budsjettet. Bruk disse kardinalitetsdekslene som utgangspunkt, bruk den modifiserte grådige algoritmen, og behold det beste omslaget som er funnet hittil. Ring dette dekselet . På slutten av prosessen vil det omtrentlige beste omslaget være enten eller . Denne algoritmen oppnår et tilnærmingsforhold på for verdier på . Dette er det best mulige tilnærmingsforholdet med mindre . ${\ 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)})}$

Generalisert maksimal dekning

I den generelle versjonen med maksimal dekning har hvert sett en kostnad , elementet har en annen vekt og kostnad, avhengig av hvilket sett som dekker det. Nemlig hvis er dekket av sett vekten av er og kostnaden er . Det gis et budsjett for den totale kostnaden for løsningen. ${\ 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}$

maksimere . (maksimere den veide summen av dekkede elementer i settene de er dekket i).${\ displaystyle \ sum _ {e \ in E, S_ {i}} w_ {i} (e_ {j}) \ cdot y_ {ij}}$

underlagt ; (kostnaden for de valgte settene kan ikke overstige ). ${\ 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}$; (elementet kan bare dekkes av maksimalt ett sett).${\ displaystyle e_ {j} = 1}$

${\ displaystyle \ sum _ {S_ {i}} x_ {i} \ geq y_ {ij}}$; (hvis minst ett sett er valgt).${\ displaystyle y_ {j}> 0}$${\ displaystyle e_ {j} \ i S_ {i}}$

${\ displaystyle y_ {ij} \ in \ {0,1 \}}$; (hvis det dekkes av settet )${\ displaystyle y_ {ij} = 1}$${\ displaystyle e_ {j}}$${\ displaystyle S_ {i}}$

${\ displaystyle x_ {i} \ in \ {0,1 \}}$(hvis da er valgt for omslaget).${\ displaystyle x_ {i} = 1}$${\ displaystyle S_ {i}}$

Generalisert maksimal dekningsalgoritme

Algoritmen bruker begrepet restkostnad/vekt. Restkostnaden/vekten måles mot en foreløpig løsning, og det er forskjellen mellom kostnad/vekt fra kostnad/vekt oppnådd av en foreløpig løsning.

Algoritmen har flere stadier. Finn først en løsning ved hjelp av grådig algoritme. I hver iterasjon av den grådige algoritmen blir den foreløpige løsningen lagt til settet som inneholder den maksimale gjenværende vekten av elementer dividert med restkostnaden for disse elementene sammen med restkostnaden for settet. For det andre, sammenlign løsningen fra det første trinnet med den beste løsningen som bruker et lite antall sett. For det tredje, returner det beste ut av alle undersøkte løsninger. Denne algoritmen oppnår et tilnærmingsforhold på . ${\ displaystyle 1-1/eo (1)}$

Relaterte problemer

• Set cover problem er å dekke alle elementene med så få sett som mulig.

Merknader

Referanser

• Vazirani, Vijay V. (2001). Tilnærmelsesalgoritmer . Springer-Verlag. ISBN 978-3-540-65367-7.

Eksterne linker