I detta dokument presenteras en distribuerad O(1)-tillnärmningsalgoritm, med förväntad O(log log n) körtid, i CON GE ST-modellen för den metriska anläggningens lokaliseringsproblem på ett size-n clique-nätverk. Även om metriska anläggningsplacering har övervägts av ett antal forskare i lågdiameter inställningar, är detta den första sub-logaritmisk-round algoritm för problemet som ger en O(1)-uppskattning i fastställandet av icke-uniforma anläggning öppningskostnader. För att uppnå detta resultat ger vårt dokument tre huvudsakliga tekniska bidrag. För det första visar vi en ny nedre gräns för metriska anläggningens läge, som utökar den nedre gränsen av B-doiu et al. (ICAP 2005) som endast gäller det särskilda fallet med enhetliga öppningskostnader. Därefter visar vi en minskning av problemet med distribuerad metriska anläggningsplats till problemet med att beräkna en O(1)-rulling uppsättning av en lämplig spännvidd subgraf. Slutligen presenterar vi en sub-logaritmisk-round (i förväntan) algoritm för att beräkna en 2-radig uppsättning i en spännande subgraf av en klick. Vår algoritm åstadkommer detta med hjälp av en kombination av randomiserad och deterministisk sparifiering.
Till exempel i en nyligen publicerad tidning av Berns m.fl. REF är en 2-radig uppsättning som beräknas som ett sätt att få en O(1)-faktor approximation till det metriska lokaliseringsproblemet för anläggningen.
Super-Fast Distributed Algorithms for Metric Facility Location
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}