Vi anser att det är ett klassiskt k-center problem i träd. Låt T vara ett träd av n hörn och varje vertex har en icke-negativ vikt. Problemet är att hitta k centra på kanterna av T sådan att den maximala viktade avståndet från alla hörn till deras närmaste centra minimeras. Megiddo och Tamir (SIAM J. Comput., 1983) gav en algoritm som kan lösa problemet i O(n log 2 n) tid genom att använda Coles parametriska sökning. Sedan dess har det varit öppet i över tre decennier om problemet kan lösas i O(n log n) tid. I detta dokument presenterar vi en O(n log n) tid algoritm för problemet och därmed lösa det öppna problemet positivt. I denna uppsats studerar vi ett klassiskt k-center problem i träd. Låt T vara ett träd av n hörn. Varje kant e(u, v) förbinder två hörn u och v har en positiv längd d(u, v), och vi betraktar kanten som en linje segment av längd d(u, v) så att vi kan tala om "punkter" på kanten. För två punkter p och q av T, Det finns en unik väg i T från p till q, betecknad av π(p, q), och genom att något missbruka notationen, Vi använder d(p, q) för att beteckna längden av π(p, q). Varje vertex v av T är associerad med en vikt w(v) ≥ 0. K-center problemet är att beräkna en uppsättning Q av k punkter på T, kallas centra, sådan att den maximala viktade avståndet från alla hörn av T till sina närmaste centra minimeras, eller formellt, värdet max v och V (T ) min q.Q {w(v) · d(v, q)} minimeras, där V (T ) är vertex uppsättning av T. Observera att varje centrum kan vara i det inre av en kant av T. Kariv och Hakimi [20] först gav en O (n 2 log n) tid algoritm för problemet. Jeger och Kariv [19] föreslog en tidsalgoritm för O(kn log n). Megiddo och Tamir [25] löste problemet i O(n log 2 n log n) tid, och körtiden för deras algoritm kan reduceras till O(n log 2 n) genom att tillämpa Coles parametriska sökning [12]. Vissa framsteg har nyligen gjorts av Banik et al. [3], där en O(n log n+k log 2 n log(n/k))-tidsalgoritm och en annan O(n log n+k 2 log 2 (n/k))-tidsalgoritm gavs, och båda algoritmerna föredrar små värden av k. Sedan Megiddo och Tamirs arbete [25] har det varit öppet om problemet kan lösas i O(n log n) tid. I detta dokument löser vi detta tre-decenniens långa öppna problem positivt genom att presentera en O (n log n)-tidsalgoritm. Observera att den tidigare O(n log 2 n)-tidsalgoritmen [12, 25] och den första algoritmen [3] båda bygger på Coles parametriska sökning, vilket innebär en stor konstant i tid komplexitet på grund av AKS sorteringsnätverk [2]. Men vår algoritm undviker Coles parametriska sökning. Om varje centrum krävs för att vara lokaliserad en vertex av T, Sedan kallar vi det det diskret fall. Den tidigare mest kända algoritmen för detta fall körs i O(n log 2 n) tid [26]. Våra tekniker löser också det diskreta fallet i O(n log n) tid. Många variationer av k-centerproblemet har studerats. Om k = 1, då problemet kan lösas i O(n) tid [23]. Om T är en väg, K-center problemet var redan löst i O(n log n) tid [9, 12, 25], och Bhattacharya och Shi [4] gav också en algoritm vars körtid är linjär i n men exponentiell i k. För det oviktade fallet där hörn av T har samma vikt, en O(n 2 log n)-tid algoritm gavs i [8] för k-center problem. Senare, Megiddo et al. [26] löste problemet i O(n log 2 n) tid, och algoritmen förbättrades till O(n log n) tid [17]. Slutligen löste Frederickson [16] problemet på O(n) tid. Ovanstående fyra papper också lösa det diskreta fallet och följande problemversionen i samma körtider: Alla punkter i T anses som efterfrågepunkter och centra är skyldiga att vara på hörn av T. Vidare, om alla punkter i T är efterfrågepunkter och centra kan vara några punkter i T, Megiddo och Tamir löst problemet i O (n log 3 n) tid [25], och körtiden kan minskas till O (n log 2 n) genom att tillämpa Coles parametriska sökning [12]. Som relaterade problem, Frederickson [15] presenterade O(n)-tid algoritmer för följande träd partitionering problem: ta bort k kanter från T så att den maximala (resp., minimum) totalvikten av alla anslutna delträd minimeras (resp., maximerad). Att hitta k-centra i en allmän graf är NP-hård [20]. Den geometriska versionen av problemet i planet är också NP-hård [24], dvs. att hitta k-centra för n krävande punkter i planet. Vissa specialfall kan dock lösas i polynom tid. Om t.ex. k = 1, kan problemet lösas i O(n) tid [23], och om k = 2, kan det lösas i O(n log 2 n log 2 log n) tid [7] (även hänvisa till [1] för en snabbare randomiserad algoritm). Om vi kräver att alla centra ska vara på en given linje, då problemet med att hitta k centra kan lösas i polynom tid [5, 21, 27]. Nyligen har problem med osäkra data studerats i stor utsträckning och vissa k-centerproblemvariationer på osäkra data har också beaktats, t.ex. [13, 18, 28, 29, 30, 31].
Wang och Zhang REF gav nyligen en O (n log n) tidsalgoritm för problemet.
An O(n\log n)-Time Algorithm for the k-Center Problem in Trees
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}