I detta dokument överväger vi parallellisering för tillämpningar vars syfte kan uttryckas som maximering av en icke-monoton submodulär funktion under en kardinalitetsbegränsning. Vårt huvudsakliga resultat är en algoritm vars approximation är godtyckligt nära 1/2e i O(log 2 n) adaptiva rundor, där n är storleken på marken uppsättning. Detta är en exponentiell upphastighet i parallell drifttid över någon tidigare studerade algoritm för begränsad icke-monoton submodulär maximering. Utöver de bevisbara garantierna fungerar algoritmen bra i praktiken. Speciellt, experiment på trafikövervakning och personliga datasammanfattning applikationer visar att algoritmen hittar lösningar vars värden är konkurrenskraftiga med toppmoderna algoritmer medan kör i exponentiellt färre parallella iterationer.
I REF föreslogs en 1 2e - approximationsalgoritm med O(log 2 n) adaptiva rundor.
Non-monotone Submodular Maximization in Exponentially Fewer Iterations
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}