Submodulär funktion maximering är ett centralt problem i kombinatoriell optimering, generalisera många viktiga problem inklusive Max Cut i riktade / oriktade grafer och i hypergrafer, vissa begränsningar tillfredsställelse problem, maximal entropi provtagning, och maximal anläggning plats problem. Till skillnad från submodulär minimering är submodulär maximering NP-hård. I detta dokument, vi ger den första konstant-faktor approximation algoritm för att maximera någon icke-negativ submodulär funktion som omfattas av flera matris eller knapsack begränsningar. Vi betonar att våra resultat är för icke-monotona submodulära funktioner. I synnerhet, för varje konstant k, presenterar vi en "" 1 k+ - approximation för att maximera en monoton submodulär funktion under k ≥ 2 partition matroider, vilket förbättrar över den tidigare mest kända garantin på 1 k+1.
I inställningen av begränsad icke-monoton submodulär maximering, Lee et al. REF ger en 1/( + 2 + 1/ + ) approximation med matrisbegränsningar och en 1/( 5 - ) approximation för knapsackbegränsningar.
Non-monotone submodular maximization under matroid and knapsack constraints
{'venue': "STOC '09", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}