Two approximation algorithms for maximizing nonnegative weakly monotonic set functions

Min Cui (), Donglei Du (), Dachuan Xu () and Ruiqi Yang ()
Additional contact information
Min Cui: Beijing University of Technology
Donglei Du: University of New Brunswick
Dachuan Xu: Beijing University of Technology
Ruiqi Yang: Beijing University of Technology

Journal of Combinatorial Optimization, 2023, vol. 45, issue 1, No 48, 18 pages

Abstract: Abstract 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 $$\widehat{\gamma }$$ γ ^ . 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 $$\frac{\widehat{\gamma }}{\widehat{\gamma }+2}$$ γ ^ γ ^ + 2 . When $$\widehat{\gamma }=1$$ γ ^ = 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 $$\frac{\widehat{\gamma }}{\widehat{\gamma }+1}$$ γ ^ γ ^ + 1 . When $$\widehat{\gamma }=1$$ γ ^ = 1 , the approximation ratio is 1/2, the same as the best algorithm for the maximization of unconstrained submodular set functions.

Keywords: Unconstrained; Non-submodular; Weakly-monotone; Greedy (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00978-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:45:y:2023:i:1:d:10.1007_s10878-022-00978-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-022-00978-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().