This paper presents a bicriteria approximation algorithm for the minimum submodular cost partial set multi cover problem (SCPSMC), the goal of which is to find a minimum cost subcollection of sets to fully cover q per...
详细信息
This paper presents a bicriteria approximation algorithm for the minimum submodular cost partial set multi cover problem (SCPSMC), the goal of which is to find a minimum cost subcollection of sets to fully cover q percentage of total profit of all elements, where the cost on sub-collections is a submodular function, and an element e with covering requirement r(e) is fully covered if it belongs to at least r(e) picked sets. Assuming that the maximum covering requirement r(max) = max(e is an element of E) r(e) is a constant and the cost function is nonnegative and submodular, we give a deterministic (b/q epsilon, (1 - epsilon))-bicriteria algorithm for SCPSMC, the output of which fully covers at least (1 - epsilon)q-percentage of the total profit and the performance ratio is b/q epsilon, where b = max(e) ((fe)(re)) and fe is the number of sets containing element e. (C) 2019 Elsevier B.V. All rights reserved.
In this paper,we mainly investigate the optimization model that minimizes the cost function such that the cover function exceeds a required threshold in the set cover problem,where the cost function is additive linear...
详细信息
In this paper,we mainly investigate the optimization model that minimizes the cost function such that the cover function exceeds a required threshold in the set cover problem,where the cost function is additive linear,and the cover function is non-monotone approximately *** study the problem under streaming model and propose three bicriteria approximation ***,we provide an intuitive streaming algorithm under the assumption of known optimal objective *** intuitive streaming algorithm returns a solution such that its cover function value is no less thanα(1−ϵ)times threshold,and the cost function is no more than(2+ϵ)^(2)/(ϵ^(2)ω^(2))⋅κ,whereκis a value that we suppose for the optimal solution andαis the approximation ratio of an algorithm for unconstrained maximization problem that we can call *** we present a bicriteria streaming algorithm scanning the ground set multi-pass to weak the assumption that we guess the optimal objective value in advance,and maintain the same bicriteria approximation *** we modify the multi-pass streaming algorithm to a single-pass one without compromising the performance ***,we also propose some numerical experiments to test our algorithm’s performance comparing with some existing methods.
Partial set cover problem and set multi-cover problem are two generalizations of the set cover problem. In this paper, we consider the partial set multi-cover problem which is a combination of them: given an element s...
详细信息
Partial set cover problem and set multi-cover problem are two generalizations of the set cover problem. In this paper, we consider the partial set multi-cover problem which is a combination of them: given an element set E, a collection of sets S subset of 2(E), a total covering ratio q, each set S is an element of S is associated with a cost c(S), each element e is an element of E is associated with a covering requirement re, the goal is to find a minimum cost sub-collection S' subset of S to fully cover at least q vertical bar E vertical bar elements, where element e is fully covered if it belongs to at least r(e) sets of S'. Denote by r(max) = max{r(e) : e is an element of E} the maximum covering requirement. We present an (O(r(max) log(2) n(1+ ln(1/epsilon) + 1-q/epsilon q)), 1 - epsilon)-bicriteria approximation algorithm, that is, the output of our algorithm has cost O(r(max) log(2) n(1+ ln(1/epsilon) + 1-q/epsilon q)) times of the optimal value while the number of fully covered elements is at least (1 - epsilon)q vertical bar E vertical bar.
Sweep cover is a basic issue in wireless sensor networks, which uses mobile sensors to inspect points of interest (PoIs) periodically. There are many studies on the problem assuming that all mobile sensors have a unif...
详细信息
Sweep cover is a basic issue in wireless sensor networks, which uses mobile sensors to inspect points of interest (PoIs) periodically. There are many studies on the problem assuming that all mobile sensors have a uniform velocity, while some literature shows that using heterogeneous velocities may greatly increase the difficulty of research. In this paper, we study a minimum energy partial sweep cover (MinEPSC) problem on a line, the goal of which is to minimize energy consumption to sweep-cover at least K PoIs, where the energy consumption of a mobile sensor is related with its velocity in somewhat arbitrary but monotone manner. We design algorithms with theoretically guaranteed approximation ratios under different assumptions on the candidate velocity sets. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
In this paper, we investigate the problem of maximizing the difference between an approximately submodular function and a non-negative linear function subject to a matroid constraint. This model has widespread applica...
详细信息
ISBN:
(数字)9783030926816
ISBN:
(纸本)9783030926816;9783030926809
In this paper, we investigate the problem of maximizing the difference between an approximately submodular function and a non-negative linear function subject to a matroid constraint. This model has widespread applications in real life, such as the team formation problem in labor market and the assortment optimization in sales market. We provide a bicriteria approximation algorithm with bifactor ratio (gamma/1+gamma, 1), where gamma is an element of (0, 1] is a parameter to characterize the approximate submodularity. Our result extends Ene's recent work on maximizing the difference between a monotone submodular function and a linear function. Also, a generalized version of the proposed algorithm is capable to deal with huge volume data set.
Submodular function has the property of diminishing marginal gain, and thus it has a wide range of applications in combinatorial optimization and in emerging disciplines such as machine learning and artificial intelli...
详细信息
Submodular function has the property of diminishing marginal gain, and thus it has a wide range of applications in combinatorial optimization and in emerging disciplines such as machine learning and artificial intelligence. For any set S, most of previous works usually do not consider how to compute f (S), but assume that there exists an oracle that will output f (S) directly. In reality, however, the process of computing the exact f is often inevitably inaccurate or costly. At this point, we adopt the easily avail-able noise version F of f . In this paper, we investigate the problems of maximizing a non-negative monotone normalized submodular function minus a non-negative mod-ular function under the e-multiplicative noise in three situations, i.e., the cardinality constraint, the matroid constraint and the online unconstraint. For the above problems, we design three deterministic bicriteria approximation algorithms using greedy and threshold ideas and furthermore obtain good approximation guarantees.
暂无评论