Praktische und parallelisierbare Algorithmen für die nicht-monotone submodulare Maximierung mit Größenbeschränkung

Wir präsentieren kombinatorische und parallelisierbare Algorithmen zur Maximierung einer submodularen Funktion, die nicht unbedingt monoton ist, hinsichtlich einer Größenbeschränkung. Wir verbessern den besten Annäherungsfaktor, der von einem Algorithmus erreicht wurde, der optimale Anpassungsfähigkeit und nahezu optimale Abfragekomplexität hat, auf 1/6 − ε und sogar weiter auf 0,193 − ε, indem wir die Anpassungsfähigkeit um einen Faktor von O(log(k)) erhöhen. Die Konferenzversion dieser Arbeit verwendete fälschlicherweise eine Unterroutine, die nicht für nicht-monotone, submodulare Funktionen funktioniert. In dieser Version schlagen wir eine feste und verbesserte Unterroutine vor, um eine Menge mit hohem durchschnittlichem Grenzgewinn, ThreshSeq, hinzuzufügen, die mit hoher Wahrscheinlichkeit eine Lösung in O(log(n)) adaptiven Runden zurückgibt. Darüber hinaus bieten wir zwei Annäherungsalgorithmen an. Der erste hat ein Annäherungsverhältnis von 1/6 − ε, Anpassungsfähigkeit O(log(n)) und Abfragekomplexität O(n log(k)), während der zweite ein Annäherungsverhältnis von 0,193 − ε, Anpassungsfähigkeit O(log(n) log(k)) und Abfragekomplexität O(n log(k)) hat. Unsere Algorithmen wurden empirisch validiert, um eine geringe Anzahl an adaptiven Runden und Gesamtabfragen zu verwenden und währenddessen Lösungen mit hohem Objektivwert im Vergleich zu modernen Annäherungsalgorithmen zu erhalten, einschließlich kontinuierlicher Algorithmen, die die mehrdimensionale Erweiterung nutzen.