Online algorithms for BP functions maximization
Online algorithms for BP functions maximization
复制标题
BP函数最大化的在线算法
DOI：
10.1016/j.tcs.2021.01.020
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Zhang Xiaoyan
中科院分区：
文献类型：
--
作者：
Liu Zhicheng;Chen Ling;Chang Hong;Du Donglei;Zhang Xiaoyan
BP最大化问题在机器学习和数据科学中有着广泛的应用。它可以被描述为在一定的约束条件下最大化一个超B模函数和一个超模函数之和，其中两个函数都是非负的单调函数。在本文中，我们考虑了两个在线案例。第一类是具有一致拟阵约束的物品逐个到达时的BP极大化问题，我们给出了一个恒定竞争比的在线算法。第二类是受分区拟阵约束的BP最大化问题，其中分区的每个部分以随机顺序到达，对于该问题，我们给出了两个恒定竞争比的近似算法，其中一个是随机化的，另一个是确定性的。
BP maximization problem has many applications in machine learning and data science. It can be described as maximizing the sum of a suBmodular function and a suPermodular function (BP) under some constraints, where both functions are nonnegative and monotonic. In this paper, we consider two online cases. The first is a BP maximization problem subject to a uniform matroid constraint when the items arrive one-by-one, for which we offer an online algorithm with constant competitive ratio. The second is a BP maximization problem subject to a partition matroid constraint where each part of the partition arrives in a random order, for which we present two approximation algorithms of both constant competitive ratios, where one is randomized and the other is deterministic.
登录
查看更多内容
DOI：
--
发表时间：
2011-06
期刊：
--
影响因子：
--
作者：
Hui-Ching Lin;J. Bilmes
通讯作者：
Hui-Ching Lin;J. Bilmes
DOI：
--
发表时间：
2007-07
期刊：
--
影响因子：
--
作者：
Andreas Krause;Carlos Guestrin
通讯作者：
Andreas Krause;Carlos Guestrin
DOI：
--
发表时间：
2015-07
期刊：
The Science of the total environment
影响因子：
--
作者：
K. Wei;Rishabh K. Iyer;J. Bilmes
通讯作者：
K. Wei;Rishabh K. Iyer;J. Bilmes
影响因子：
1.1
作者：
CONFORTI, M;CORNUEJOLS, G
通讯作者：
CORNUEJOLS, G
DOI：
10.1061/(asce)0733-9496(2008)134:6(516
发表时间：
2008-11-01
期刊：
JOURNAL OF WATER RESOURCES PLANNING AND MANAGEMENT-ASCE
影响因子：
--
作者：
Krause, Andreas;Leskovec, Jure;Faloutsos, Christos
通讯作者：
Faloutsos, Christos