Academy of Mathematics and Systems Science, CAS
Colloquia & Seminars

Speaker:	唐中正，北京邮电大学
Inviter:	陈旭瑾
Title:	Improved Analysis of Greedy Algorithm on k-Submodular Knapsack
Language:	Chinese&English
Time & Venue:	2023.08.15 16:00-17:00 南楼N602
Abstract:	A k-submodular function is a generalization of submodular functions that takes k disjoint subsets as input and outputs a real value. It captures many problems in combinatorial optimization and machine leaning such as influence maximization, sensor placement,etc.In this work,we consider the monotone k-submodular maximization problem under a knapsack constraint, and explore the performance guarantee of a greedy-based algorithm: enumerating all size-2 solutions and extending every singleton solution greedily; the best outcome is returned. We provide a novel analysis framework and prove that this algorithm achieves an approximation ratio of at least 0.328.