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

streaming algorithms for News and Scientific Literature Recommendation: Monotone Submodular Maximization With a d-Knapsack Constraint

引用

IEEE ACCESS 2018年 6卷 53736-53747页

作者： Yu, Qilian Xu, Li Cui, Shuguang Univ Calif Davis Dept Elect & Comp Engn Davis CA 95616 USA Chinese Acad Sci Inst Comp Technol Beijing 100190 Peoples R China

Submodular optimization plays a significant role in combinatorial problems, since it captures the structure of the edge cuts in graphs, the coverage of sets, and so on. Many data mining and machine learning problems can be cast as submodular maximization problems with applications in recommendation systems and data diversification. In this paper, we focus on the problem of maximizing a monotone submodular function subject to a d-knapsack constraint, for which we propose a streaming algorithm that achieves a ((1/1 + 2d) - epsilon)-approximation of the optimal value, while it only needs one single pass through the data set without storing all the data in the memory. In our experiments, we extensively evaluate the effectiveness of our proposed algorithm via two applications: news recommendation and scientific literature recommendation. It is observed that the proposed streaming algorithm achieves both execution speedup and memory saving by several orders of magnitude, compared with existing approaches.

关键词： Submodular optimization streaming algorithm news recommendation scientific literature recommendation

来源：评论

学校读者我要写书评

暂无评论

streaming algorithms for multitasking scheduling with shared processing

引用

DISCRETE APPLIED MATHEMATICS 2022年 320卷 346-355页

作者： Fu, Bin Huo, Yumei Zhao, Hairong Univ Texas Rio Grande Valley Dept Comp Sci Edinburg TX 78539 USA CUNY Coll Staten Isl Dept Comp Sci Staten Isl NY 10314 USA Purdue Univ Northwest Dept Comp Sci Hammond IN 46323 USA

In this paper, we design the first streaming algorithms for the problem of multitasking scheduling on parallel machines with shared processing. In one pass, our streaming approximation schemes can provide an approximate value of the optimal makespan. If the jobs can be read in two passes, the algorithm can find the schedule with the approximate value. This work not only provides an algorithmic big data solution for the studied problem, but also gives an insight into the design of streaming algorithms for other problems in the area of scheduling. (C) 2022 Elsevier B.V. All rights reserved.

关键词： streaming algorithm Multitasking scheduling Shared processing Parallel machine Makespan Approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Maximization of k-Submodular Function with d-Knapsack Constraints Over Sliding Window

引用

清华大学学报自然科学版（英文版） 2025年第2期30卷 488-498页

作者： Wenqi Wang Yuefang Sun Zhiren Sun Donglei Du Xiaoyan Zhang School of Mathematical Science&Institute of Mathematics Nanjing Normal University Key Laboratory of Ministry of Education Numerical Simulation of Large Scale Complex Systems Nanjing 210023China School of Mathematics and Statistics Ningbo UniversityNingbo 315211China Faculty of Management University of New BrunswickFredericton E3B9Y2Canada

Submodular function maximization problem has been extensively studied recently.A natural variant of submodular function is k-submodular function,which has many applications in real life,such as influence maximization and sensor placement *** domain of a k-submodular function has k disjoint subsets,and hence includes submodular function as a special case when k=*** work investigates the k-submodular function maximization problem with d-knapsack constraints over the sliding *** on the smooth histogram technique,we design a deterministic approximation ***,we propose a randomized algorithm to improve the approximation ratio.

关键词： k-submodular function d-knapsack constraints sliding window streaming algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

streaming algorithms for Maximizing k-Submodular Functions with the Multi-knapsack Constraint

引用

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA 2024年 1-19页

作者： Gong, Shu-Fang Liu, Bin Fang, Qi-Zhi Ocean Univ China Sch Math Sci Qingdao 266100 Shandong Peoples R China

The problem of maximizing submodular functions with constraints has attracted widespread attention in the past few decades. In recent years, the extensions of submodular functions were studied, such as lattice submodular functions, diminishing return submodular (DR-submodular) functions and k-submodular functions. A k-submodular function is a generalization of a submodular function to k dimensions. Many machine learning problems can be cast as k-submodular maximization problems, for example, influence maximization with k kinds of topics and sensor placement with k kinds of sensors. Recently, the unprecedented growth in modern datasets makes it necessary to design streaming algorithms. This paper investigates the problem of maximizing a nonnegative normalized k-submodular function with the multi-knapsack constraint (also called the d-knapsack constraint) in the streaming model. To address this problem, we design an efficient streaming algorithm that runs in one pass, stores at most O(b log b/epsilon) elements and queries at most O(dk log b/epsilon) per element where b is a constant after the normalization of the problem. This streaming algorithm also can achieve a (1/2(1+d) - epsilon)-approximation when the objective function f is monotone and (1/3+2d - epsilon)-approximation when the objective function f is non-monotone.

