En effektiv teknik för att lösa optimeringsproblem över massiva datamängder är att dela upp data i mindre bitar, lösa problemet på varje del och beräkna en representativ lösning från den, och slutligen få en lösning inom föreningen av representativa lösningar för alla bitar. Denna teknik kan fångas upp via konceptet komposerbara kärnuppsättningar, och har nyligen tillämpats för att lösa problem med mångfald maximering samt flera klusterproblem [7, 15, 8]. För täcknings- och submodulära maximeringsproblem är dock omöjlighetsgränser kända för denna teknik [15]. I detta dokument fokuserar vi på effektiv konstruktion av en randomiserad variant av komposerbara kärnuppsättningar där ovanstående idé tillämpas på en slumpmässig samling av data. Vi använder denna teknik för täckning, monoton och icke-monoton submodulära maximeringsproblem. Våra resultat förbättras avsevärt på hårdhetsresultaten för icke-randomiserade kärnuppsättningar, och innebär förbättrade resultat för submodulär maximering i en distribuerad och strömmande inställningar. Effektiviteten av denna teknik har bekräftats empiriskt för flera maskininlärning tillämpningar [22], och vårt bevis ger en teoretisk grund för denna idé. Sammanfattningsvis visar vi att en enkel girig algoritm resulterar i en 1/3-ungefärlig randomiserad komposerbar coreset för submodulär maximering under en kardinalitetsbegränsning. Vårt resultat sträcker sig också till icke-monotona submodulära funktioner, och leder till den första 2-runda MapReducebaserade konstant-faktor approximation algoritm med O(n) total kommunikations komplexitet för antingen monotona eller ickemonotona funktioner. Slutligen, med hjälp av en förbättrad analysteknik och en ny algoritm PseudoGreedy, presenterar vi en förbättrad 0,545-approximeringsalgoritm för monoton submodulär maximering, vilket i sin tur är den första MapReduce-baserade algoritmen slå faktor 1/2 i ett konstant antal rundor.
Slutligen gav Mirrokni och Zadimoghaddam REF den för närvarande bästa 0,545- approximationen för kardinalitetsbegränsning fallet med endast 2 rundor MapReduce.
Randomized Composable Core-sets for Distributed Submodular Maximization
{'venue': "STOC '15", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}