1-center problem

1-centerproblemet , även känt som minimaxproblem eller minmaxlokaliseringsproblem , är ett klassiskt kombinatoriskt optimeringsproblem i operationsforskning av lokaliseringstyp av anläggningar . I sitt mest generella fall anges problemet enligt följande: givet en uppsättning av n behovspunkter, ett utrymme av möjliga platser för en anläggning och en funktion för att beräkna transportkostnaden mellan en anläggning och en valfri behovspunkt, hitta en plats för anläggningen vilket minimerar den maximala kostnaden för transport av anläggningar efter behov.

Det finns många speciella fall av problemet, beroende på valet av platser både av efterfrågepunkter och faciliteter, såväl som avståndsfunktionen.

Ett enkelt specialfall är när de genomförbara platserna och behovspunkterna finns i planet med euklidiskt avstånd som transportkostnad ( planar minmax euklidiska anläggningsplatsproblem, euklidiskt 1-centerproblem i planet, etc.). Det är också känt som det minsta cirkelproblemet . Dess generalisering till n -dimensionella euklidiska rum är känt som det minsta problemet med omslutande boll . En ytterligare generalisering ( vägd euklidisk anläggningsplats ) är när uppsättningen vikter tilldelas efterfrågepunkter och transportkostnaden är summan av produkterna av avstånd med motsvarande vikter. Ett annat specialfall, det närmaste strängproblemet , uppstår när ingångarna är strängar och deras avstånd mäts med Hamming-avstånd .

1-centerproblemet kan omformuleras som att hitta en stjärna i en viktad komplett graf som minimerar den maximala vikten för de valda kanterna. Motsvarande problem med att minimera den maximala vikten av en väg mellan två utvalda hörn, i stället för en stjärna, kallas minimaxvägproblemet .

• Megiddo, Nimrod (november 1983). "Det viktade euklidiska 1-centerproblemet" (PDF) . Operationsforskningens matematik . 8 (4): 498–504. doi : 10.1287/moor.8.4.498 .
• Fel, Abdelaziz (maj 2006). "Ett 1-centerproblem på planet med jämnt fördelade kravpunkter". Operations Research Letters . Elsevier. 34 (3): 264–268. doi : 10.1016/j.orl.2005.04.011 .
• Chandrasekaran, R. (juli 1982). "Det viktade euklidiska 1-centerproblemet". Operations Research Letters . Elsevier. 1 (3): 111–112. doi : 10.1016/0167-6377(82)90009-8 .
•   Colebrook, M.; J. Gutiérrez, S. Alonso; J. Sicilia (december 2002). "En ny algoritm för det oönskade 1-centerproblemet i nätverk". Journal of the Operational Research Society . Palgrave Macmillan Journals. 53 (12): 1357–1366. doi : 10.1057/palgrave.jors.2601468 . JSTOR 822725 .
•   Burkard, Rainer E.; Helidon Dollani (februari 2002). "En anteckning om det robusta 1-centerproblemet på träd". Annals of Operations Research . Kluwer Academic Publishers. 110 (1–4): 69–82. doi : 10.1023/A:1020711416254 . ISSN 1572-9338 .

Se även

• Minsum anläggningens läge ( 1-medianproblem ), med geometrisk median som ett specialfall
• Maxmin anläggningens plats ( motbjudande anläggningens plats )
• k-center problem
• k-medianproblem