关键词： k-Submodular maximization Multi-knapsack constraint streaming algorithm Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

streaming algorithms for Maximization of a Non-submodular Function with a Cardinality Constraint on the Integer Lattice 22nd

Streaming Algorithms for Maximization of a Non-submodular Fu...

引用

22nd International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2021)

作者： Tan, Jingjing Sun, Yue Xu, Yicheng Zou, Juan Weifang Univ Sch Math & Informat Sci Weifang 261061 Peoples R China Beijing Univ Technol Beijing Inst Sci & Engn Comp Beijing 100124 Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen 518055 Peoples R China Guangxi Key Lab Cryptog & Informat Secur Guilin 541004 Peoples R China Qufu Normal Univ Sch Math Sci Qufu 273165 Shandong Peoples R China

We consider the maximization of a monotone non-submodular function with a cardinality constraint on the integer lattice. As our main contribution, two streaming algorithms with provable good performance guarantee and ... 详细信息

ISBN: (纸本)9783030967727;9783030967710

关键词： streaming algorithm Non-submodular Cardinality constraint Integer lattice

来源：评论

学校读者我要写书评

暂无评论

streaming algorithms for Maximizing Non-submodular Functions on the Integer Lattice 10th

Streaming Algorithms for Maximizing Non-submodular Functions...

引用

10th International Conference on Computational Data and Social Networks (CSoNet)

作者： Liu, Bin Chen, Zihan Wang, Huijuan Wu, Weili Ocean Univ China Sch Math Sci Qingdao Peoples R China Qingdao Univ Sch Math & Stat Qingdao Peoples R China Univ Texas Dallas Dept Comp Sci Dallas TX 75080 USA

ISBN: (纸本)9783030914349;9783030914332

Submodular functions play a key role in combinatorial optimization field. The problem of maximizing submodular and nonsubmodular functions on the integer lattice has received a lot of recent attention. In this paper, we study streaming algorithms for the problem of maximizing a monotone non-submodular functions with cardinality constraint on the integer lattice. For a monotone non-submodular function f : Z(n) (+)-> R+ defined on the integer lattice with diminishing-return (DR) ratio., we present a one pass streaming algorithm that gives a (1 - 1/ 27 - is an element of)-approximation, requires at most O(k is an element of(-1) log k/gamma) space and O(is an element of(-1) log k/gamma center dot log parallel to B parallel to 8) update time per element. To the best of our knowledge, this is the first streaming algorithm on the integer lattice for this constrained maximization problem.

关键词： streaming algorithm Cardinality constraint Non-submodular maximization Integer lattice

来源：评论

学校读者我要写书评

暂无评论

streaming algorithms for Diversity Maximization with Fairness Constraints 38

Streaming Algorithms for Diversity Maximization with Fairnes...

引用

38th IEEE International Conference on Data Engineering (ICDE)

作者： Wang, Yanhao Fabbri, Francesco Mathioudakis, Michael East China Normal Univ Sch Data Sci & Engn Shanghai Peoples R China Univ Pompeu Fabra Dept Informat & Commun Technol Barcelona Spain Eurecat Ctr Tecnol Catalunya Barcelona Spain Univ Helsinki Dept Comp Sci Helsinki Finland

ISBN: (数字)9781665408837

ISBN: (纸本)9781665408837

Diversity maximization is a fundamental problem with wide applications in data summarization, web search, and recommender systems. Given a set X of n elements, it asks to select a subset S of k << n elements with maximum diversity, as quantified by the dissimilarities among the elements in S. In this paper, we focus on the diversity maximization problem with fairness constraints in the streaming setting. Specifically, we consider the max-min diversity objective, which selects a subset S that maximizes the minimum distance (dissimilarity) between any pair of distinct elements within it. Assuming that the set X is partitioned into m disjoint groups by some sensitive attribute, e.g., sex or race, ensuring fairness requires that the selected subset S contains k(i) elements from each group i is an element of [1, m]. A streaming algorithm should process X sequentially in one pass and return a subset with maximum diversity while guaranteeing the fairness constraint. Although diversity maximization has been extensively studied, the only known algorithms that can work with the max-min diversity objective and fairness constraints are very inefficient for data streams. Since diversity maximization is NP-hard in general, we propose two approximation algorithms for fair diversity maximization in data streams, the first of which is 1- epsilon/4-approximate and specific for m = 2, where epsilon is an element of (0, 1), and the second of which achieves a 1-epsilon/3m+2-approximation for an arbitrary m. Experimental results on real-world and synthetic datasets show that both algorithms provide solutions of comparable quality to the state-of-the-art algorithms while running several orders of magnitude faster in the streaming setting.

关键词： algorithmic fairness diversity maximization max-min dispersion streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

