En vanlig metod för att utforma skalbara algoritmer för massiva datamängder är att distribuera beräkningen över, säger k, maskiner och bearbeta data med hjälp av begränsad kommunikation mellan dem. En särskilt tilltalande ram här är den samtidiga kommunikationsmodellen där varje maskin konstruerar en liten representativ sammanfattning av sina egna data och man får en ungefärlig/exakt lösning från föreningen av de representativa sammanfattningarna. Om de representativa sammanfattningar som behövs för ett problem är små, då resulterar detta i ett kommunikationseffektivt och runda-optimalt (kräver i huvudsak ingen interaktion mellan maskinerna) protokoll. Några välkända exempel på tekniker för att skapa sammanfattningar inkluderar provtagning, linjär skissning och komposerbara kärnor. Dessa tekniker har framgångsrikt använts för att utforma kommunikationseffektiva lösningar för många grundläggande grafproblem. Två framträdande problem saknas dock särskilt i listan över framgångar, nämligen problemet med maximal matchning och problemet med minsta vertex-täckning. Det har nyligen visat sig att för båda dessa problem, även om man uppnår en blygsam approximationsfaktor för polylog(n) krävs det att man använder representativa sammanfattningar av storlek (n 2) d.v.s. I grund och botten finns det ingen bättre sammanfattning än att varje maskin helt enkelt skickar hela indatadiagrammet. Den huvudsakliga insikten i vårt arbete är att intractability av matchning och vertex cover i den samtidiga kommunikationsmodellen är i sig ansluten till en kontradiktorisk partitionering av den underliggande grafen över maskiner. Vi visar att när den underliggande grafen är slumpmässigt partitionerad över maskiner, båda dessa problem medger randomiserade komposerbara kärnor av storlek O (n) som ger en O (1)-ungefärlig lösning 1. Med andra ord, en liten del av indatagrafen vid varje maskin kan identifieras som dess representativa sammanfattning och det slutliga svaret sedan erhålls genom att helt enkelt köra någon maximal matchning eller minimum vertex täcka algoritm på dessa kombinerade subgrafer. Detta resulterar i en O (1)- approximation 1 Här och i hela papperet, använder vi O (·) notation för att undertrycka polylog(n) faktorer, där n är antalet hörn i diagrammet. Samtidigt protokoll för dessa problem med O (nk ) total kommunikation när inmatningen slumpmässigt delas upp över k maskiner. Vi visar också att våra resultat är optimala i en mycket stark bemärkelse: vi utesluter inte bara förekomsten av mindre randomiserade komposerbara kärnuppsättningar för dessa problem, utan visar i själva verket att vår O (nk ) som är knuten till total kommunikation är optimal för alla samtidiga kommunikationsprotokoll (d.v.s. inte bara för randomiserade kärnor) för dessa två problem. Slutligen innebär våra resultat också MapReduce algoritmer med samma approximation garanti i en eller två omgångar av kommunikation, vilket förbättrar den tidigare mest kända round komplexiteten för dessa problem.
Om utrymmet per maskin är Õ(n ε n), Assadi och Khanna REF visar hur man konstruerar en O(1)-ungefärlig maximal matchning och en O(log n)-ungefärlig minsta vertex täcka i två rundor.
Randomized Composable Coresets for Matching and Vertex Cover
{'venue': "SPAA '17", 'journal': None, 'mag_field_of_study': ['Computer Science']}