Vi anser att problemet med att maximera en monoton submodulär funktion under en knapsack begränsning. Vi visar att det finns en polynom-tidsalgoritm med ett approximationsförhållande 1 − c/e −  och där c 0 [1] är (totalt) krökning av inmatningsfunktionen. Detta approximationsförhållande är tight upp till  på c [0, 1]. Såvitt vi vet är detta det första resultatet för en knapsackrestriktion som innehåller krökning för att uppnå ett approximationsförhållande som är bättre än 1 − 1/e, vilket är tight för allmänna submodulära funktioner. Som en tillämpning av vårt resultat presenterar vi en polynom-tidsalgoritm för budgettilldelningsproblem med en förbättrad approximationsgrad.
För en knapsackrestriktion visade Yoshida REF ett bättre approximationsförhållande på 1 – c/e.
Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}