Randomized Parallel Algorithm for Maximizing Nonsubmodular Function Subject to Cardinality Constraint

Jingjing Tan (), Wenting Chen, Meixia Li and Wenchao Wang ()
Additional contact information
Jingjing Tan: School of Mathematics and Information Science, Weifang University, Weifang Shandong, 261061, P. R. China
Wenting Chen: School of Mathematics and Systems Science, Shandong University of Science and Technology, Qingdao Shandong 266590, P. R. China
Meixia Li: School of Mathematics and Information Science, Weifang University, Weifang Shandong, 261061, P. R. China
Wenchao Wang: School of Mathematics and Systems Science, Shandong University of Science and Technology, Qingdao Shandong 266590, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2021, vol. 38, issue 05, 1-11

Abstract: The problem of maximization submodular functions with a cardinality constraint has been extensively researched in recent years. Balkanski and Singer were the first to study this class problem. Subsequently, Chekuri and Kent recently extended these results to more general constraints, that is, k-cardinality constraint, partition and laminar matroids, matching, knapsack constraints, and including their intersection. They proposed a (1 − 1/e − 𝜀) approximation randomized-parallel-greedy algorithm which are poly-logarithmic adaptivity. However, these existing approaches are hardly extended to the nonsubmodular case. In this paper, we investigate the problem of maximization on a nonsubmodular function subject to a cardinality constraint, provided the objective function is specified by a generic submodularity ratio γ. We design a (1 − e−γ − 𝜀)-approximation Greedy algorithm by using the technical aspects to maximize the multilinear relaxation of the object function under the k-cardinality constraints. The adaptive of multilinear relaxation is O(log n/𝜀2); the number of oracle is Õ(n/𝜀4).

Keywords: Cardinality; nonsubmodular function; randomized parallel algorithm; multilinear relaxation (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595921400091
Access to full text is restricted to subscribers

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:wsi:apjorx:v:38:y:2021:i:05:n:s0217595921400091

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595921400091

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().