Symmetriska submodulära funktioner är en viktig familj av submodulära funktioner som fångar många intressanta fall, inklusive skärfunktioner av grafer och hypergrafer. Maximering av sådana funktioner som är föremål för olika begränsningar får liten uppmärksamhet av aktuell forskning, till skillnad från liknande minimeringsproblem som har studerats vida omkring. I detta arbete identifierar vi några submodulära maximeringsproblem för vilka man kan få en bättre approximation för symmetriska mål än den senaste approximationen för allmänna submodulära funktioner. Vi först överväga problemet med att maximera en icke-negativ symmetrisk submodulär funktion f : 2 N → R + föremål för en dun-monoton solvable polytope P... [0, 1] N. För detta problem, beskriver vi en algoritm som producerar en fraktionerad lösning av värde minst 0.432 · f (OPT), där OPT är den optimala integrerade lösningen. Vårt andra resultat tar hänsyn till problemet max { f (S) :... = k} för en icke-negativ symmetrisk submodulär funktion f : 2 N → R +. För detta problem, ger vi ett approximationsförhållande som beror på värdet k/ på N och är alltid minst 0,432. Vår metod kan också tillämpas på icke-negativa icke-symmetriska submodulära funktioner, i vilket fall det producerar 1 /e - o(1) approximation, förbättra över det mest kända resultatet för detta problem. För okonstruerad maximering av en icke-negativ symmetrisk submodulär funktion beskriver vi en deterministisk linjär-tid 1 /2- approximationsalgoritm. Slutligen ger vi en [1 − (1 − 1/k) k−1 ] approximationsalgoritm för submodulär välfärd med k-spelare som har identiska icke-negativa submodulära allmännyttiga funktioner och visar att detta är bästa möjliga approximationsförhållande för problemet.
Denna lucka överbryggas något av ett resultat av att REF ger en 0.432-approximationsalgoritm för maximering av en särskild klass av icke-monotona submodulära funktioner, så kallade symmetriska submodulära funktioner, som är föremål för en allmän matrisrestriktion.
Maximizing Symmetric Submodular Functions
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}