Many practical problems emphasize the importance of not only knowing whether an element is selectedbut also deciding to what extent it is selected,which imposes a challenge on submodule optimization.In this study,we c...Many practical problems emphasize the importance of not only knowing whether an element is selectedbut also deciding to what extent it is selected,which imposes a challenge on submodule optimization.In this study,we consider the monotone,nondecreasing,and non-submodular maximization on the integer lattice with a cardinalityconstraint.We first design a two-pass streaming algorithm by refining the estimation interval of the optimal value.Foreach element,the algorithm not only decides whether to save the element but also gives the number of reservations.Then,we introduce the binary search as a subroutine to reduce the time complexity.Next,we obtain a one-passstreaming algorithm by dynamically updating the estimation interval of optimal value.Finally,we improve the memorycomplexity of this algorithm.展开更多
In this paper,we investigate the problem of minimizing the ratio of normalized non-negative monotone non-submodular set function f and normalized non-negative monotone set function g.We take advantage of the greedy te...In this paper,we investigate the problem of minimizing the ratio of normalized non-negative monotone non-submodular set function f and normalized non-negative monotone set function g.We take advantage of the greedy technique and get a per-formance guarantee depending on the generalized curvature and inverse generalized curvature of f,as well as the submodularity ratio of g.Our results generalize the works of Bai et al.(Algorithms for optimizing the ratio of submodular functions.In:Proceedings of the 33rd International Conference on Machine L earning,2016)and Qian et al.(Optimizing ratio of monotone set functions.In:Proceedings of the 26th International Joint Conference on Artificial Intelligence,2017).展开更多
The widely used greedy algorithm has been recently shown to achieve near-optimal theoretical guarantees for the problems of constrained monotone non-submodular function maximization,with competitive performances in pr...The widely used greedy algorithm has been recently shown to achieve near-optimal theoretical guarantees for the problems of constrained monotone non-submodular function maximization,with competitive performances in practice.In this paper,we investigate the problems of maximizing monotone non-submodular set functions under three classes of independent system constraints,including p-matroid intersection constraints,p-extendible system constraints and p-system constraints.We prove that the greedy algorithm yields an approximation ratio ofγ/p+γfor the former two problems,andξγ/p+ξγfor the last problem,which further has been improved toγ/p+γ,whereγ,ξdenote the submodularity ratio and the diminishing returns ratio of set function respectively.In addition,we also show that the greedy guarantees have a further refinement of for all the problems mentioned above,whereαis the generalized curvatureξ/p+αγof set function.Finally,we show that our greedy algorithm does yield competitive practical performances using a variety of experiments on synthetic data.展开更多
基金supported by the National Natural Science Foundation of China(No.11871081)the Natural Science Foundation of Shandong Province(No.ZR2022MA034)+3 种基金the Guangxi Key Laboratory of Cryptography and Information Security(No.GCIS202116)the Fundamental Research Project of Shenzhen City(No.JCYJ20210324102012033)the National Natural Science Foundation of China(No.11901558)the National Natural Science Foundation of China(No.11801310).
文摘Many practical problems emphasize the importance of not only knowing whether an element is selectedbut also deciding to what extent it is selected,which imposes a challenge on submodule optimization.In this study,we consider the monotone,nondecreasing,and non-submodular maximization on the integer lattice with a cardinalityconstraint.We first design a two-pass streaming algorithm by refining the estimation interval of the optimal value.Foreach element,the algorithm not only decides whether to save the element but also gives the number of reservations.Then,we introduce the binary search as a subroutine to reduce the time complexity.Next,we obtain a one-passstreaming algorithm by dynamically updating the estimation interval of optimal value.Finally,we improve the memorycomplexity of this algorithm.
基金Da-Chuan Xu’s research was supported by the National Natural Science Foundation of China(No.11531014)Yan-Jun Jiang was supported by the National Natural Science Foundation of China(No.11801251)Dong-Mei Zhang was supported by the National Natural Science Foundation of China(No.11871081).
文摘In this paper,we investigate the problem of minimizing the ratio of normalized non-negative monotone non-submodular set function f and normalized non-negative monotone set function g.We take advantage of the greedy technique and get a per-formance guarantee depending on the generalized curvature and inverse generalized curvature of f,as well as the submodularity ratio of g.Our results generalize the works of Bai et al.(Algorithms for optimizing the ratio of submodular functions.In:Proceedings of the 33rd International Conference on Machine L earning,2016)and Qian et al.(Optimizing ratio of monotone set functions.In:Proceedings of the 26th International Joint Conference on Artificial Intelligence,2017).
基金supported by the National Natural Science Foundation of China(No.11971376).
文摘The widely used greedy algorithm has been recently shown to achieve near-optimal theoretical guarantees for the problems of constrained monotone non-submodular function maximization,with competitive performances in practice.In this paper,we investigate the problems of maximizing monotone non-submodular set functions under three classes of independent system constraints,including p-matroid intersection constraints,p-extendible system constraints and p-system constraints.We prove that the greedy algorithm yields an approximation ratio ofγ/p+γfor the former two problems,andξγ/p+ξγfor the last problem,which further has been improved toγ/p+γ,whereγ,ξdenote the submodularity ratio and the diminishing returns ratio of set function respectively.In addition,we also show that the greedy guarantees have a further refinement of for all the problems mentioned above,whereαis the generalized curvatureξ/p+αγof set function.Finally,we show that our greedy algorithm does yield competitive practical performances using a variety of experiments on synthetic data.
