I detta dokument studerar vi adaptiviteten hos submodulär maximering. Adaptivitet kvantifierar antalet sekventiella rundor som en algoritm gör när funktionsutvärderingar kan utföras parallellt. Adaptivitet är ett grundläggande begrepp som studeras mycket inom en rad olika områden inom datavetenskap, till stor del på grund av behovet av parallellisering av beräkningar. För det kanoniska problemet att maximera en monoton submodulär funktion under en kardinalitetsbegränsning, är det väl känt att en enkel girig algoritm uppnår en 1 − 1/e approximation [NWF78] och att denna approximation är optimal för polynom-tid algoritmer [NW78]. Något överraskande, trots omfattande ansträngningar för submodulära optimering för storskaliga datauppsättningar, fram till helt nyligen fanns det ingen känd algoritm som uppnår en konstant faktor approximation för detta problem vars adaptivitet är sublinear i storleken på marken uppsättning n. Nyligen arbete av [BS18] beskriver en algoritm som får en approximation godtyckligt nära 1/3 i O(log n) adaptiva rundor och visar att ingen algoritm kan få en konstant faktor approximation inõ(log n) adaptiva rundor. Detta tillvägagångssätt leder till en exponentiellt snabbare anpassningsförmåga (och parallell körtid) på bekostnad av approximationskvaliteten. I detta dokument beskriver vi ett nytt tillvägagångssätt som ger en algoritm vars approximation är godtyckligt nära den optimala 1 − 1/e-garantin i O(log n) adaptiva rundor. Denna algoritm uppnår därför en exponentiell hastighetsökning i parallell drifttid för submodulär maximering på bekostnad av en godtyckligt liten förlust i approximationskvalitet. Denna garanti är optimal i både approximation och anpassningsförmåga, upp till lägre ordertermer.
Som en uppföljning postade de ett dokument om arXiv för att uppnå en (1 −1/e − ε)-uppskattning i O(log(n)) rundor REF för de submodulära monotonfunktionerna.
An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}