k-Submodular Maximization with a Knapsack Constraint and p Matroid Constraints

被引：2

作者：

Liu, Qian ^{[1
]}

Yu, Kemin ^{[1
]}

Li, Min ^{[1
]}

Zhou, Yang ^{[1
]}

机构：

[1] Shandong Normal Univ, Sch Math & Stat, Jinan 250014, Peoples R China

来源：

TSINGHUA SCIENCE AND TECHNOLOGY | 2023年 / 28卷 / 05期

基金：

中国国家自然科学基金;

关键词：

k-submodularity; knapsack constraint; matroid constraint; approximation algorithm; FUNCTION SUBJECT;

D O I：

10.26599/TST.2022.9010039

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A k-submodular function is a generalization of a submodular function, its definition domain is extended from the collection of single subsets to the collection of k disjoint subsets. The k-submodular maximization problem has a wide range of applications. In this paper, we propose a nested greedy and local search algorithm for the problem of maximizing a monotone k-submodular function subject to a knapsack constraint and p matroid constraints.

引用

页码：896 / 905

页数：10

共 17 条

[11] Rafiey A., 2020, PROC 37 INT C MACHIN, P731
[12] On maximizing a monotone k-submodular function subject to a matroid constraint
Sakaue, Shinsaku
[J]. DISCRETE OPTIMIZATION, 2017, 23 : 105 - 113
[13] Constrained submodular maximization via greedy local search
Sarpatwar, Kanthi K.
Schieber, Baruch
Shachnai, Hadas
[J]. OPERATIONS RESEARCH LETTERS, 2019, 47 (01) : 1 - 6
[14] A note on maximizing a submodular set function subject to a knapsack constraint
Sviridenko, M
[J]. OPERATIONS RESEARCH LETTERS, 2004, 32 (01) : 41 - 43
[15] On maximizing a monotone k-submodular function under a knapsack constraint
Tang, Zhongzheng
Wang, Chenhao
Chan, Hau
[J]. OPERATIONS RESEARCH LETTERS, 2022, 50 (01) : 28 - 31
[16] Maximizing k-Submodular Functions and Beyond
Ward, Justin
Zivny, Stanislav
[J]. ACM TRANSACTIONS ON ALGORITHMS, 2016, 12 (04)
[17] MAXIMIZING A MONOTONE SUBMODULAR FUNCTION WITH A BOUNDED CURVATURE UNDER A KNAPSACK CONSTRAINT
Yoshida, Yuichi
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2019, 33 (03) : 1452 - 1471

← 1 2 →