1-keskuksen ongelma

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 8. maaliskuuta 2017 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

1 - keskuksen ongelma tai minimax objektin sijoitteluongelma on klassinen kombinatorinen optimointiongelma , operaatiotutkimuksen tieteenalaongelma , onobjektin sijoitteluongelmanerikoistapaus . Yleisimmässä tapauksessa se on muotoiltu seuraavasti:

Joukko kuluttajapaikkoja, esineiden (tuotanto tai palvelu) mahdollisten sijaintipaikkojen tila ja kuljetuskustannusten funktio mistä tahansa mahdollisesta paikasta kulutuspisteeseen On tarpeen löytää esineiden optimaalinen sijainti minimoimalla maksimikustannukset esineestä kuluttajalle.

Yksinkertainen erikoistapaus, jossa majoitus- ja kulutuspisteet ovat tasossa ja toimituskustannus on euklidinen etäisyys ( planar minimax Euclidean placement problem, Euclidean 1-center plane problem ) tunnetaan myös pienimmän ympyrän ongelmana . Sen yleistäminen korkeampiulotteisiin euklidisiin avaruksiin tunnetaan vähiten rajoittavana sfääriongelmana . Lisäyleistyksessä ( painotettu euklidinen sijaintiongelma ) kulutuspisteille osoitetaan painoja ja kuljetuskustannus on etäisyyksien summa kerrottuna vastaavilla painoilla. Toinen erikoistapaus on lähimmän rivin ongelma , kun tehtävän syöte on merkkijono ja etäisyys mitataan Hamming-etäisyydenä .

Ongelman erikoistapauksia on lukuisia, riippuen sekä kulutuspisteiden ja tuotanto- (tai palvelu-)kohteiden sijainnin valinnasta että etäisyyden laskevan funktion valinnasta.

1-keskuksen ongelma graafiteorian kannalta

Tällaisen ongelman muunnelman muotoilu on siinä, että on annettu graafi sekä kustannusfunktio, ja on tarpeen löytää sellainen joukko , joka on minimaalinen, ts. sellainen joukko , että polun maksimikustannus mitä tahansa kärkeä lähimmältä kärjeltä jää minimaaliseksi. Tehtävää voidaan myös täydentää huippukustannusfunktiolla, jolloin sen säde määritellään muodossa . $G=(V,E)$ $k\in {\mathbb {N}}$ ${\displaystyle c\colon E\to \mathbb {Q} ^{+))$ $Z\subset V$ $\operaattorin nimi {rad} (Z)=\max _{v\in V}\min _{z\in Z}c(z,v)$ $Z$ $Z$ ${\displaystyle w\colon V\to \mathbb {Q} ^{+))$ $\operaattorin nimi {rad} (Z)=\max _{v\in V}[w(v)\cdot \min _{z\in Z}c(z,v)]$

Ongelman likimääräisen ratkaisun ideana on etsiä kiinteää sädettä ahneella algoritmilla . Niin kauan kuin on pisteitä , joita ei kata , täytyy ahneesti valita kärkipiste ja ottaa huomioon kaikki muut saatavilla olevat kärjet . Algoritmi toistetaan eri arvoille . Seuraavassa on menetelmän kuvaus virallisessa muodossa: $Z$ $R$ $Z$ $z$ $2R$ $R$

Asenna ja . $Z=\emptyset$ $U=V$
Heippa : $U\neq \emptyset$
1. ${\displaystyle z=\operaattorin nimi {argmax} \{w(u)\mid u\in U\))$ .
2. ${\displaystyle Z=Z\cup \{z\))$ .
3. ${\displaystyle U=U\setminus \{v\in U\mid w(v)\cdot \operaattorin nimi {dist} (v,z)\leqslant 2R\))$ .
Tuo esiin . $Z$

Antaa olla optimaalinen ratkaisu . Siinä tapauksessa, kun , ahne algoritmi palauttaa joukon siten, että . Tämän perusteella määritämme ja huomaamme, että funktio ei ole monotoninen . Seuraavaksi merkitään säde , jonka avulla vain yksi kärki in voi peittää kaikki graafin kärjet, ts. , a . $R^{*}$ $Z^*$ $R\geqslant R^{*}$ $Z$ $|Z|\leqslant |Z^{*}|$ $f(R)=|\operaattorin nimi {GreedyCenter} (G,c,w,R)|$ $f$ $R'=\max _{v\in V}[w(v)\cdot \sum _{e\in E}c(e)]$ $Z$ $f(R')=1$ $f(0)=|V|=n$

Lemma. Jokaiselle kuvaajalle , jolla on optimaalinen joukko ja säde , epäyhtälö pätee kaikkiin . $G=(V,E)$ $Z^*$ $R^{*}=\operaattorinimi {rad} (Z^{*})$ $f(R)\leqslant k$ $R\geqslant R^{*}$

