On additive approximate submodularity

DOI10.1016/j.tcs.2022.04.035OpenAlexW3092131767MaRDI QIDQ2672599

Ravi Kumar, Anirban Dasgupta, Flavio Chierichetti

Publication date: 13 June 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2010.02912

zbMATH Keywords

approximationsubmodular functionsHyers-Ulam theory

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Is submodularity testable?
• On submodular function minimization
• The ellipsoid method and its consequences in combinatorial optimization
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On concentrators and related approximation constants
• Submodular functions and optimization.
• Uniformly Exhaustive Submeasures and Nearly Additive Set Functions
• Maximizing Non-monotone Submodular Functions
• A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• On Testing Convexity and Submodularity
• Approximate modularity revisited
• When Are Welfare Guarantees Robust
• Learning with Submodular Functions: A Convex Optimization Perspective
• Learning submodular functions
• Approximately Convex Functions
• Remarks on the stability of functional equations

This page was built for publication: On additive approximate submodularity