Vi studerar sändningsversionen av CONGEST-CLIQUE modellen för distribuerad dator [8, 22, 25]. I den här modellen, i varje omgång, kan vilken nod som helst i ett nätverk av storlek n skicka samma meddelande (dvs. Sända ett meddelande) av begränsad storlek till varje annan nod i nätverket. Nanongkai presenteras i [STOC'14 [25]] en randomiserad (2 + o(1)) - approximation algoritm för att beräkna alla par kortaste vägar (APSP) i tid 1Õ ( ε n) på vägda grafer. Vi kompletterar detta resultat genom att bevisa att en slumpmässig (2 − o(1)) - approximation av APSP och (2 − o(1)) - approximation av diametern på en graf tar en (n) tid i värsta fall. Detta visar att det krävs betydligt mer tid för att uppnå en försumbar förbättring av approximeringsfaktorn. Dessutom innebär denna gräns att redan datorisering av en (2 − o(1))-uppskattning av alla par kortaste vägar är bland de svåraste graf-problemen i sändning-version av CONGEST-CLIQUE-modellen. Detta är sant eftersom alla graf-problem kan lösas trivialt i linjär tid i denna modell och kontrasterar en nyligen (1 + o(1))-uppskattning för APSP som körs i tiden O(n 0,15715 ) och en exakt algoritm för APSP som körs i tid Õ(n 1/3 )) i den unicast versionen av den CONGEST-CLIQUE modellen [3, 17]. Denna nedre gräns i CONGEST-CLIQUE-modellen härleds genom att först upprätta en ny nedre gräns för (2 – o(1)) ungefärlig diameter i viktade grafer i CONGEST-modellen, som är av oberoende intresse. Denna nedre gräns överförs sedan till CONGEST-CLIQUE-modellen. På den positiva sidan ger vi en deterministisk version av Nanongkais (2+o(1)) approximationsalgoritm för APSP [25]. För att göra det presenterar vi en snabb deterministisk konstruktion av små slaguppsättningar. Vi visar också hur man ersätter en annan randomiserad del i Nanongkais algoritm med en deterministisk källdetekteringsalgoritm avsedd för CONGEST-modellen [20].
I denna modell, är det känt att få en (2 - o(1)) - approximation för APSP kräver  på (n) rundor REF, som är nästan tight.
Approximation of Distances and Shortest Paths in the Broadcast Congest Clique
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}