Att förstå dynamiken i föränderliga sociala nätverk eller infrastrukturnät är en utmaning inom tillämpade områden som epidemiologi, viral marknadsföring eller stadsplanering. Under det senaste årtiondet har data samlats in på sådana nätverk men har ännu inte analyserats fullt ut. Vi föreslår att information om dynamiken i data för att hitta stabila partitioner av nätverket i grupper. För det ändamålet introducerar vi en tidsberoende, dynamisk version av anläggningens lokaliseringsproblem, som inkluderar en växlingskostnad när en kunds uppdrag ändras från en anläggning till en annan. Detta kan ge en bättre representation av ett växande nätverk, betona den plötsliga förändringen av relationer mellan ämnen snarare än den kontinuerliga utvecklingen av det underliggande nätverket. Vi visar att i realistiska exempel ger denna modell verkligen bättre passande lösningar än att optimera varje ögonblicksbild oberoende. Vi presenterar en O(log nT )-tillnärmning algoritm och en matchande hårdhet resultat, där n är antalet kunder och T antalet tidssteg. Vi ger också en annan algoritm med approximation förhållande O(log nT ) för den variant där man betalar vid varje gång steg (leasing) för varje öppen anläggning.
Eisenstat m.fl. REF studerade flerstegsversionen av anläggningslokaliseringsproblem för vilka de föreslog logaritmiska approximationsalgoritmer.
Facility Location in Evolving Metrics
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}