streaming algorithms for Budgeted k-Submodular Maximization Problem 10th

Streaming Algorithms for Budgeted k-Submodular Maximization ...

引用

10th International Conference on Computational Data and Social Networks (CSoNet)

作者： Pham, Canh V. Vu, Quang C. Ha, Dung K. T. Nguyen, Tai T. Phenikaa Univ ORlab Fac Comp Sci Hanoi 12116 Vietnam Peoples Secur Acad Fac Informat Secur Hanoi Vietnam Vietnam Natl Univ Fac Informat Technol Univ Engn & Technol Hanoi Vietnam

ISBN: (纸本)9783030914349;9783030914332

Stimulated by practical applications arising from viral marketing. This paper investigates a novel Budgeted k-Submodular Maximization problem defined as follows: Given a finite set V, a budget B and a k-submodular function f : (k + 1)(V) sic R+, the problem asks to find a solution s = (S-1, S-2,..., S-k), each element e is an element of V has a cost c(i)(e) to be put into i-th set S-i, with the total cost of s does not exceed B so that f(s) is maximized. To address this problem, we propose two streaming algorithms that provide approximation guarantees for the problem. In particular, in the case of each element e has the same cost for all i-th sets, we propose a deterministic streaming algorithm which provides an approximation ratio of 1/4 - is an element of when f is monotone and 1/5 - is an element of when f is nonmonotone. For the general case, we propose a random streaming algorithm that provides an approximation ratio of min{a/2, (1- a)k/(1+ss)k-ss}-is an element of when f is monotone and min{a 2, (1-a)k/ (1+2 ss)k- 2 ss} - is an element of when f is non-monotone in expectation, where ss = maxe is an element of V-,V-i,V-j is an element of[k],V-i not equal j ci(e) /cj (e) and is an element of, alpha are fixed inputs.

关键词： k-submodular Budget constraint Approximation algorithm streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

streaming algorithms for 2-Coloring Uniform Hypergraphs

Streaming Algorithms for 2-Coloring Uniform Hypergraphs

引用

12th International Symposium on algorithms and Data Structures (WADS)

作者： Radhakrishnan, Jaikumar Shannigrahi, Saswata Tata Inst Fundamental Res Bombay 400005 Maharashtra India

ISBN: (纸本)9783642222993

We consider the problem of two-coloring n-uniform hypergraphs. It is known that any such hypergraph with at most 1/10 root n/lnn(2)2(n) hyperedges can be two-colored [7]. In fact, there is an efficient (requiring polynomial time in the size of the input) randomized algorithm that produces such a coloring. As stated [7], this algorithm requires random access to the hyperedge set of the input hypergraph. In this paper, we show that a variant of this algorithm can be implemented in the streaming model (with just one pass over the input), using space O(vertical bar V vertical bar B), where V is the vertex set of the hypergraph and each vertex is represented by B bits. (Note that the number of hyperedges in the hypergraph can be superpolynomial in vertical bar V vertical bar, and it is not feasible to store the entire hypergraph in memory.) We also consider the question of the minimum number of hyperedges in non-two-colorable n-uniform hypergraphs. Era's showed that there exist non-2-colorable n-uniform hypegraphs with O(n(2)2(n)) hyperedges and Theta(n(2)) vertices. We show that the choice Theta(n(2)) for the number of vertices in Erdos's construction is crucial: any hypergraph with at most 2n(2)/t vertices and 2(n) exp(t/8) hyperedges is 2-colorable. (We present a simple randomized streaming algorithm to construct the two-coloring.) Thus, for example, if the number of vertices is at most n(1.5), then any non-2-colorable hypergraph must have at least 2(n) exp(root n/8) >> n(2)2(n) hyperedges. We observe that the exponential dependence on t in our result is optimal up to constant factors.

关键词： Property B hypergraph coloring streaming algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Bicriteria streaming algorithms to balance gain and cost with cardinality constraint

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第4期44卷 2946-2962页

作者： Wang, Yijing Xu, Dachuan Du, Donglei Jiang, Yanjun Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Univ New Brunswick Fac Management Fredericton NB E3B 5A3 Canada Ludong Univ Sch Math & Stat Sci Yantai 264025 Peoples R China

Team formation plays an essential role in the labor market. In this paper, we propose two bicriteria algorithms to construct a balance between gain and cost in a team formation problem under the streaming model, subject to a cardinality constraint. We formulate the problem as maximizing the difference of a non-negative normalized monotone submodular function and a non-negative linear function. As an extension, we also consider the case where the first function is gamma-weakly submodular. Combining the greedy technique with the threshold method, we present bicriteria streaming algorithms and give detailed analysis for both of these models. Our analysis is competitive with that in Ene's work.

关键词： streaming algorithm Approximately submodular Linear function Bicriteria

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：