Loading…
Two approximation algorithms for maximizing nonnegative weakly monotonic set functions
Many combinatorial optimization problems can be reduced to submodular optimization problems. However, many cases in practical applications do not fully comply with the diminishing returns characteristic. This paper studies the problem of maximizing weakly-monotone non-submodular non-negative set fun...
Saved in:
Published in: | Journal of combinatorial optimization 2023, Vol.45 (1), Article 54 |
---|---|
Main Authors: | , , , |
Format: | Article |
Language: | English |
Subjects: | |
Citations: | Items that this one cites |
Online Access: | Get full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Summary: | Many combinatorial optimization problems can be reduced to submodular optimization problems. However, many cases in practical applications do not fully comply with the diminishing returns characteristic. This paper studies the problem of maximizing weakly-monotone non-submodular non-negative set functions without constraints, and extends the normal submodular ratio to weakly-monotone submodular ratio
γ
^
. In this paper, two algorithms are given for the above problems. The first one is a deterministic greedy approximation algorithm, which realizes the approximation ratio of
γ
^
γ
^
+
2
. When
γ
^
=
1
, the approximate ratio is 1/3, which matches the ratio of the best deterministic algorithm known for the maximization of submodular function without constraints. The second algorithm is a random greedy algorithm, which improves the approximation ratio to
γ
^
γ
^
+
1
. When
γ
^
=
1
, the approximation ratio is 1/2, the same as the best algorithm for the maximization of unconstrained submodular set functions. |
---|---|
ISSN: | 1382-6905 1573-2886 |
DOI: | 10.1007/s10878-022-00978-4 |