A note on the implications of approximate submodularity in discrete optimization
A note on the implications of approximate submodularity in discrete optimization
复制标题
关于离散优化中近似子模性影响的注释
DOI：
10.1007/s11590-022-01890-w
复制
发表时间：
2022
影响因子：
1.6
通讯作者：
Schaefer, Andrew J.
中科院分区：
文献类型：
--
作者：
Ajayi, Temitayo;Lee, Taewoo;Schaefer, Andrew J.
子模性是离散优化的一个关键属性。子模性已广泛用于分析贪婪算法以给出性能界限并提供对混合整数程序的有效不等式构造的深入了解。近年来，研究人员开始研究近似子模块性，主要关注为迭代方法提供性能界限。在本文中，我们从不同的角度研究近似子模性，以扩大其在离散优化中的用例。我们定义了量化近似子模性的度量，然后用它来导出关于近似子模性保留和集合函数的众所周知的 Lovász 扩展的新属性。我们还表明，先前对混合整数集（例如子模背包多胞形）的分析可以扩展到近似子模性设置。我们的工作表明，人们可以将子模优化中使用的许多分析工具推广到近似子模性环境中。
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.
登录
查看更多内容
影响因子：
3.6
作者：
S. Salhi
通讯作者：
S. Salhi
影响因子：
2.7
作者：
Alper Atamtürk;Vishnu Narayanan
通讯作者：
Vishnu Narayanan
DOI：
--
发表时间：
2016
期刊：
影响因子：
--
作者：
Tomoyuki Obuchi;Remi Monasson;and Simona Cocco;Tomoyuki Obuchi and Yoshiyuki Kabashima
通讯作者：
Tomoyuki Obuchi and Yoshiyuki Kabashima
影响因子：
13.3
作者：
Matsui, Y;Nishio, K;Masuda, H
通讯作者：
Masuda, H