Vi undersöker prestandan av GREEDY algoritmen för kardinality begränsad maximisering av icke-submodulära icke-decreasing set funktioner. Även om det finns starka teoretiska garantier för prestanda hos GREEDY för att maximera submodulära funktioner, finns det få garantier för icke-submodulära funktioner. GREEDY har dock en stark empirisk prestanda för många viktiga icke-submodulära funktioner, t.ex. Bayesian A-optimalitetsmålet i experimentell design. Vi bevisar teoretiska garantier som stöder den empiriska prestationen. Våra garantier kännetecknas av (generaliserad) submodulitet förhållandet γ och (generaliserad) krökning α. I synnerhet bevisar vi att GREEDY har en snäv approximationsgaranti på 1 α (1 - e - γα ) för kardinalitetsbegränsad maximering. Dessutom band vi submodularitet förhållandet och krökning för flera viktiga verkliga mål, t.ex. Bayesian A-optimality mål, den avgörande funktionen av en kvadrat submatris och vissa linjära program med kombinatoriska begränsningar. Vi validerar experimentellt våra teoretiska resultat för flera verkliga tillämpningar.
Använda generaliserad submodulitetsförhållande och generaliserad krökning, REF härledd prestanda bundet för någon icke submodulär funktion.
Guarantees for Greedy Maximization of Non-submodular Functions with Applications
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}