Vi introducerar flera generaliseringar av klassiska datavetenskapliga problem som erhållits genom att ersätta enklare objektiva funktioner med allmänna submodulära funktioner. De nya problemen inkluderar submodulär lastbalansering, som generaliserar lastbalansering eller minimal-makespan schemaläggning, submodulära glesaste snitt och submodulära balanserade snitt, som generaliserar deras respektive graf skär problem, liksom submodulär funktion minimering med en kardinalitet lägre gräns. Vi etablerar övre och nedre gränser för tillnärmningen av dessa problem med ett polynom antal frågor till ett funktionsvärde orakel. Den approximativa garantier för de flesta av våra algoritmer är av ordningen n/ln n. Vi visar att detta är den inneboende svårigheten med problemen genom att bevisa att matcha lägre gränser. Vi ger också en förbättrad lägre gräns för problemet med att ungefär lära sig en monoton submodulär funktion. Dessutom presenterar vi en algoritm för ungefär lärande submodulära funktioner med speciell struktur, vars garanti ligger nära den nedre gränsen. Även om den är ganska restriktiv, omfattar den klass av funktioner med denna struktur de som används för lägre gränser både av oss och i tidigare arbete. Detta visar att om det finns betydligt starkare lägre gränser för detta problem, de förlitar sig på mer allmänna submodulära funktioner.
Konstruerad submodulär minimering är mycket svårare - även med enkla begränsningar såsom en kardinalitet lägre bundna begränsningar, problemen är inte approximerbar bättre än en polynomial faktor av  och ( ε n) REF.
Submodular Approximation: Sampling-based Algorithms and Lower Bounds
{'venue': '2008 49th Annual IEEE Symposium on Foundations of Computer Science', 'journal': '2008 49th Annual IEEE Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}