Vi ger algoritmer för geometriska grafproblem i de moderna parallella modellerna som MapReduce. Till exempel, för minsta Spanning Tree (MST) problem över en uppsättning punkter i det tvådimensionella utrymmet, vår algoritm beräknar en (1 + )-ungefärlig MST. Våra algoritmer fungerar i ett konstant antal omgångar av kommunikation, samtidigt som vi använder totalt utrymme och kommunikation proportionellt mot storleken på data (linjärt utrymme och nära linjär tid algoritmer). Däremot, för allmänna grafer, att uppnå samma resultat för MST (eller även anslutning) är fortfarande ett utmanande öppet problem [9], trots att dra betydande uppmärksamhet under de senaste åren. Vi utvecklar en allmän algoritmisk ram som förutom MST även gäller för Earth-Mover Distance (EMD) och transportkostnadsproblemet. Vårt algoritmiska ramverk har konsekvenser bortom MapReduce-modellen. Till exempel ger det en ny algoritm för beräkning av EMD kostnad i planet i nära-linjär tid, n 1+o (1). Vi noterar att medan nyligen [33] har utvecklat en näralinjär tidsalgoritm för (1 + )-ungefärande EMD, vår algoritm är i grunden annorlunda, och, till exempel, också löser transport (kostnad) problem, tas upp som en öppen fråga i [33]. Dessutom ger vår algoritm omedelbart en (1+ ) approximationsalgoritm med n δ utrymme i streamingwith-sortering modell med 1/δ O(1) passerar. Som sådan är det frestande att anta att de parallella modellerna också kan utgöra en konkret lekplats i sökandet efter effektiva algoritmer för EMD (och andra liknande problem) i vanilj streaming modellen, ett välkänt öppet problem.
I REF, Andoni et al. utvecklade en ungefärlig algoritm för att approximera minsta spännviddsträd och jordskredsavstånd för geometriska grafer (kompletterade viktade grafer för punkter i geometriskt utrymme).
Parallel algorithms for geometric graph problems
{'venue': "STOC '14", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}