Bibliographic Details
| Title: |
Regularized Submodular Maximization With a k-Matroid Intersection Constraint |
| Authors: |
Qingqin Nong, Zhijia Guo, Suning Gong |
| Source: |
IEEE Access, Vol 11, Pp 103830-103838 (2023) |
| Publisher Information: |
IEEE, 2023. |
| Publication Year: |
2023 |
| Collection: |
LCC:Electrical engineering. Electronics. Nuclear engineering |
| Subject Terms: |
Algorithm design and analysis, distorted greedy, k-matroid intersection, monotonicity, regularized submodularity, Electrical engineering. Electronics. Nuclear engineering, TK1-9971 |
| More Details: |
With the development of the Internet and the emergence of various social-media platforms, designing approximation algorithms for optimization problems such as the influence maximization in social networks has received widespread attention. With considering cost, these problems are typically modeled as the regularized submodular optimization, in which a regularized submodular function is expressed as the difference of a nonnegative submodular revenue function $f(\cdot )$ and a nonnegative modular cost function $c(\cdot )$ . In this paper, we consider two kinds of regularized submodular maximization problems with a $k$ -matroid intersection constraint. When $f(\cdot )$ is additionally monotone, we provide a distorted greedy algorithm with a tight constant bicriteria approximation ratio and a time complexity of $O(n^{2})$ . When $f(\cdot )$ is nonmonotone, we combine the distorted greedy algorithm with a simple stochastic process to design a constant bicriteria approximation algorithm with a time complexity of $O(kn^{2})$ . To our knowledge, this is the first paper to design polynomial-time algorithms for the regularized submodular maximization with a $k$ -matroid intersection constraint. |
| Document Type: |
article |
| File Description: |
electronic resource |
| Language: |
English |
| ISSN: |
2169-3536 |
| Relation: |
https://ieeexplore.ieee.org/document/10256173/; https://doaj.org/toc/2169-3536 |
| DOI: |
10.1109/ACCESS.2023.3317691 |
| Access URL: |
https://doaj.org/article/c513965d8cb0449bba95052bc96f0201 |
| Accession Number: |
edsdoj.513965d8cb0449bba95052bc96f0201 |
| Database: |
Directory of Open Access Journals |
