.png){kind=icon}
返回
String Submodular Functions With Curvature Constraints
.png){kind=icon}
OA
AI
DOI：10.1109/TAC.2015.2440566.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Consider the problem of choosing a string of actions to optimize an objective function that is string submodular. It was shown in previous papers that the greedy strategy, consisting of a string of actions that only locally maximizes the step-wise gain in the objective function, achieves at least a (1 -e(-1))-approximation to the optimal strategy. This paper improves this approximation by introducing additional constraints on curvature, namely, total backward curvature, total forward curvature, and elemental forward curvature. We show that if the objective function has total backward curvature sigma, then the greedy strategy achieves at least a (1/ sigma)(1 - e(-sigma))-approximation of the optimal strategy. If the objective function has total forward curvature epsilon, then the greedy strategy achieves at least a (1 - epsilon)-approximation of the optimal strategy. Moreover, we consider a generalization of the diminishing-return property by defining the elemental forward curvature. We also introduce the notion of string-matroid and consider the problem of maximizing the objective function subject to a string-matroid constraint. We investigate two applications of string submodular functions with curvature constraints: 1) choosing a string of actions to maximize the expected fraction of accomplished tasks; and 2) designing a string of measurement matrices such that the information gain is maximized.
Keyword:
Combinatorial optimization
greedy
matroid
optimal control
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
7
论文数:
1.3W
被引数:
6.7W
机构
引用论文
.png){kind=icon}
Gravitational Search Algorithm with Wavelet Mutation applied for optimal IIR band pass filter design
PREAI
分享收藏Barium Hexaaluminate as a Novel Promising Support for Ruthenium-based Ammonia Synthesis Catalysts
PREAI
分享收藏
查看更多内容