The problem of maximizing a normalized monotone non-submodular set function subject to a cardinality constraint arises in the context of extracting information from massive streaming data. In this paper, we present fo...
详细信息
The problem of maximizing a normalized monotone non-submodular set function subject to a cardinality constraint arises in the context of extracting information from massive streaming data. In this paper, we present four streaming algorithms for this problem by utilizing the concept of diminishing-return ratio. We analyze these algorithms to obtain the corresponding approximation ratios, which generalize the previous results for the submodular case. The numerical experiments show that our algorithms have better solution quality and competitive running time when compared to an existing algorithm.
We study the non-submodular maximization problem, in which the objective function is characterized by parameters, subject to a cardinality or p\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \u...
详细信息
We study the non-submodular maximization problem, in which the objective function is characterized by parameters, subject to a cardinality or p\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p$$\end{document}-system constraint. By adapting the Threshold-Greedy algorithm for the submodularmaximization, we present two deterministic algorithms for approximately solving the non-submodular maximization problem. Our analysis shows that the algorithms we propose requires much less function evaluations than existing algorithms, while providing comparable approximation guarantees. Moreover, numerical experiment results are presented to validate the theoretical analysis. Our results not only fill a gap in the (non-)submodularmaximization, but also generalize and improve several existing results on closely related optimization problems.
We investigate the problem of maximizing a gamma-submodular function subject to one or multiple matroid constraints and one knapsack constraint. By the greedy local search technique, we present approximation algorithm...
详细信息
We investigate the problem of maximizing a gamma-submodular function subject to one or multiple matroid constraints and one knapsack constraint. By the greedy local search technique, we present approximation algorithms with constant approximation ratios. When gamma = 1, our model reduces to the regular submodularmaximization problem investigated in the literature under the same type of constraints. Our results therefore contribute towards the line of research on constrained non-submodular function maximization.
submodular optimization problem has been concerned in recent years. The problem of maximizing submodular and non-submodular functions on the integer lattice has received a lot of recent attention. In this paper, we st...
详细信息
submodular optimization problem has been concerned in recent years. The problem of maximizing submodular and non-submodular 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 gamma , we present a one pass streaming algorithm that gives a (1-12(gamma)-epsilon)\-approximation, requires at most O(k epsilon-1logk/gamma)\space and O(epsilon-1logk/*** ||B||(infinity)) . update time per element. We then modify the algorithm and improve the memory complexity to O(k/gamma(epsilon)) . To the best of our knowledge, this is the first streaming algorithm on the integer lattice for this constrained maximization problem.
We investigate a non-submodular maximization problem subject to a p-independence system constraint, where the non-submodularity of the utility function is characterized by a series of parameters, such as submodularity...
详细信息
ISBN:
(纸本)9783030261764;9783030261757
We investigate a non-submodular maximization problem subject to a p-independence system constraint, where the non-submodularity of the utility function is characterized by a series of parameters, such as submodularity (supmodularity) ratio, generalized curvature, and zero order approximate submodularity coefficient, etc. Inspired by Feldman et al. [15] who consider a non-monotone submodularmaximization with a p-independence system constraint, we extend their Repeat-Greedy algorithm to non-submodular setting. While there is no general reduction to convert algorithms for submodular optimization problems to non-submodular optimization problems, we are able to show the extended Repeat-Greedy algorithm has an almost constant approximation ratio for non-monotone non-submodular maximization.
In this paper, we firstly study the problem of maximizing a gamma-weakly DR-submodular function under a general matroid constraint. We present a local search algorithm, which is guided by a tailored potential function...
详细信息
In this paper, we firstly study the problem of maximizing a gamma-weakly DR-submodular function under a general matroid constraint. We present a local search algorithm, which is guided by a tailored potential function, for solving this problem. We prove that our algorithm produces a (1 - e(-gamma) - epsilon)-approximate solution. To the best of our knowledge, it's the first algorithm achieving the tight approximation guarantee for such maximization problem. In addition, we study the maximization of the sum of submodular and supermodular functions. We show that this problem can be reduced to the maximization of submodular and linear sums. Based on this reduction, we derive new and improved approximation bounds for the problem under various types of constraints.
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, ...
详细信息
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.
In this paper, the problem we study is how to maximize a monotone non-submodular function with cardinality constraint. Different from the previous streaming algorithms, this paper mainly considers the sliding window m...
详细信息
In this paper, the problem we study is how to maximize a monotone non-submodular function with cardinality constraint. Different from the previous streaming algorithms, this paper mainly considers the sliding window model. Based on the concept of diminishing-return ratio gamma, we propose a (1/3-gamma(2) - epsilon)-approximation algorithm with the memory O(k log(2)(k Phi 1/gamma/epsilon(2)), where Phi is the ratio between maximum and minimum values of any singleton element of function f. Then, we improve the approximation ratio to (1/2 gamma - epsilon) through the sub-windows at the expense of losing some memory. Our results 2 generalize the corresponding results for the submodular case.
暂无评论