1-center problem

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 8 mars 2017; verifiering kräver 1 redigering .

1- centerproblemet eller minimax-objektplaceringsproblemet är ett klassiskt kombinatoriskt optimeringsproblem , ett problem inom disciplinen operationsforskning , är ett specialfall av objektplaceringsproblemet . I det mest allmänna fallet är det formulerat enligt följande:

En uppsättning konsumentplatser, ett utrymme av möjliga platser för objekt (produktion eller tjänst) och en funktion av kostnaden för transport från vilken plats som helst på möjlig plats till konsumtionspunkten ges Det är nödvändigt att hitta den optimala platsen för objekt, vilket minimerar den maximala kostnaden för leverans från objektet till konsumenten.

Ett enkelt specialfall där boenden och konsumtionsställen finns på ett plan och leveranskostnaden är det euklidiska avståndet ( planar minimax euklidiskt placeringsproblem, euklidiskt 1-centrumplansproblem ) är också känt som det minsta cirkelproblemet . Dess generalisering till högre dimensionella euklidiska utrymmen är känd som det minst gränsande sfärproblemet . I en ytterligare generalisering ( vägt euklidiskt lokaliseringsproblem ) tilldelas vikter till konsumtionspunkter och transportkostnaden är summan av avstånden multiplicerat med motsvarande vikter. Ett annat specialfall är problemet med den närmaste linjen , när indata för problemet är strängen och avståndet mäts som Hamming-avståndet .

Det finns många specialfall av problemet, beroende både på valet av placering av konsumtionsställen och produktions- (eller service) objekt, och på valet av en funktion som beräknar avståndet.

1-centerproblemet i termer av grafteori

Formuleringen av en sådan variant av problemet ligger i det faktum att en graf ges , såväl som en kostnadsfunktion, och det är nödvändigt att hitta en mängd så att den är minimal, d.v.s. en uppsättning så att den maximala kostnaden för en väg från det hörn som är närmast någon vertex förblir minimal. Problemet kan också kompletteras med vertexkostnadsfunktionen, och då kommer radien för det att definieras som . $G=(V,E)$ $k\in {\mathbb {N}}$ ${\displaystyle c\colon E\to \mathbb {Q} ^{+))$ $Z\subset V$ $\operatorname {rad} (Z)=\max _{v\in V}\min _{z\in Z}c(z,v)$ $Z$ $Z$ ${\displaystyle w\colon V\to \mathbb {Q} ^{+))$ $\operatorname {rad} (Z)=\max _{v\in V}[w(v)\cdot \min _{z\in Z}c(z,v)]$

Tanken med en ungefärlig lösning på problemet är att söka med en girig algoritm efter en fast radie . Så länge det finns hörn som inte täcks av måste man girigt välja en vertex och överväga alla andra tillgängliga hörn . Algoritmen upprepas för olika värden på . Följande är en beskrivning av metoden i formell form: $Z$ $R$ $Z$ $z$ $2R$ $R$

Installera och . $Z=\emptyset$ $U=V$
Hejdå : $U\neq \emptyset$
1. ${\displaystyle z=\operatörsnamn {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 \operatörsnamn {avstånd} (v,z)\leqslant 2R\))$ .
Ta fram . $Z$

