Abstract Submodulära funktioner är ett nyckelbegrepp i kombinatoriell optimering. Algoritmer som inbegriper submodulära funktioner förutsätter vanligtvis att de ges av ett (värde) orakel. Många intressanta problem med submodulära funktioner kan lösas med hjälp av endast polynomialt många frågor till oraklet, t.ex., exakt minimering eller ungefärlig maximering. I detta dokument överväger vi problemet med att tillnärma en icke-negativ, monoton, submodulär funktion f på en markuppsättning av storlek n överallt, efter endast poly(n) oracle frågor. Vårt huvudsakliga resultat är en deterministisk algoritm som gör poly(n) oracle frågor och härleder en funktionf sådan att, för varje uppsättning S, f (S) approximerar f (S) inom en faktor α(n), där α(n) = ε n + 1 för rank funktioner av matroider och för allmänna monotona submodulära funktioner. Vårt resultat är baserat på ungefär att hitta en maximal volym inskriven ellipsoid i en symfoniiserad polymatroid, och analysen omfattar olika egenskaper hos submodulära funktioner och polymatroider. Vår algoritm är nära logaritmiska faktorer. I själva verket visar vi att ingen algoritm kan uppnå en faktor som är bättre än  och som är bättre än  och som är bättre än  och som är lika med n/ log n, inte ens för rangfunktioner hos en matris.
Goemans m.fl. REF beaktade problemet med hur väl en given monoton submodulär funktion f kan approximeras när endast polynomiskt många värde orakelfrågor är tillåtna.
Approximating Submodular Functions Everywhere
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}