Effiziente deterministische Algorithmen zur Maximierung symmetrischer submodularer Funktionen

Die symmetrische submodulare Maximierung ist eine wichtige Klasse von kombinatorischen Optimierungsproblemen, einschließlich MAX-CUT auf Graphen und Hypergraphen. Der derzeit beste Algorithmus für das Problem unter allgemeinen Nebenbedingungen hat ein Approximationsverhältnis von 0,432. Der Algorithmus nutzt die kanonische kontinuierliche gierige Technik, die einen Sampling-Prozess beinhaltet. Daher leidet er unter hoher Abfragekomplexität und ist grundsätzlich randomisiert. In diesem Papier stellen wir mehrere effiziente deterministische Algorithmen zur Maximierung einer symmetrischen submodularen Funktion unter verschiedenen Nebenbedingungen vor. Insbesondere für die Kardinalitätsbeschränkung entwerfen wir einen deterministischen Algorithmus, der ein Verhältnis von 0,432 erreicht und O(kn) Abfragen verwendet. Zuvor erreichte der beste deterministische Algorithmus ein Verhältnis von 0,385 und verwendete O(kn(10^9)^{20{9-1}}) Abfragen. Für die Matroidbeschränkung entwerfen wir einen deterministischen Algorithmus, der ein Verhältnis von 1/3 erreicht und O(kn^{-1}) Abfragen verwendet. Zuvor konnte der beste deterministische Algorithmus ebenfalls ein Verhältnis von 1/3 erreichen, verwendete aber deutlich größere O(n^{-4}) Abfragen. Für die Verpackungsbeschränkungen mit großer Breite entwerfen wir einen deterministischen Algorithmus, der ein Verhältnis von 0,432 erreicht und O(n²) Abfragen verwendet. Soweit wir wissen, gibt es zuvor keinen deterministischen Algorithmus für diese Einschränkung. Der letzte Algorithmus kann angepasst werden, um ein Verhältnis von 0,432 für die Einzelknapsack-Beschränkung mit O(n⁴) Abfragen zu erreichen. Zuvor erreichte der beste deterministische Algorithmus ein Verhältnis von 0,316 und verwendete O(n³) Abfragen.