I detta dokument anser vi att problemet med submodulär maximering är oöverskådligt. Vi föreslår den första algoritmen för detta problem som uppnår en tight (1/2 − ε)-tillnärmningsgaranti med hjälp av Õ(ε −1 ) adaptiva rundor och ett linjärt antal funktionsutvärderingar. Ingen tidigare känd algoritm för detta problem uppnår ett approximationsförhållande bättre än 1/3 genom att använda mindre än  och (n) rundor av adaptivitet, där n är storleken på markuppsättningen. Dessutom sträcker sig vår algoritm enkelt till att maximera en icke-negativ kontinuerlig DR-submodulär funktion som är föremål för en låda begränsning, och uppnår en tight (1/2 − ε)-tillnärmning garanti för detta problem samtidigt som samma adaptiva och frågekomplex.
REF övervägde det okonstruerade submodulära maximeringsproblemet och föreslog den första algoritmen som uppnår den optimala approximationsgarantin i ett konstant antal adaptiva rundor.
Unconstrained submodular maximization with constant adaptive complexity
{'venue': 'STOC 2019', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}