2019/01/26 by Temitayo Ajayi, Ajayi, Temitayo, Taewoo Lee +3
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #FOS: Mathematics #Optimization and Control (math.OC) #Smart Parking Systems Research
paper · pdf · doi:10.48550/arxiv.1901.09209
openalex publication_date 2019/01/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Submodularity is a key property in discrete optimization. Submodularity has been widely used for analyzing the greedy algorithm to give performance bounds and providing insight into the construction of valid inequalities for mixed-integer programs. In recent years, researchers started to study approximate submodularity, with a primary focus on providing performance bounds for iterative approaches. In this paper, we study approximate submodularity from a different perspective in order to broaden its use cases in discrete optimization. We define metrics that quantify approximate submodularity, which we then use to derive new properties about both approximate submodularity preservation and the well-known Lovász extension for set functions. We also show that previous analyses of mixed-integer sets, such as the submodular knapsack polytope, can be extended to the approximate submodularity setting. Our work demonstrates that one may generalize many of the analytical tools used in submodular optimization into the approximate submodularity context.