Submodular maximization is a significant area of interest in combinatorial optimization.It has various real-world applications.In recent years,streaming algorithms for submodular maximization have gained attention,all...Submodular maximization is a significant area of interest in combinatorial optimization.It has various real-world applications.In recent years,streaming algorithms for submodular maximization have gained attention,allowing realtime processing of large data sets by examining each piece of data only once.However,most of the current state-of-the-art algorithms are only applicable to monotone submodular maximization.There are still significant gaps in the approximation ratios between monotone and non-monotone objective functions.In this paper,we propose a streaming algorithm framework for non-monotone submodular maximization and use this framework to design deterministic streaming algorithms for the d-knapsack constraint and the knapsack constraint.Our 1-pass streaming algorithm for the d-knapsack constraint has a 1/4(d+1)-∈approximation ratio,using O(BlogB/∈)memory,and O(logB/∈)query time per element,where B=MIN(n,b)is the maximum number of elements that the knapsack can store.As a special case of the d-knapsack constraint,we have the 1-pass streaming algorithm with a 1/8-∈approximation ratio to the knapsack constraint.To our knowledge,there is currently no streaming algorithm for this constraint when the objective function is non-monotone,even when d=1.In addition,we propose a multi-pass streaming algorithm with 1/6-∈approximation,which stores O(B)elements.展开更多
In this work,we study a k-Cardinality Constrained Regularized Submodular Maximization(k-CCRSM)problem,in which the objective utility is expressed as the difference between a non-negative submodular and a modular funct...In this work,we study a k-Cardinality Constrained Regularized Submodular Maximization(k-CCRSM)problem,in which the objective utility is expressed as the difference between a non-negative submodular and a modular function.No multiplicative approximation algorithm exists for the regularized model,and most works have focused on designing weak approximation algorithms for this problem.In this study,we consider the k-CCRSM problem in a streaming fashion,wherein the elements are assumed to be visited individually and cannot be entirely stored in memory.We propose two multipass streaming algorithms with theoretical guarantees for the above problem,wherein submodular terms are monotonic and nonmonotonic.展开更多
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.展开更多
This paper presents a ZUC-256 stream cipher algorithm hardware system in order to prevent the advanced security threats for 5 G wireless network.The main innovation of the hardware system is that a six-stage pipeline ...This paper presents a ZUC-256 stream cipher algorithm hardware system in order to prevent the advanced security threats for 5 G wireless network.The main innovation of the hardware system is that a six-stage pipeline scheme comprised of initialization and work stage is employed to enhance the solving speed of the critical logical paths.Moreover,the pipeline scheme adopts a novel optimized hardware structure to fast complete the Mod(231-1)calculation.The function of the hardware system has been validated experimentally in detail.The hardware system shows great superiorities.Compared with the same type system in recent literatures,the logic delay reduces by 47%with an additional hardware resources of only 4 multiplexers,the throughput rate reaches 5.26 Gbps and yields at least 45%better performance,the throughput rate per unit area increases 14.8%.The hardware system provides a faster and safer encryption module for the 5G wireless network.展开更多
Video streaming is one of the most important applications used in the best-effort Internet. This paper presents a new scheme for multiple source video streaming in which the traditional fine granular scal-able coding ...Video streaming is one of the most important applications used in the best-effort Internet. This paper presents a new scheme for multiple source video streaming in which the traditional fine granular scal-able coding was rebuilt into a multiple sub-streams based transmission model. A peak signal to noise ratio based stream rate allocation algorithm was then developed based on the transmission model. In tests, the algorithm performance is about 1 dB higher than that of a uniform rate allocation algorithm. Therefore, this scheme can overcome bottlenecks along a single link and smooth jitter to achieve high quality and stable video.展开更多
In this paper,we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone k-submodular function under a matroid constraint.In order to reduce the complexity of this algorithm,we al...In this paper,we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone k-submodular function under a matroid constraint.In order to reduce the complexity of this algorithm,we also present a randomized 1/3-approximation algorithm with the probability of 1−ε,whereεis the probability of algorithm failure.Moreover,we design a streaming algorithm for both monotone and non-monotone objective k-submodular functions.展开更多
Recent progress in maximizing submodular functions with a cardinality constraint through centralized and streaming modes has demonstrated a wide range of applications and also developed comprehensive theoretical guara...Recent progress in maximizing submodular functions with a cardinality constraint through centralized and streaming modes has demonstrated a wide range of applications and also developed comprehensive theoretical guarantees.The submodularity was investigated to capture the diversity and representativeness of the utilities,and the monotonicity has the advantage of improving the coverage.Regularized submodular optimization models were developed in the latest studies(such as a house on fire),which aimed to sieve subsets with constraints to optimize regularized utilities.This study is motivated by the setting in which the input stream is partitioned into several disjoint parts,and each part has a limited size constraint.A first threshold-based bicriteria(1/3,2/3/)-approximation for the problem is provided.展开更多
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 ...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 problem.The domain of a k-submodular function has k disjoint subsets,and hence includes submodular function as a special case when k=1.This work investigates the k-submodular function maximization problem with d-knapsack constraints over the sliding window.Based on the smooth histogram technique,we design a deterministic approximation algorithm.Furthermore,we propose a randomized algorithm to improve the approximation ratio.展开更多
We investigate the problem of maximizing the sum of submodular and supermodular functions under a fairness constraint.This sum function is non-submodular in general.For an offline model,we introduce two approximation ...We investigate the problem of maximizing the sum of submodular and supermodular functions under a fairness constraint.This sum function is non-submodular in general.For an offline model,we introduce two approximation algorithms:A greedy algorithm and a threshold greedy algorithm.For a streaming model,we propose a one-pass streaming algorithm.We also analyze the approximation ratios of these algorithms,which all depend on the total curvature of the supermodular function.The total curvature is computable in polynomial time and widely utilized in the literature.展开更多
In this paper,we investigate the maximization of the differences between a nonnegative monotone diminishing return submodular(DR-submodular)function and a nonnegative linear function on the integer lattice.As it is al...In this paper,we investigate the maximization of the differences between a nonnegative monotone diminishing return submodular(DR-submodular)function and a nonnegative linear function on the integer lattice.As it is almost unapproximable for maximizing a submodular function without the condition of nonnegative,we provide weak(bifactor)approximation algorithms for this problem in two online settings,respectively.For the unconstrained online model,we combine the ideas of single-threshold greedy,binary search and function scaling to give an efficient algorithm with a 1/2 weak approximation ratio.For the online streaming model subject to a cardinality constraint,we provide a one-pass(3-√5)/2 weak approximation ratio streaming algorithm.Its memory complexity is(k log k/ε),and the update time for per element is(log^(2)k/ε).展开更多
基金supported in part by the National Natural Science Foundation of China(Grant Nos.62325210 and 62272441).
文摘Submodular maximization is a significant area of interest in combinatorial optimization.It has various real-world applications.In recent years,streaming algorithms for submodular maximization have gained attention,allowing realtime processing of large data sets by examining each piece of data only once.However,most of the current state-of-the-art algorithms are only applicable to monotone submodular maximization.There are still significant gaps in the approximation ratios between monotone and non-monotone objective functions.In this paper,we propose a streaming algorithm framework for non-monotone submodular maximization and use this framework to design deterministic streaming algorithms for the d-knapsack constraint and the knapsack constraint.Our 1-pass streaming algorithm for the d-knapsack constraint has a 1/4(d+1)-∈approximation ratio,using O(BlogB/∈)memory,and O(logB/∈)query time per element,where B=MIN(n,b)is the maximum number of elements that the knapsack can store.As a special case of the d-knapsack constraint,we have the 1-pass streaming algorithm with a 1/8-∈approximation ratio to the knapsack constraint.To our knowledge,there is currently no streaming algorithm for this constraint when the objective function is non-monotone,even when d=1.In addition,we propose a multi-pass streaming algorithm with 1/6-∈approximation,which stores O(B)elements.
基金This work was supported by the Beijing Natural Science Foundation Project(No.Z220004)the National Natural Science Foundation of China(Nos.11901544 and 12101587)the China Postdoctoral Science Foundation(No.2022M720329).
文摘In this work,we study a k-Cardinality Constrained Regularized Submodular Maximization(k-CCRSM)problem,in which the objective utility is expressed as the difference between a non-negative submodular and a modular function.No multiplicative approximation algorithm exists for the regularized model,and most works have focused on designing weak approximation algorithms for this problem.In this study,we consider the k-CCRSM problem in a streaming fashion,wherein the elements are assumed to be visited individually and cannot be entirely stored in memory.We propose two multipass streaming algorithms with theoretical guarantees for the above problem,wherein submodular terms are monotonic and nonmonotonic.
基金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.
基金supported in part by the National R&D Program for Major Research Instruments of China(Grant No:62027814)the National Natural Science Foundation of China(Grant No:62104054)+2 种基金the Natural Science Foundation of Heilongjiang Province(Grant No:F2018010)the Postdoctoral Science Foundation of Heilongjiang Province,China(No:LBH-Z20133)the Fundamental Research Funds for The Central Universities,China(3072021CF0806)。
文摘This paper presents a ZUC-256 stream cipher algorithm hardware system in order to prevent the advanced security threats for 5 G wireless network.The main innovation of the hardware system is that a six-stage pipeline scheme comprised of initialization and work stage is employed to enhance the solving speed of the critical logical paths.Moreover,the pipeline scheme adopts a novel optimized hardware structure to fast complete the Mod(231-1)calculation.The function of the hardware system has been validated experimentally in detail.The hardware system shows great superiorities.Compared with the same type system in recent literatures,the logic delay reduces by 47%with an additional hardware resources of only 4 multiplexers,the throughput rate reaches 5.26 Gbps and yields at least 45%better performance,the throughput rate per unit area increases 14.8%.The hardware system provides a faster and safer encryption module for the 5G wireless network.
基金the National Natural Science Foundation of China (No. 60273008)
文摘Video streaming is one of the most important applications used in the best-effort Internet. This paper presents a new scheme for multiple source video streaming in which the traditional fine granular scal-able coding was rebuilt into a multiple sub-streams based transmission model. A peak signal to noise ratio based stream rate allocation algorithm was then developed based on the transmission model. In tests, the algorithm performance is about 1 dB higher than that of a uniform rate allocation algorithm. Therefore, this scheme can overcome bottlenecks along a single link and smooth jitter to achieve high quality and stable video.
基金supported by the Natural Science Foundation of Shandong Province of China(No.ZR2020MA029).
文摘In this paper,we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone k-submodular function under a matroid constraint.In order to reduce the complexity of this algorithm,we also present a randomized 1/3-approximation algorithm with the probability of 1−ε,whereεis the probability of algorithm failure.Moreover,we design a streaming algorithm for both monotone and non-monotone objective k-submodular functions.
基金This work was supported by the Beijing Natural Science Foundation Project(No.Z200002)the National Natural Science Foundation of China(Nos.12001523,12131003,and 12101587)+1 种基金the National Innovation and Entrepreneurship Training Program for College Students of Beijing University of Technology(No.GJDC-2022-01-39)the China Postdoctoral Science Foundation(No.2022M720329).
文摘Recent progress in maximizing submodular functions with a cardinality constraint through centralized and streaming modes has demonstrated a wide range of applications and also developed comprehensive theoretical guarantees.The submodularity was investigated to capture the diversity and representativeness of the utilities,and the monotonicity has the advantage of improving the coverage.Regularized submodular optimization models were developed in the latest studies(such as a house on fire),which aimed to sieve subsets with constraints to optimize regularized utilities.This study is motivated by the setting in which the input stream is partitioned into several disjoint parts,and each part has a limited size constraint.A first threshold-based bicriteria(1/3,2/3/)-approximation for the problem is provided.
基金supported by the National Natural Science Foundation of China(Nos.12271259 and 12371352)the Zhejiang Provincial Natural Science Foundation of China(No.LY23A010011)+1 种基金the Yongjiang Talent Introduction Programme of Ningbo(No.2021B-011-G)the Natural Sciences and Engineering Research Council of Canada(NSERC)(No.06446).
文摘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 problem.The domain of a k-submodular function has k disjoint subsets,and hence includes submodular function as a special case when k=1.This work investigates the k-submodular function maximization problem with d-knapsack constraints over the sliding window.Based on the smooth histogram technique,we design a deterministic approximation algorithm.Furthermore,we propose a randomized algorithm to improve the approximation ratio.
基金The first author was supported by the National Natural Science Foundation of China(Nos.12001025 and 12131003)The second author was supported by the Spark Fund of Beijing University of Technology(No.XH-2021-06-03)+2 种基金The third author was supported by the Natural Sciences and Engineering Research Council of Canada(No.283106)the Natural Science Foundation of China(Nos.11771386 and 11728104)The fourth author is supported by the National Natural Science Foundation of China(No.12001335).
文摘We investigate the problem of maximizing the sum of submodular and supermodular functions under a fairness constraint.This sum function is non-submodular in general.For an offline model,we introduce two approximation algorithms:A greedy algorithm and a threshold greedy algorithm.For a streaming model,we propose a one-pass streaming algorithm.We also analyze the approximation ratios of these algorithms,which all depend on the total curvature of the supermodular function.The total curvature is computable in polynomial time and widely utilized in the literature.
基金supported by the National Natural Science Foundation of China(Nos.12001025 and 12131003)The second author is supported by the Natural Sciences and Engineering Research Council(No.06446),and the National Natural Science Foundation of China(Nos.11771386 and 11728104)+2 种基金The third author is supported by the National Natural Science Foundation of China(Nos.11501171 and 11771251)the Province Natural Science Foundation of Shandong(No.ZR2020MA028)The fourth author is supported by the National Natural Science Foundation of China(No.11701150)。
文摘In this paper,we investigate the maximization of the differences between a nonnegative monotone diminishing return submodular(DR-submodular)function and a nonnegative linear function on the integer lattice.As it is almost unapproximable for maximizing a submodular function without the condition of nonnegative,we provide weak(bifactor)approximation algorithms for this problem in two online settings,respectively.For the unconstrained online model,we combine the ideas of single-threshold greedy,binary search and function scaling to give an efficient algorithm with a 1/2 weak approximation ratio.For the online streaming model subject to a cardinality constraint,we provide a one-pass(3-√5)/2 weak approximation ratio streaming algorithm.Its memory complexity is(k log k/ε),and the update time for per element is(log^(2)k/ε).