Todiste. Olkoon ja valittu huippupiste algoritmisyklissä . Sitten todellinen eriarvoisuus on: ${\displaystyle V_{i}=\{v\in V\mid w(v)\cdot \operaattorin nimi {dist} (v,z_{i})\leqslant R^{*}\))$ ${\displaystyle z\in V_{i))$ $\operaattorin nimi {GreedyCenter}$

{\begin{aligned}w(v)\cdot \operaattorinimi {dist} (v,z)&\leqslant w(v)\cdot (\operaattorinimi {dist} (v,v_{i})+\ operaattorin nimi {dist} (v_{i},z))\\&\leqslant w(v)\cdot \operaattorinimi {dist} (v,v_{i})+w(z)\cdot \operaattorinimi {dist} ( v_{i},z)\\&\leqslant 2\cdot R^{*}\leqslant 2\cdot R\end{aligned}}

Kaikki pisteet kohteesta poistetaan iteroinnin lopussa, mikä tarkoittaa, että silmukka päättyy enintään iteraatioihin, ja siksi . $V_i$ $k=|Z^{*}|$ $|Z|\leqslant k$

Lemasta seuraa, että ahne algoritmia voidaan ajaa, kunnes tuloksena oleva joukko tulee vaadittua pienemmäksi , käyttämällä etäisyysmatriisia säteiden laskemiseen . Siten algoritmin yleinen aikamonimutkaisuus on , ja approksimaatiokerroin on . $Z$ $k$ $O(n^{4})$ $2$

Ratkaisevuus

Sillä ehdolla, että luokat P ja NP eivät ole yhtä suuret, millekään ei ole polynomialgoritmia, jolla on approksimaatiokerroin . Tämän väitteen todistus pelkistyy hallitsevan joukko-ongelman pelkistykseen : Annetaan se syötteeksi algoritmille, joka ratkaisee hallitsevan joukko-ongelman. Anna myös kaikki reunat . Sitten sisältää hallitsevan koon joukon, jos joukko sisältää pisteitä ja säde ( ) on yhtä suuri kuin . Jos olisi olemassa -approksimoiva algoritmi , niin se löytäisi hallitsevan joukon täsmälleen samalla approksimaatiokertoimella, mikä on mahdotonta. $r<2$ $r$ ${\näyttötyyli (G,k)}$ $c(e)=1$ $e\in E(G)$ $G$ $k$ $Z$ $k$ $\operaattorin nimi {rad} (Z)$ $yksi$ $r$ ${\mathcal {A}}$ $r<2$ ${\mathcal {A}}(G,1,k,c)$

Katso myös

Ongelma objektien sijoittamisesta etäisyyksien summan minimoimiseksi (alias "1-mediaanin ongelma") pistejoukon mediaanilla erikoistapauksena
Objektien maksimaalisen sijoittamisen ongelma (mahdollisimman haitallisten esineiden sijoittaminen)
K-keskuksen ongelma
K-mediaaniongelma

Muistiinpanot

Kirjallisuus

Nimrod Megiddo. Painotettu euklidinen 1-keskuksen ongelma // Operaatiotutkimuksen matematiikka. — Hannover: Operaatioiden tutkimus- ja hallintotieteiden instituutti. - T. 8 , no. 4 . — S. 498–504 . - doi : 10.1287/moor.8.4.498 .
Abdelaziz Foul. Yhden keskuksen ongelma koneessa tasaisesti jakautuneilla kysyntäpisteillä // Operations Research Letters. - Elsevier, 2006. - T. 34 , no. 3 . — S. 264–268 . - doi : 10.1016/j.orl.2005.04.011 .
R. Chandrasekaran. Painotettu euklidinen 1-keskuksen ongelma // Operations Research Letters. - Elsevier, heinäkuu 1982. - Vol. 1 , no. 3 . — S. 111–112 . - doi : 10.1016/0167-6377(82)90009-8 .
M. Colebrook, S. Alonso Gutierrez, J. Sicilia. Uusi algoritmi ei-toivotulle 1-keskuksen ongelmalle verkoissa // Journal of the Operational Research Society . - Palgrave Macmillan Journals, 2002. - V. 53 , no. 12 . - S. 1357-1366 . doi : 10.1057 / palgrave.jors.2601468 . — .
Rainer E. Burkard, Helidon Dollani. Huomautus vahvasta 1-keskuksen ongelmasta puissa // Annals of Operations Research. - Kluwer Academic Publishers, 2002. - T. 110 , no. 1-4 . — s. 69–82 . — ISSN 1572-9338 . - doi : 10.1023/A:1020711416254 .