Låt vara den optimala lösningen för . I fallet när kommer den giriga algoritmen att returnera en uppsättning sådan att . Utifrån detta definierar vi och noterar att funktionen inte är monoton . Därefter betecknar vi radien , med hjälp av vilken endast en vertex in kan täcka alla hörn i grafen, d.v.s. , a . $R^{*}$ $Z^*$ $R\geqslant R^{*}$ $Z$ $|Z|\leqslant |Z^{*}|$ $f(R)=|\operatörsnamn {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. För varje graf med en optimal uppsättning och radie gäller olikheten för alla . $G=(V,E)$ $Z^*$ $R^{*}=\operatörsnamn {rad} (Z^{*})$ $f(R)\leqslant k$ $R\geqslant R^{*}$

Bevis. Låt och vara det valda hörnet i algoritmcykeln . Då är den verkliga ojämlikheten: ${\displaystyle V_{i}=\{v\in V\mid w(v)\cdot \operatörsnamn {avstånd} (v,z_{i})\leqslant R^{*}\))$ ${\displaystyle z\in V_{i))$ $\operatörsnamn {GreedyCenter}$

{\begin{aligned}w(v)\cdot \operatörsnamn {dist} (v,z)&\leqslant w(v)\cdot (\operatörsnamn {dist} (v,v_{i})+\ operatörsnamn {avstånd} (v_{i},z))\\&\leqslant w(v)\cdot \operatörsnamn {avstånd} (v,v_{i})+w(z)\cdot \operatörsnamn {avstånd} ( v_{i},z)\\&\leqslant 2\cdot R^{*}\leqslant 2\cdot R\end{aligned}}

Alla hörn från kommer att tas bort i slutet av iterationen, vilket innebär att slingan kommer att sluta i maximalt antal iterationer, och därför . $V_i$ $k=|Z^{*}|$ $|Z|\leqslant k$

Det följer av lemmat att den giriga algoritmen kan köras tills den resulterande mängden blir mindre än den som krävs , med hjälp av avståndsmatrisen för att beräkna radierna . Således är den totala tidskomplexiteten för algoritmen , och approximationsfaktorn är . $Z$ $k$ $O(n^{4})$ $2$

Lösbarhet

Under förutsättning att klasserna P och NP inte är lika, för alla finns det ingen polynomalgoritm med en approximationsfaktor . Beviset för detta påstående reduceras till en reduktion till det dominerande mängdproblemet : Låt det ges som input till algoritmen som löser det dominerande mängdproblemet. Låt även för alla kanter . Innehåller sedan en dominerande mängd storlek om mängden innehåller hörn och radien ( ) är lika med . Om det fanns en -approximationsalgoritm med , då skulle den hitta en dominant uppsättning med exakt samma approximationsfaktor, vilket är omöjligt. $r<2$ $r$ $(G,k)$ $c(e)=1$ $e\in E(G)$ $G$ $k$ $Z$ $k$ $\operatörsnamn {rad} (Z)$ $ett$ $r$ ${\mathcal {A}}$ $r<2$ ${\mathcal {A}}(G,1,k,c)$

Se även

Problemet med att placera objekt med minimering av summan av avstånd (aka "Problemet med 1-median") med medianen för uppsättningen av punkter som ett specialfall
Problemet med att maximera placeringen av föremål (så långt som möjligt, placering av skadliga föremål)
K-centerproblemet
K-medianproblemet

Anteckningar

Litteratur

Nimrod Megiddo. Det viktade euklidiska 1-centerproblemet // Mathematics of Operations Research. — Hannover: Institutet för operationsforskning och managementvetenskap. - T. 8 , nej. 4 . — S. 498–504 . - doi : 10.1287/moor.8.4.498 .
Abdelaziz Ful. Ett 1-centerproblem på planet med enhetligt fördelade kravpunkter // Operations Research Letters. - Elsevier, 2006. - T. 34 , nr. 3 . — S. 264–268 . - doi : 10.1016/j.orl.2005.04.011 .
R. Chandrasekaran. Det viktade euklidiska 1-centerproblemet // Operations Research Letters. - Elsevier, juli 1982. - Vol. 1 , nr. 3 . — S. 111–112 . - doi : 10.1016/0167-6377(82)90009-8 .
M. Colebrook, S. Alonso Gutierrez, J. Sicilia. En ny algoritm för det oönskade 1-centerproblemet i nätverk // Journal of the Operational Research Society . - Palgrave Macmillan Journals, 2002. - V. 53 , nr. 12 . - S. 1357-1366 . doi : 10.1057 / palgrave.jors.2601468 . — .
Rainer E. Burkard, Helidon Dollani. En anteckning om det robusta 1-centerproblemet om träd // Annals of Operations Research. - Kluwer Academic Publishers, 2002. - T. 110 , nr. 1-4 . — s. 69–82 . — ISSN 1572-9338 . - doi : 10.1023/A:1020711416254 .