Greedy Guarantees for Non-submodular Function Maximization Under Independent System Constraint with Applications

Majun Shi (), Zishen Yang () and Wei Wang ()
Additional contact information
Majun Shi: Xi’an Jiaotong University
Zishen Yang: Xi’an Jiaotong University
Wei Wang: Xi’an Jiaotong University

Journal of Optimization Theory and Applications, 2023, vol. 196, issue 2, No 6, 516-543

Abstract: Abstract We study the problems of maximizing a monotone non-submodular function subject to two types of constraints, either an independent system constraint or a p-matroid constraint. These problems often occur in the context of combinatorial optimization, operations research, economics and especially, machine learning and data science. Using the generalized curvature $$\alpha $$ α and the submodularity ratio $$\gamma $$ γ or the diminishing returns ratio $$\xi $$ ξ , we analyze the performances of the widely used greedy algorithm, which yields theoretical approximation guarantees of $$\frac{1}{\alpha }[1-(1-\frac{\alpha \gamma }{K})^k]$$ 1 α [ 1 - ( 1 - α γ K ) k ] and $$\frac{\xi }{p + \alpha \xi }$$ ξ p + α ξ for the two types of constraints, respectively, where k, K are, respectively, the minimum and maximum cardinalities of a maximal independent set in the independent system, and p is the minimum number of matroids such that the independent system can be expressed as the intersection of p matroids. When the constraint is a cardinality one, our result maintains the same approximation ratio as that in Bian et al. (Proceedings of the 34th international conference on machine learning, pp 498–507, 2017); however, the proof is much simpler owning to the new definition of the greedy curvature. In the case of a single matroid constraint, our result is competitive compared with the existing ones in Chen et al. (Proceedings of the 35th international conference on machine learning, pp 804–813, 2018) and Gatmiry and Rodriguez (Non-submodular function maximization subject to a matroid constraint, with applications, 2018. arXiv:1811.07863v4 ). In addition, we bound the generalized curvature, the submodularity ratio and the diminishing returns ratio for several important real-world applications. Computational experiments are also provided supporting our analyses.

Keywords: Non-submodular function; Independent system; p-matroid; Greedy algorithm (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/s10957-022-02145-5 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:joptap:v:196:y:2023:i:2:d:10.1007_s10957-022-02145-5

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-022-02145-5

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

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