.png){kind=icon}
.png){kind=icon}
Return
The approximation algorithm and fast algorithm for constrained or-submodular maximization problem
.png){kind=icon}
PRE
AI
DOI：10.1007/s10878-026-01421-8.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The problem of maximizing k-submodular functions is a classical issue in the field of combinatorial optimization. In our work, we primarily consider an orsubmodular function, which is a generalization of k-submodular. For maximizing the or-submodular function problem, we first propose a greedy algorithm to get a 1/r+1-approximation ratio under a matroid constraint and design a fast algorithm to reduce its complexity, where 1 <= r <= k. In addition, we also use a greedy algorithm to obtain an approximation solution of r/1+1 (1-e(-(r+1))) for maximizing the or-submodular function with a knapsack constraint, where 1 <= r <= k.
Keywords:
Approximation algorithm
Fast algorithm
Matroid
Knapsack
or-Submodularity
Journal
J
IF:
1.1
Papers:
78
Citations:
0