Motiverad av tillämpningar i leveranskedjan, nätverkshantering och maskininlärning, har en stadig ström av forskning ägnats åt att studera olika beräkningsaspekter av den beställda k-median problem, som subsumerar traditionella anläggnings lokaliseringsproblem (såsom median, center, p-centrum, etc.) genom en enhetlig modelleringsmetod. Med tanke på ett ändligt metriska utrymme är målet att lokalisera k-anläggningar för att minimera den beställda mediankostnadsfunktionen. I sin allmänna form straffar denna funktion täckningsavståndet för varje vertex med en multiplikativ vikt, beroende på dess ranking (eller percentil) i den beställda listan över alla täckningsavstånd. Medan tidigare litteratur har fokuserat på matematiska egenskaper av beställda medianfunktioner, heltal programmeringsmetoder, olika heuristik, och specialfall, detta problem har inte studerats hittills genom linsen av approximation algoritmer. I synnerhet är det en öppen fråga att få icke-triviala approximativa garantier, även om det rör sig om enkla topologier på nätet, t.ex. träd eller linjediagram. Det viktigaste bidraget i detta dokument är att ta fram de första bevisligen bra approximationsalgoritmerna för det beställda k-medianproblemet. Vi utvecklar ett nytt tillvägagångssätt som främst bygger på en surrogatmodell, där den beställda medianfunktionen byts ut mot en förenklad ranknings-invariant funktionell form, genom effektiv uppräkning. Förvånansvärt nog får vi en O(log n) approximation för vårt ursprungliga problem genom att använda lokala sökmetoder på en smidig variant av surrogatfunktionen, medan denna surrogatmodell är svår att approximera på allmänna mätvärden. Dessutom erhålls en förbättrad garanti på 2 + på trädmått genom att optimalt lösa surrogatmodellen genom dynamisk programmering. Slutligen visar vi att den senare optimalitetsklyftan är snäv upp till en O( ) term. Motiverad av tillämpningar i leveranskedjan, nätverkshantering och maskininlärning [36, 35, 8, 38] har det beställda k-medianproblemet utvecklats under de senaste två decennierna som en robust och enhetlig strategi för anläggningens läge. I denna inställning, vi ges en ändlig metriska utrymme (V, d) på n hörn, en sekvens av straffvikter λ 1 ≥ · · ≥ λ n ≥ 0, och ett heltal parameter k. För varje uppsättning anläggningar F  på V, den beställda mediankostnad funktion straffar avståndet d (v, F) av varje vertex v  på sin närmaste anläggning med en multiplikativ vikt, beroende på dess ranking (eller percentil) i den beställda listan över alla täckningsavstånd. För att formalisera detta kriterium, för varje rankning i  på [n], låt  på F (i) vara den i-th största avståndet ut ur {d(v, F) : v  på V }, bryta band godtyckligt. Sedan är det största avståndet  och F (1) straffas av λ 1, det näst största avståndet  och F (2) straffas av λ 2, så vidare och så vidare, säkerställa att högre rankade hörn bestraffas hårdare än lägre rankade. Följaktligen är målet att beräkna en uppsättning F  på de flesta k anläggningar som minimerar den beställda mediankostnad funktion: Förhållande till grundläggande modeller. Den beställda medianramen utvecklar ett enhetligt och standardiserat tillvägagångssätt till ett brett spektrum av anläggningslokaliseringsproblem, där kostnadsfunktionen uttrycks i allmän form, tillämpa godtyckliga straffvikter beroende på percentil rangen av täckningsavstånd. Denna modellering ram subsumes några av de mest grundläggande objektiva funktioner i lokaliseringsteori [11, 23, 3, 29, 9, 22, 48, 49], såsom: • k-median, som minimerar den genomsnittliga avståndet till närmaste anläggning, fångas genom inställning (λ 1,. .., λ n ) = (1,..., 1). • k-center, som minimerar maximal täckning avstånd, med (λ 1,. ., λ n ) = (1, 0,..., 0). • k-centdian, som generaliserar konvexa kombinationer av k-median och k-center. • k-facilitet p-centrum, vilket minimerar summan av p-största täckningsavstånd, med λ 1 = · · · = λ p = 1 och λ p+1 = · · · = λ n = 0. I sin största generalitet gör den beställda medianfunktionen att man kan formulera en kontinuum av kompromisser mellan k-median- och k-centermodellerna (se t.ex. [37, Chap. 1]), där yttre hörn bestraffas enligt deras percentil rank. För en fördjupad diskussion om teori och tillämpningar av anläggningsplaceringsmodeller hänvisar vi läsaren till böcker om detta allmänna ämne [34, 13] samt till de som är särskilt avsedda för beställda medianmodeller [27, 37]. Beräkningsutmaningar. Modelleringskraften som diskuteras ovan utgör ytterligare tekniska hinder, jämfört med specialiserade mål som k-median och k-center, som är kända för att medge approximationer med konstant faktor [11, 23, 3, 29, 9, 22]. Den första utmaningen beror på beroendet av den beställda mediankostnadsfunktionen på den relativa avståndsrankningen. Till exempel, på grund av bristen på tydliga särskiljande egenskaper [45], även på trädmått eller linjediagram
Den första bevisbara approximationsalgoritmen för Ordered k-Median föreslogs av REF, och de gav 2 approximation för träd och O(log n)-uppskattning för allmänna mätvärden.
The ordered k-median problem: surrogate models and approximation algorithms
{'venue': None, 'journal': 'Mathematical Programming', 'mag_field_of_study': ['Computer Science', 'Mathematics']}