Vi designar nya approximationsalgoritmer för problem med att optimera submodulära och supermodulära funktioner som är föremål för en enda matrisrestriktion. Specifikt anser vi att fallet där vi vill maximera en monoton ökande submodulär funktion eller minimera en monoton minskande supermodulär funktion med en begränsad total krökning c. Intuitivt representerar parametern 0 ≤ c ≤ 1 hur icke-linjär en funktion f är: när c = 0, f är linjär, medan för c = 1, f kan vara en godtycklig monoton ökande submodulär funktion. När det gäller submodulär maximering med total krökning c, får vi en (1 - c/ e)- approximation - den första förbättringen jämfört med den giriga (1 - e - c ) / c- approximering av Conforti och Cornuéjols från 1984, som innehar för en kardinalitet begränsning, samt en nyligen liknande resultat för en godtycklig matroid begränsning. Vår strategi är baserad på modifieringar av den kontinuerliga giriga algoritmen och icke-oblivious lokal sökning, och tillåter oss att ungefär maximera summan av en icke-negativ, monoton ökande submodulär funktion och en (eventuellt negativ) linjär funktion. Vi visar hur man kan minska både submodulär maximering och supermodulär minimering till detta allmänna problem när den objektiva funktionen har avgränsat total krökning. Vi bevisar att de approximativa resultat vi får är det bästa möjliga i värde orakelmodellen, även när det gäller en kardinalitetsbegränsning. Vi definierar en utvidgning av begreppet krökning till allmänna monotona uppsättningsfunktioner och visar en (1 - c) - approximation för maximering och en 1/ (1 - c) - approximation för minimeringsfall. Slutligen ger vi två konkreta tillämpningar av våra resultat i inställningarna för maximal entropi provtagning, och kolumn-subset urvalsproblem.
Sviridenko m.fl. REF förbättrade approximationsförhållandet till 1 − c f/e −  till en matrisrestriktion (och därmed en kardinalitetsrestriktion), som är ouppnåelig med c * f, och visade att approximationsförhållandet 1 − c f/e är tight även för en kardinalitetsrestriktion.
Optimal approximation for submodular and supermodular optimization with bounded curvature
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}