In this work,we focus on maximizing the ratio of two monotone DR-submodular functions on the integer lattice.It is neither submodular nor supermodular.We prove that the Threshold Decrease Algorithm is a 1-e^(1-kg)-εa...In this work,we focus on maximizing the ratio of two monotone DR-submodular functions on the integer lattice.It is neither submodular nor supermodular.We prove that the Threshold Decrease Algorithm is a 1-e^(1-kg)-εapproximation ratio algorithm.Additionally,we construct the relationship between maximizing the ratio of two monotone DR-submodular functions and maximizing the difference of two monotone DR-submodular functions on the integer lattice.Based on this relationship,we combine the dichotomy technique and Threshold Decrease Algorithm to solve maximizing the difference of two monotone DR-submodular functions on the integer lattice and prove its approximation ratio is f(x)-g(x)≥1-e^(1-kg)f(X^(*))-g(X^(*)).To the best of our knowledge,before us,there was no work to focus on maximizing the ratio of two monotone DR-submodular functions on integer lattice by using the Threshold Decrease Algorithm.展开更多
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 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/ε).展开更多
Inspired by the framework of Boyen, in this paper, an attribute-based signature（ABS） scheme from lattice assumption is proposed. In this attribute-based signature scheme, an entity＇s attributes set corresponds to t...Inspired by the framework of Boyen, in this paper, an attribute-based signature（ABS） scheme from lattice assumption is proposed. In this attribute-based signature scheme, an entity＇s attributes set corresponds to the concatenation of a lattice matrix with the sum of some random matrices, and the signature vector is generated by using the Preimage Sampling algorithm. Compared with current attribute-based signature schemes, this scheme can resist quantum attacks and enjoy shorter public-key, smaller signature size and higher efficiency.展开更多
基金upported by the China Scholarship Council(No.202004910755)supported by the National Natural Science Foundation of China(Nos.12071459 and 11991022)+2 种基金the Fundamental Research Funds for Central Universities(No.E1E40107X2)supported by the Natural Sciences and Engineering Research Council of Canada(No.283106)the National Natural Science Foundation of China(Nos.11771386 and 11728104)。
文摘In this work,we focus on maximizing the ratio of two monotone DR-submodular functions on the integer lattice.It is neither submodular nor supermodular.We prove that the Threshold Decrease Algorithm is a 1-e^(1-kg)-εapproximation ratio algorithm.Additionally,we construct the relationship between maximizing the ratio of two monotone DR-submodular functions and maximizing the difference of two monotone DR-submodular functions on the integer lattice.Based on this relationship,we combine the dichotomy technique and Threshold Decrease Algorithm to solve maximizing the difference of two monotone DR-submodular functions on the integer lattice and prove its approximation ratio is f(x)-g(x)≥1-e^(1-kg)f(X^(*))-g(X^(*)).To the best of our knowledge,before us,there was no work to focus on maximizing the ratio of two monotone DR-submodular functions on integer lattice by using the Threshold Decrease Algorithm.
基金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 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/ε).
基金Supported by the National Natural Science Foundation of China(61173151,61472309)
文摘Inspired by the framework of Boyen, in this paper, an attribute-based signature（ABS） scheme from lattice assumption is proposed. In this attribute-based signature scheme, an entity＇s attributes set corresponds to the concatenation of a lattice matrix with the sum of some random matrices, and the signature vector is generated by using the Preimage Sampling algorithm. Compared with current attribute-based signature schemes, this scheme can resist quantum attacks and enjoy shorter public-key, smaller signature size and higher efficiency.
