检索结果-内蒙古大学图书馆

Partial-monotone adaptive submodular maximization

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第1期45卷 1-13页

作者： Tang, Shaojie Yuan, Jing Univ Texas Dallas Naveen Jindal Sch Management Richardson TX 75080 USA Univ North Texas Dept Comp Sci & Engn Denton TX USA

Many AI/Machine learning problems require adaptively selecting a sequence of items, each selected item might provide some feedback that is valuable for making better selections in the future, with the goal of maximizing an adaptive submodular function. Most of existing studies in this field focus on either monotone case or non-monotone case. Specifically, if the utility function is monotone and adaptive submodular, Golovin and Krause (J Artif Intell Res 42:427-486, 2011) developed (1 - 1/e) approximation solution subject to a cardinality constraint. For the cardinality-constrained non-monotone case, Tang (Theor Comput Sci 850:249-261, 2021) showed that a random greedy policy attains an approximation ratio of 1/e. In this work, we generalize the above mentioned results by studying the partial-monotone adaptive submodular maximization problem. To this end, we introduce the notation of adaptive monotonicity ratio m is an element of [0, 1] to measure the degree of monotonicity of a function. Our main result is to show that for the case of cardinality constraints, if the utility function has an adaptive monotonicity ratio of m and it is adaptive submodular, then a random greedy policy attains an approximation ratio of m(1 - 1/e) + (1 - m)(1/e). Notably this result recovers the aforementioned (1 - 1/e) and 1/e approximation ratios when m = 1 and m = 0, respectively. We further extend our results to consider a knapsack constraint and develop a (m + 1)/10 approximation solution for this general case. One important implication of our results is that even for a non-monotone utility function, we still can attain an approximation ratio close to (1-1/e) if this function is "close" to a monotone function. This leads to improved performance bounds for many machine learning applications whose utility functions are almost adaptive monotone.

关键词： Approximation algorithm adaptive submodular maximization Partial-monotonicity

来源：评论

学校读者我要写书评

暂无评论

adaptive Cascade submodular maximization 21

Adaptive Cascade Submodular Maximization

引用

Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems

作者： Shaojie Tang Jing Yuan University of Texas at Dallas Richardson TX USA

ISBN: (纸本)9781450383073

In this paper, we propose and study the cascade submodular maximization problem under the adaptive setting. The input of our problem is a set of items, each item is in a particular state (i.e., the marginal contribution of an item) which is drawn from a known probability distribution. However, we can not know its actual state before selecting it. As compared with existing studies on stochastic submodular maximization, one unique setting of our problem is that each item is associated with a continuation probability which represents the probability that one is allowed to continue to select the next item after selecting the current one. Intuitively, this term captures the externality of selecting one item to all its subsequent items in terms of the opportunity of being selected. Therefore, the actual set of items that can be selected by a policy depends on the specific ordering it adopts to select items, this makes our problem fundamentally different from classical submodular set optimization problems. Our objective is to identify the best sequence of selecting items so as to maximize the expected utility of the selected items. We propose a class of stochastic utility functions, adaptive cascade submodular functions, and show that the objective functions in many practical application domains satisfy adaptive cascade submodularity. Then we develop a $0.12$ approximation algorithm to the adaptive cascade submodular maximization problem.

关键词： adaptive submodular maximization cascade browse model submodular sequencing

来源：评论

学校读者我要写书评

暂无评论

Worst-Case adaptive submodular Cover 23

Worst-Case Adaptive Submodular Cover

引用

Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems

作者： Jing Yuan Shaojie Tang University of North Texas Denton TX USA The University of Texas at Dallas Richardson TX USA

ISBN: (纸本)9781450394321

In this paper, we study the adaptive submodular cover problem under the worst-case setting. This problem generalizes many previously studied problems, namely, the pool-based active learning and the stochastic submodular set cover. The input of our problem is a set of items (e.g., medical tests) and each item has a random state (e.g., the outcome of a medical test), whose realization is initially unknown. One must select an item at a fixed cost in order to observe its realization. There is a utility function which maps a subset of items and their states to a non-negative real number. We aim to sequentially select a group of items to achieve a "target value'' while minimizing the maximum cost across realizations (a.k.a. worst-case cost). To facilitate our study, we assume that the utility function is worst-case submodular, a property that is commonly found in many machine learning applications. With this assumption, we develop a tight (log (Q/η)+1)-approximation policy, where Q is the "target value'' and η is the smallest difference between Q and any achievable utility value ^Q < Q. We also study a worst-case maximum-coverage problem, a dual problem of the minimum-cost-cover problem, whose goal is to select a group of items to maximize its worst-case utility subject to a budget constraint. To solve this problem, we develop a (1-1/e)/2-approximation solution.

关键词： adaptive submodular maximization worst-case analysis approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

adaptive Discount Allocation in Social Networks 17

Adaptive Discount Allocation in Social Networks

引用

18th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)

作者： Yuan, Jing Tang, Shao-Jie Univ Texas Dallas Dept Comp Sci Richardson TX 75083 USA Univ Texas Dallas JSOM Richardson TX 75083 USA

ISBN: (纸本)9781450349123

It has been reported that 40% of consumers will share an email offer with their friend and 28% of consumers will share deals via social media platforms. This motivates us to study the influence maximization discount allocation problem: given a social network and a limited marketing budget, which set of initial users should be selected to receive the discount, and how much should the discounts be worth? Our goal is to maximize the number of customers who finally adopt the target product. We investigate this problem under both non-adaptive and adaptive settings. In the first setting, we have to commit the set of initial users and corresponding discounts all at once in advance. In the latter case, given that an user has been offered a discount, we are able to know immediately her decision on whether or not to accept that discount, therefore, the decision process is performed in a sequential manner based on the feedback from previously selected users. We propose a simple greedy policy with an approximation ratio of (1 - 1/e) in non-adaptive setting. For the significantly more complex adaptive setting, we propose a series of adaptive policies with bounded approximation ratio in terms of expected utility.

关键词： adaptive submodular maximization influence maximization discount allocation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：