Sammanfattning Problemet med att maximera icke-negativa submodulära monotona funktioner under en viss begränsning har studerats intensivt under det senaste årtiondet. I detta dokument, vi tar itu med problemet för funktioner som definieras över heltal lattice. Antag att en icke-negativ monoton submodulär funktion f : Z n + → R + ges via en utvärdering orakel. Anta vidare att f uppfyller den minskande returegendom, som inte är en omedelbar följd av submodulalitet när domänen är heltal lattice. Med tanke på detta designar vi polynom-tid (1 − 1/e −  på)-tillnärmningsalgoritmer för en kardinalitetsrestriktion, en polymatroidrestriktion och en knapsackrestriktion. För en kardinalitetsbegränsning tillhandahåller vi också en (1 −1/e −  med) approximationsalgoritm med något sämre tids komplexitet som inte är beroende av den minskande returegendomen.
På heltal lattice, Soma et al. REF studerade problemet med maximering av monotona DR-submodulära uttömmande, där de konstruerade algoritmer med (1 −1/e − ε) approximation under kardinalitet, polymatroid och knapsackrestriktion.
Maximizing Monotone Submodular Functions over the Integer Lattice
{'venue': None, 'journal': 'arXiv: Data Structures and Algorithms', 'mag_field_of_study': ['Mathematics', 'Computer Science']}