Ett antal senaste resultaten om optimeringsproblem som involverar submodulära funktioner har använt sig av "multilinjär avkoppling" av problemet [3], [8], [24], [14], [13]. Vi presenterar en allmän strategi för att härleda omätbarhet resulterar i värdet orakelmodellen, baserat på begreppet "symmetrigap". Vårt huvudsakliga resultat är att för varje fast instans som uppvisar en viss "symmetrigap" i sin multilinjära avkoppling, finns det en naturligt relaterad klass av instanser för vilka en bättre approximationsfaktor än symmetrigapet skulle kräva exponentiellt många orakelfrågor. Detta förenar flera kända hårdhetsresultat för submodulär maximering, t.ex. optimaliteten av (1 −1/e)-uppskattning för monoton submodulär maximering under en kardinalitetsbegränsning [20], [7], och omöjligheten av ( 1 2 + )-uppskattning för okonstruerad (icke-monoton) submodulal maximering [8]. Det följer av vårt resultat att ( 1 2 + )-uppskattning är också omöjligt för icke-monoton submodulär maximering föremål för en (icke-trivial) matroid begränsning. På den algoritmiska sidan presenterar vi en 0,309 approximation för detta problem, vilket förbättrar den tidigare kända faktorn 1 4 − o(1) [14]. Som en annan tillämpning, anser vi problemet med att maximera en icke-monoton submodulär funktion över baserna i en matroid. A ( 1 6 − o(1)) - approximation har utvecklats för detta problem, förutsatt att matroiden innehåller två olika baser [14]. Vi visar att den bästa approximationen man kan uppnå verkligen är relaterad till förpackningar av baser i matroiden. Specifikt, för varje k ≥ 2, det finns en klass av matriser av fraktionerad bas förpackningsnummer v = k‐1, sådan att någon algoritm som uppnår en bättre än (1 - 1 v ) - approximation för denna klass skulle kräva exponentiellt många värdefrågor. På den positiva sidan presenterar vi en 1 2 (1 - 1 v - o(1)) approximationsalgoritm för samma problem. Våra hårdhetsresultat håller i själva verket för mycket speciella symmetriska fall. För sådana symmetriska fall visar vi att approximationsfaktorerna 1 2 (för submodulär maximering som är föremål för en matrisrestriktion) och 1 - 1 v (för en matrisbasrestriktion) kan uppnås algoritmiskt och därmed är optimala.
Problemet med att maximera en (inte nödvändigtvis monoton) submodulär funktion som är föremål för en allmän matrisrestriktion gavs en 0,309-approximering i referens REF.
Symmetry and Approximability of Submodular Maximization Problems
{'venue': '2009 50th Annual IEEE Symposium on Foundations of Computer Science', 'journal': '2009 50th Annual IEEE Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}